СОРТИРОВКА Комбинаторные алгоритмы Выполнил: Припадчев Артём, группа 1125. - презентация

1 СОРТИРОВКА Комбинаторные алгоритмы Выполнил: Припадчев Артём, группа 1125

2 Дональд Шелл 1959 год Среднее время работы алгоритма: t = a*N 1.5

3 public static long shellSort(int[] array) { Stopwatch sw = new Stopwatch(); sw.Start(); int step = array.Length / 2; while (step > 0) { int i, j; for (i = step; i < array.Length; i++) { int value = array[i]; for (j = i - step; (j >= 0) && (array[j] > value); j -= step) array[j + step] = array[j]; array[j + step] = value; } step /= 2; } sw.Stop(); return sw.ElapsedTicks;

4 Чарльз Хоар 1960 год Среднее время работы алгоритма: t = N * log N

5 array[A] = array[B]; array[B] = T; ++A; --B; } if (a < B) Sort.QuickSort(array, a, B); if (A < b) QuickSort(array, A, b); } sw.Stop(); return sw.ElapsedTicks; public static long QuickSort(int[] array, int a, int b) { Stopwatch sw = new Stopwatch(); sw.Start(); int A = a; int B = b; double mid; if (b > a) { mid = array[(a + b) / 2]; while (A <= B) { while ((A < b) && (array[A] < mid)) ++A; while ((B > a) && (array[B] > mid)) --B; if (A <= B) { int T; T = array[A];

6 t = 0.185*N*log(N)

7

8 t = 0.1*N*log(N)

9 private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer comparer) { while (hi > lo) { int num = (hi - lo) + 1; if (num <= 0x10) { switch (num) { case 1: return; case 2: ArraySortHelper.SwapIfGreater(keys, comparer, lo, hi); return; case 3: ArraySortHelper.SwapIfGreater(keys, comparer, lo, hi - 1); ArraySortHelper.SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper.SwapIfGreater(keys, comparer, hi - 1, hi); return; } ArraySortHelper.InsertionSort(keys, lo, hi, comparer); return; } if (depthLimit == 0) { ArraySortHelper.Heapsort(keys, lo, hi, comparer); return; } depthLimit--; int num2 = ArraySortHelper.PickPivotAndPartition(keys, lo, hi, comparer); ArraySortHelper.IntroSort(keys, num2 + 1, hi, depthLimit, comparer); hi = num2 - 1; }

10 InsertionSort Heapsort (Пирамидальная сортировка) t = N * log N t = N 2 Introsort (интроспективная сортировка) InsertionSort InsertionSort Heapsort Heapsort

11 Выводы: Самой эффективной оказалась встроенная в.NET сортировка, т.к. она включает в себя анализ переданных ей входных данных и вызывает различные методы сортировки Самой эффективной оказалась встроенная в.NET сортировка, т.к. она включает в себя анализ переданных ей входных данных и вызывает различные методы сортировки Для коллекций, в которых количество элементов меньше 512 лучше использовать сортировку методом Шелла, нежели QuickSort (если не использовать встроенную) Для коллекций, в которых количество элементов меньше 512 лучше использовать сортировку методом Шелла, нежели QuickSort (если не использовать встроенную) Для коллекций, в которых более 512 элементов продуктивнее использовать QuickSort (если не использовать встроенную) Для коллекций, в которых более 512 элементов продуктивнее использовать QuickSort (если не использовать встроенную)