Обсуждение:Алгоритм сортировки
Просьба указать источники алгоритма Шелла за O(n log n) и сортировки Акульшина. Jukier 07:33, 18 июля 2008 (UTC)
В англоязычной статье сортировки Шелла есть ссылка на статью 1992 года, в которой доказана невозможность оценки O(n log n), исправил оценку на O(n log2 n) Jukier 10:19, 19 июля 2008 (UTC)
Вроде как одно и тоже:
Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок. Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
Или я заблуждаюсь?--Fat-Zer 07:55, 3 марта 2010 (UTC)
Алгоритмы, не основанные на сравнениях
Блочная сортировка (Корзинная сортировка, Bucket sort) Лексикографическая или поразрядная сортировка (Radix sort)
Сортировка подсчётом (Counting sort)
Во-первых, эти алгоритмы указаны в других разделах, предлагаю удалить их из других частей и оставить в этой, а, во-вторых, сам раздел переименовать во что-то вроде "Алгоритмы, требующие дополнительных сведений о природе данных"--Fat-Zer 07:55, 3 марта 2010 (UTC)
Остальные алгоритмы сортировки
Топологическая сортировка
Внешняя сортировка
Это всё вообще не из этой оперы.--Fat-Zer 07:55, 3 марта 2010 (UTC)
хочу добавить скрипт на AUTOIT для сравнения алгоритмов сортировки[править код]
#include <Array.au3>
dim $length=100 ;длинна массива
dim $myarray[$length+1][3]
;создание случайного массива данных, и его дублирование для разных алгоритмов + исходный массив данных для проверки
For $i=1 To $length Step 1
$myarray[$i][0]=Round(Random(0,999),0)
$myarray[$i][1]=$myarray[$i][0]
$myarray[$i][2]=$myarray[$i][0]
Next
;наихудший вариант массива по убыванию
;~ For $i=1 To $length Step 1
;~ $myarray[$i][0]=$length-$i+1
;~ $myarray[$i][1]=$myarray[$i][0]
;~ $myarray[$i][2]=$myarray[$i][0]
;~ Next
;~ ====================== пузырьковая сортировка ===============================================================
$count_math=0 ;счетчик количества операций вычисления
$count_logic=0 ;счетчик количества операций сравнения
$count_ch=0 ;счетчик количества операций изменения значения
$timer_start = TimerInit()
for $i=$length To 1 Step -1
for $j=1 To $i-1 Step 1
$count_logic+=1
If $myarray[$j+1][0]<$myarray[$j][0] Then
$count_ch+=3
$temp = $myarray[$j+1][0]
$myarray[$j+1][0] = $myarray[$j][0]
$myarray[$j][0] = $temp
EndIf
$count_ch+=1
$count_math+=1
Next
$count_ch+=1
$count_math+=1
Next
$myarray[0][0] =$count_math & 'm - ' & $count_logic & 'l - ' & $count_ch & 'c - ' & TimerDiff($timer_start)
;~ ========================== пузырьковая улучшенная сортировка ==================================================
$count_math=0 ;счетчик количества операций вычисления
$count_logic=0 ;счетчик количества операций сравнения
$count_ch=0 ;счетчик количества операций изменения значения
$timer_start = TimerInit()
for $i=$length To 1 Step -1
$count_ch+=1
$max=1
for $j=2 To $i-1 Step 1
$count_logic+=1
If $myarray[$max][1]<$myarray[$j][1] Then
$count_ch+=1
$max=$j
EndIf
$count_math+=1
$count_ch+=1
Next
$count_logic+=1
If $myarray[$max][1]>$myarray[$j][1] Then
$count_ch+=3
$temp = $myarray[$max][1]
$myarray[$max][1] = $myarray[$j][1]
$myarray[$j][1] = $temp
EndIf
$count_math+=1
$count_ch+=1
Next
$myarray[0][1] = $count_math & 'm - ' & $count_logic & 'l - ' & $count_ch & 'c - ' & TimerDiff($timer_start)
_ArrayDisplay($myarray)
|
194.44.50.253 10:56, 31 января 2012 (UTC) Sergio
Формальное определение[править код]
В статье полностью отсутствует формальное определение алгоритма сортировки, а также, определение упорядочивания. 176.15.230.164 08:06, 13 сентября 2012 (UTC)
- у Кнута, например, есть. Попробую написать. РоманСузи 16:52, 13 сентября 2012 (UTC)
- Привел формальное определение. Конечно, Кнут несколько оригинален, но зато краток. Иначе пришлось бы про отношение частичного порядка писать и т. п. Вместо "записей" и "файла" я записал "элементы" и "массив", дав другие варианты в примечании.РоманСузи 17:33, 13 сентября 2012 (UTC)
Я только не понял, почему в разделе об оценке говорится о множестве. РоманСузи 17:44, 13 сентября 2012 (UTC)
Пузырьковая сортировка. Устойчивость[править код]
Пузырьковая сортировка может оказаться неустойчивой в некоторых случаях. Поэтому её можно перенести в категорию неустойчивых. Для примера можно отсортировать массив 2 3 2 3 5 4 1 4. Для проверки усточивости можно создть двумерный массив. Например 1-2 2-3 3-2 4-3 5-5 6-4 7-1 8-4
Массив после сортировки: 5-5 6-4 8-4 4-3 2-3 1-2 3-2 7-1 Как видно по строкам с одинаковым вторым элементом "3" - сортировка не сохранила порядок для заданного массива.
Cheshire a 10:00, 8 апреля 2013 (UTC)Wazaaaaaa
А это что за покемон?[править код]
http://habrahabr.ru/post/208088/ Тут вот новый что-ли изобрели? --Higimo 04:24, 10 января 2014 (UTC)