Выбор оптимального алгоритма сортировки.

@Ham · Регистрация: 20.05.2011

Author24 — интернет-сервис помощи студентам

Характеристика массива:отсортирован в случайном порядке.
Необходимо подобрать метод сортировки по возрастанию и обосновать выбор.

@OstapBender · 20.05.2011, 01:33

пузырьковая сортировка - максимальная простота
быстрая сортировка - оптимальное время
реализации гуглите ... их полно ...

@Mиxaил · 20.05.2011, 01:37

Как - то давно тестировал известные и частовстречаемые сортировки... Всевозможные тесты показали, что сортировка "вставками" выполняет сортировку (~) в два раза быстрее, чем "пузырьковая"... Так же можно увеличить скорость сортировки с помощью модернизации...

@lemegeton · 20.05.2011, 11:58

Если массив большой (надо посчитать, ну, скажем больше сотни элементов), быстрее будет qsort. Если не большой, сортировка Шелла (модификация сортировки вставками).

@diagon · 20.05.2011, 12:02

C++

std::sort

Очень навороченная реализация быстрой сортировки

@OMAAGAAD · 20.05.2011, 17:11

Очень рекомендую посмотреть сюда

Нажмите на зеленый значок "обновить" и убедитесь сами)

@diagon · 20.05.2011, 18:12

Есть еще интересная сортировка подсчетом
Вроде самая быстрая, но хороша, только если значения элементов массива ограничены.
Вот пример, писал когда-то, там значения по модулю не превосходят 100.

C++

#include <iostream>
int d[201];
int main(){
    int n,x,i;
    std::cin >> n;
    for (i = 0; i < n; i++) {
        std::cin >> x;
        d[x+100]++;
    }
    for (x = 0; x < 201; x++)
        for (i = 0; i < d[x];i++ )
            std::cout << x-100 << ' ';
    return 0;
}

@Ham · 20.05.2011, 18:41 **[ТС]**

Всем спасибо.Помогли.

@Ham 0 / 0 / 0 Регистрация: 20.05.2011 Сообщений: 10
		1
	Выбор оптимального алгоритма сортировки. 20.05.2011, 01:30. Показов 2116. Ответов 7 Метки нет (Все метки) Характеристика массива:отсортирован в случайном порядке. Необходимо подобрать метод сортировки по возрастанию и обосновать выбор. 0

@OstapBender 594 / 532 / 76 Регистрация: 22.03.2011 Сообщений: 1,585
	20.05.2011, 01:33	2
	пузырьковая сортировка - максимальная простота быстрая сортировка - оптимальное время реализации гуглите ... их полно ... 0

@Mиxaил 542 / 447 / 162 Регистрация: 10.12.2009 Сообщений: 1,857
	20.05.2011, 01:37	3
	Как - то давно тестировал известные и частовстречаемые сортировки... Всевозможные тесты показали, что сортировка "вставками" выполняет сортировку (~) в два раза быстрее, чем "пузырьковая"... Так же можно увеличить скорость сортировки с помощью модернизации... 0

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	20.05.2011, 11:58	4
	Если массив большой (надо посчитать, ну, скажем больше сотни элементов), быстрее будет qsort. Если не большой, сортировка Шелла (модификация сортировки вставками). 0

@OMAAGAAD 15 / 15 / 3 Регистрация: 24.09.2010 Сообщений: 45
	20.05.2011, 17:11	6
	Сообщение было отмечено как решение Решение Очень рекомендую посмотреть сюда Нажмите на зеленый значок "обновить" и убедитесь сами) 3

@Ham 0 / 0 / 0 Регистрация: 20.05.2011 Сообщений: 10
	20.05.2011, 18:41 [ТС]	8
	Всем спасибо.Помогли. 0

Выбор оптимального алгоритма сортировки.

Решение