Новые сообщения · Правила  
Страница 1 из 11
Модератор форума: Berestovskiy 
Форум ПРОГРАММИСТОВ » ПРОГРАММИРОВАНИЕ » С, C++ » Сортирока [С++]
Сортирока [С++]
Помогите - не знаю не я не одногруппники у кого не спрашивала
вот такой попался вариант

Хоть подскажите пожалуйста)
Написать программу на языке C/C++
которая:
1) реализует указанные в индивидуальном задании методы сортировки
массивов в отдельных модулях;
2) использует системную стандартную сортировку qsort;
3) демонстрирует их работу на тестовых примерах;
4) засекает время их работы и строит график, отображающий скорость
работы всех реализованных методов в зависимости от размера
массива.
~~~~~~~~~~~~~~~~
Задание.
Пусть каждому элементу массива сопоставлено положительное
число ("вес") W[i], причём сумма всех весов равна 1.
Взвешенной медианой называется такое число X[k], что
(sum[i]: X[i]<X[k] : W[i]) <= 1/2 и
(sum[i]: X[i]>X[k] : W[i]) <= 1/2
Если все веса равны, то взвешенная медиана совпадает с обычной.
А. Напишите программу нахождения взвешенной медианы с помощью
сортировки за время O(N log N) в худшем случае.
Б. Напишите программу нахождения взвешенной медианы с помощью
алгоритма разбиения (см.QSort) за время O(N) в худшем случае.

1 | Автор: Sunless | 2011-04-05, 13:04   |  Репутация: [ + 0 ]
Форум ПРОГРАММИСТОВ » ПРОГРАММИРОВАНИЕ » С, C++ » Сортирока [С++]
Страница 1 из 11
Поиск: