![]() |
![]() ![]() |
![]() |
virt |
![]()
Сообщение
#1
|
![]() Знаток ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: ![]() ![]() ![]() |
Описание и реализация алгоритмов:
****** ****** Сравнительная скорость работы некоторых нижеприведенных алгоритмов сортировки: ![]() Примечание: size: размер сортируемой последовательности n: количество сортировок для замера времени *: RadixSort в последнем тесте прогонялся при параметрах: size=21000; n=100 |
virt |
![]()
Сообщение
#2
|
![]() Знаток ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: ![]() ![]() ![]() |
Пузырьковая сортировка (простым выбором, простым обменом, линейная)
Последовательно просматривая числа a1 , ... , an находим наименьшее i такое, что ai > ai+1 . Меняем ai и ai+1 местами, продолжаем просмотр с элемента ai+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать со второго элемента, при этом количество просматриваемых элементов уменьшится на единицу. Массив будет упорядочен после просмотра, в котором участвовали только элементы an-1 и an. Скачать: Type Пример использования Const Реализация пузырьковой сортировки на ассемблере: procedure BubbleSort(Mas: Pointer; Len: LongWord); Сложность этого метода сортировки составляет О(n^2) Сообщение отредактировано: klem4 - 2.12.2007 12:04 |
virt |
![]()
Сообщение
#3
|
![]() Знаток ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: ![]() ![]() ![]() |
Сортировка простой вставкой
Скачать: ![]() Type Сложность О(n^2) Сообщение отредактировано: Lapp - 13.09.2009 5:04 |
volvo |
![]()
Сообщение
#4
|
Гость ![]() |
Сортировка слияниями
Type Сложность О(n*logn), самая быстрая из сортировок, но использует в 2 раза больше оперативной памяти. |
volvo |
![]()
Сообщение
#5
|
Гость ![]() |
Быстрая сортировка Хоара
Это улучшенный метод, основанный на обмене. При "пузырьковой" сортировке производятся обмены элементов в соседних позициях. При пирамидальной сортировке такой обмен совершается между элементами в позициях, жестко связанных друг с другом бинарным деревом. Ниже будет рассмотрен алгоритм сортировки К. Хоара, использующий несколько иной механизм выбора значений для обменов. Этот алгоритм называется сортировкой с разделением или быстрой сортировкой. Она основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что даны N элементов массива, расположенные в обратном порядке. Их можно рассортировать, выполнив всего N/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так далее, постепенно продвигаясь с двух сторон к середине. Это возможно только, если мы знаем, что элементы расположены строго в обратном порядке. Рассмотрим следующий алгоритм: выберем случайным образом какой-то элемент массива (назовем его X). Просмотрим массив, двигаясь слева направо, пока не найдем элемент a[ i ]>X (сортируем по возрастанию), а затем просмотрим массив справа налево, пока не найдем элемент a[ j ]<X. Далее, поменяем местами эти два элемента a[ i ] и a[ j ] и продолжим этот процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. После такого просмотра массив разделится на две части: левую с элементами меньшими (или равными) X, и правую с элементами большими (или равными) X. Итак, пусть a[k] (k=1,...,N) - одномерный массив, и X - какой-либо элемент из a. Надо разбить "a" на две непустые непересекающиеся части а1 и а2 так, чтобы в a1 оказались элементы, не превосходящие X, а в а2 - не меньшие X. Рассмотрим пример. Пусть в массиве a: <6, 23, 17, 8, 14, 25, 6, 3, 30, 7> зафиксирован элемент x=14. Просматриваем массив a слева направо, пока не найдем a[ i ]>x. Получаем a[2]=23. Далее, просматриваем a справа налево, пока не найдем a[ j ]<x. Получаем a[10]=7. Меняем местами a[2] и a[10]. Продолжая этот процесс, придем к массиву <6, 7, 3, 8, 6> <25, 14, 17, 30, 23>, разделенному на две требуемые части a1, a2. Последние значения индексов таковы: i=6, j=5. Элементы a[1],....,a[i-1] меньше или равны x=14, а элементы a[j+1],...,a[n] больше или равны x. Следовательно, разделение массива произошло. Описанный алгоритм прост и эффективен, так как сравниваемые переменные i, j и x можно хранить во время просмотра в быстрых регистрах процессора. Наша конечная цель - не только провести разделение на указанные части исходного массива элементов, но и отсортировать его. Для этого нужно применить процесс разделения к получившимся двум частям, затем к частям частей, и так далее до тех пор, пока каждая из частей не будет состоять из одного единственного элемента. Эти действия описываются следующей программой. Процедура Sort реализует разделение массива на две части, и рекурсивно обращается сама к себе... Type Type Сложность O(n*logn), на некоторых тестах работает быстрее сортировки слияниями, но на некоторых специально подобранных - работает за O(n^2). |
volvo |
![]()
Сообщение
#6
|
Гость ![]() |
Пирамидальная - турнирная - HeapSort сортировка
Скачать: ![]() Type Сложность O(n*logn), самая стабильная сортировка, на любых входных данных работает за одинаковое время. Но зато немного медленнее чем слияниями и быстрая. |
volvo |
![]()
Сообщение
#7
|
Гость ![]() |
Распределяющая сортировка - RadixSort - цифровая - поразрядная
Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки. Разрядность данных (количество возможных значений элементов) - m - также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=256. Пусть у нас есть массив source из n элементов по одному байту в каждом. Для примера можете выписать на листочек массив source = <7, 9, 8, 5, 4, 7, 7>, и проделать с ним все операции, имея в виду m=9.
Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт. Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ). Цитата сначала они в сортируем по младшему на один беспорядке: разряду: выше: и еще раз: 523 523 523 088 153 153 235 153 088 554 153 235 554 235 554 523 235 088 088 554 Hу вот мы и отсортировали за O(k*n) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то 'поразрядная сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'! Реализация алгоритма "распределяющей" сортировки: Скачать: ![]() Const |
klem4 |
![]()
Сообщение
#8
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Пузырьковая сортировка с просеиванием
Аналогичен методу пузырьковой сортировки, но после перестановки пары соседних элементов выполняется просеивание: наименьший левый элемент продвигается к началу массива насколько это возможно, пока не выполняется условие упорядоченности. Преимущество: простой метод пузырька работает крайне медленно, когда мин/макс (в зависимости от направления сортировки) элемент массива стоит в конце, этот алгоритм - намного быстрее. const n = 10; Добавлено: Тестировалось на массиве целых чисел (25000 элементов). Прирост скорости относительно простой пузырьковой сортировки - около 75%... volvo |
volvo |
![]()
Сообщение
#9
|
Гость ![]() |
Древесная сортировка (TreeSort)
Использует Двоичные (бинарные) деревья, в которых для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику. При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место: если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить. Если мы будем рекурсивно обходить дерево по правилу "левый сын -> родитель -> правый сын", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. Hа этом и основана идея сортировки деревом. Более подробно правило обхода можно сформулировать так: обойти левое поддерево -> вывести корень -> обойти правое поддерево, где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается с узлом-родителем и выдает очередной элемент, если у узла нет сыновей. Const n = 8; Общее быстродействие метода O(n*logn). Поведение неестественно, устойчивости, вообще говоря, нет. Основной недостаток этого метода - большие требования к памяти под дерево. Очевидно, нужно n места под ключи и, кроме того, память на 2 указателя для каждого из них. Поэтому TreeSort обычно применяют там, где:
Прикрепленные файлы ![]() |
klem4 |
![]()
Сообщение
#10
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Сортировка методом поиска нового номера (в новый массив)
Краткая теория: Последовательно для каждого элемента массива вычисляется его новая позиция в отсортированном массиве, рассчитывается кол-во элементов, значения которых
Особенности: Требуется дополнительный массив, не чувствительный к изначальной упорядоченности. Оценка числа операций: N*N type Пример использования: NewNSort(mass1, NewMass, n); Массив NewMass будет состоять из элементов массива mass1, но уже отсортированных. На небольших массивах работает неплохо. Добавлено: Тесты на скорость (в условных единицах): 1. (набор данных - массив из 8 элементов типа integer) Количество тестов: n = 4 000 000 #1: 292 (метод нового номера) #2: 558 (сортировка пузырьком) #3: 490 (поразрядная сортировка - radixsort) 2. (набор данных - массив из 800 элементов типа integer) Количество тестов: n = 225 #1: 95 (метод нового номера) #2: 174 (сортировка пузырьком) #3: 2 (поразрядная сортировка - radixsort) На небольших массивах действительно достаточно быстрый метод, но с увеличением размера массива "метод нового номера" начинает значительно проигрывать поразрядной сортировке. volvo |
klem4 |
![]()
Сообщение
#11
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Метод последовательного поиска минимумов
Теория: Просматривается весь массив, ищется минимальный элемент и ставится на место первого, "старый" первый элемент ставится на место найденного type Вызов: NextMinSearchSort(mass1, n); Добавлено: Тесты на скорость (в условных единицах): 1. (набор данных - массив из 15 элементов типа integer) Количество тестов: n = 1 000 000 #1: 159 (метод нового номера) #2: 127 (поразрядная сортировка - radixsort) #3: 61 (метод поиска минимумов) 2. (набор данных - массив из 800 элементов типа integer) Количество тестов: n = 225 #1: 107 (метод нового номера) #2: 1 (поразрядная сортировка - radixsort) #3: 25 (метод поиска минимумов) 3. (набор данных - массив из 10000 элементов типа integer) Количество тестов: n = 9 #1: 597 (метод нового номера) #2: 2 (поразрядная сортировка - radixsort) #3: 147 (метод поиска минимумов) volvo |
![]() ![]() |
![]() |
Текстовая версия | 8.09.2024 4:38 |