Форум программистов, компьютерный форум CyberForum.ru

Комбинированый алгоритм сортировки - C++

Восстановить пароль Регистрация
 
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 17:48     Комбинированый алгоритм сортировки #1
Нужно написать програму на языке С когда имеется алгоритм ! Задача в слудуещем: сортировка масива с N- разных чисел, используя не более N+2 сравнений .
Сам алгоритм виглядить так:
1)Разбиваем масив на 2 части (в одной части будет N/2 чисел,и во второй N/2 - для четного N и в одной части будет N/2 чисел,и во второй (N/2) +1 - для нечетного N ).
2)В этих частях делаем сортировку вставкой.
3)А потом обе части сортируем слиянием.
4)У нас получится не более N+2 сравнений.

Буду очень благодарен за помощь! !!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2010, 17:48     Комбинированый алгоритм сортировки
Посмотрите здесь:

C++ Алгоритм сортировки
Алгоритм квадратичной сортировки C++
C++ Алгоритм сортировки
Алгоритм сортировки,ошибка! C++
C++ Алгоритм сортировки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2010, 17:57     Комбинированый алгоритм сортировки #2
roman ua, Вы не совсем правильно поняли. Используя не более N+2 сравнений, это подойдет для N равное 5. Но для больших значений N никакая сортировка не сможет быть реализована за не более N+2 сравнений.
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
25.11.2010, 18:07  [ТС]     Комбинированый алгоритм сортировки #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
roman ua, Вы не совсем правильно поняли. Используя не более N+2 сравнений, это подойдет для N равное 5. Но для больших значений N никакая сортировка не сможет быть реализована за не более N+2 сравнений.
Виходит, что задача(особенно вторая ее часть ) не имеет разрешения??? Поскольку такого алгоритма не существует?
" Ввести пять попарно различных целых чисел a, b, c, d, e. Упорядочить их по возрастанию, используя не более 7 сравнений. Предложить обобщенный алгоритм сортировки таких последовательностей, сохраняя пропорцию количества сравнений."
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2010, 18:42     Комбинированый алгоритм сортировки #4
Иначе не было бы кучи разных алгоритмов сортировки, применяемых для разных массивов и имеющих на них разное время работы и т.д.
Yandex
Объявления
25.11.2010, 18:42     Комбинированый алгоритм сортировки
Ответ Создать тему
Опции темы

Текущее время: 05:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru