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

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

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

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

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

Нужно написать програму на языке С когда имеется алгоритм ! Задача в слудуещем: сортировка масива с 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++
учитель попросил написать сортировку массива по возрастанию в общем виде #include <stdio.h> #include <string.h> int main() { ...

Не работает алгоритм сортировки - C++
Не работает алгоритм сортировки Ни при заполнении псевдослучайными числами,ни при заранее заданных. Подскажите пожалуйста, в чем...

Алгоритм сортировки,ошибка! - C++
У меня алгоритм сортировки вставками но вот только не сортирует почему то #include <stdio.h> #include <stdlib.h> #include...

Алгоритм квадратичной сортировки - C++
Доброго времени суток! есть вот такая задача: При составлении программы сортировки использовать минимальную необходимую память и...

Неизвестный алгоритм сортировки - C++
Доброго времени суток! Возможно вопрос данный выглядит весьма по-дурацки, но тем не менее. Предыстория такова. Некоторое время назад...

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

Алгоритм плавной сортировки (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...

Алгоритм сортировки вставками - C++
Привет, всем! В алгоритме непонятна одна строчка: #include<iostream> #include<cstdlib> using namespace std; int...

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.11.2010, 18:42     Комбинированый алгоритм сортировки #4
Иначе не было бы кучи разных алгоритмов сортировки, применяемых для разных массивов и имеющих на них разное время работы и т.д.
Yandex
Объявления
25.11.2010, 18:42     Комбинированый алгоритм сортировки
Ответ Создать тему
Опции темы

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