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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
roman ua
1 / 1 / 0
Регистрация: 06.03.2009
Сообщений: 25
#1

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

25.11.2010, 17:48. Просмотров 587. Ответов 3
Метки нет (Все метки)

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

Буду очень благодарен за помощь! !!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2010, 17:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинированый алгоритм сортировки (C++):

Алгоритм сортировки - C++
пацаны ребята помогите, реализовал два алгоритма на C++, алгоритм сортировки пирамидальный(кучей) и быстрой сортировки, все они сортируют...

Алгоритм сортировки - C++
учитель попросил написать сортировку массива по возрастанию в общем виде #include <stdio.h> #include <string.h> int main() { ...

Алгоритм сортировки - C++
Здравствуйте, подскажите пожалуйста какой алгоритм можно использовать при решении такой задачи: Дана строка char * из букв и цифр...

Алгоритм сортировки - C++
Дан одномерный масив. мне в нем нужно отсортировать по возростанию только те числа масива которые простые, а остальные оставить на той...

Алгоритм сортировки Шелла - C++
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/21/2107.htm здесь сказано, что существует, некая последовательность...

Алгоритм сортировки в файле - C++
Никак не могу придумать как отсортировать массив значений. Есть файл, в котором находятся данные типа (вершины прямоугольник) : 20 20 69...

3
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2010, 17:57 #2
roman ua, Вы не совсем правильно поняли. Используя не более N+2 сравнений, это подойдет для N равное 5. Но для больших значений N никакая сортировка не сможет быть реализована за не более N+2 сравнений.
0
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 сравнений. Предложить обобщенный алгоритм сортировки таких последовательностей, сохраняя пропорцию количества сравнений."
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.11.2010, 18:42 #4
Иначе не было бы кучи разных алгоритмов сортировки, применяемых для разных массивов и имеющих на них разное время работы и т.д.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2010, 18:42
Привет! Вот еще темы с ответами:

Не алгоритм быстрой сортировки - C++
Просто как подключить эту функцию Не работаеееет #include<iostream> #include<iomanip> #include <algorithm> using namespace std; ...

Реализовать алгоритм сортировки - C++
На рисунке расположены, все возможные компоненты имеющие свойства x,y. Размер рабочей части 8x8, но может быть и больше. Задача такая:...

Алгоритм быстрой сортировки - C++
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для массива целых чисел.

Алгоритм плавной сортировки (C++ -> Си) - C++
static void SmoothSort(String Aarg, const int N) { int temp; A = Aarg; q = 1; r = 0; p = 1; b = 1; c = 1; while...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
25.11.2010, 18:42
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru