Theory and Tasks for Students - Spring 2019
Сортировки - Шейкер, Вставками, Выбором

Сортировка "Шейкером" (Cocktail Shaker Sort)

Эта сортировка является небольшой модификацией "Пузырька" - каждый второй проход производится справа налево. Исходя из этого легко написать следующий код:

bool flag; int c; do { flag = false; for (int i = 0; i < arr.Length - 1; i++) { if (arr[i] > arr[i + 1]) { c = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = c; flag = true; } } if (!flag) { break; } for (int i = arr.Length - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { c = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = c; flag = true; } } } while (flag);

В такой реализации, однако, проверяются элементы, которые уже стоят на правильном месте, т.к. нет переменной, отвечающей за размер отсортированной части. Кроме того, можно применить ту же оптимизацию по индексу последней перестановки, как и в Улучшенном "Пузырьке": int[] arr = new int[10]; int left = 0, curLeft; int right = arr.Length - 1, curRight; int c; do { curRight = left; for (int i = left; i < right; i++) { if (arr[i] > arr[i + 1]) { c = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = c; curRight = i; } } right = curRight; if (left >= right) { break; } curLeft = right; for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) { c = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = c; curLeft = i; } } left = curLeft; } while (left < right);

Сортировка Вставками (Insertion Sort)

В этом простом алгоритме очередной элемент массива сдвигается как можно левее путём перестановок.

int j; int c; for (int i = 1; i < arr.Length; i++) { j = i; while ((j > 0) && (arr[j] < arr[j - 1])) { c = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = c; j--; } }

В такой реализации производится слишком много перестановок, что может сказаться на эффективности алгоритма при использовании на структурах данных, отличных от массива, однако это можно оптимизировать следующим образом: int j; int c; for (int i = 1; i < arr.Length; i++) { j = i; c = arr[j]; while ((j > 0) && (c < arr[j - 1])) { arr[j] = arr[j - 1]; j--; } arr[j] = c; }

Сортировка Выбором (Selection Sort)

В неотсортированной части массива ищется минимальный элемент и меняется местами с первым элементом этой части.

int t, c; for (int i = 0; i < arr.Length - 1; i++) { t = i; // индекс минимального элемента for (int j = i + 1; j < arr.Length; j++) { if (arr[j] < arr[t]) { t = j; } } c = arr[i]; arr[i] = arr[t]; arr[t] = c; }