Алгоритмы сортировки

В общем виде задачу сортировки можно сформулировать следующим образом: Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого(ключ сортировки). Тип данных ключа должен включать операции сравнения.

Требуется преобразовать исходную последовательность в последовательность содержащую те же записи, но в порядке возрастания или убывания значения ключа.

Существует 2 типа сортировки

1. Внутренняя сортировка, в которой предполагается, что данные находятся в памяти и важно оптимизировать число действий программы. Она делится на универсальные и специальные методы. Специальные делятся на подсчетные и поразрядное. Универсальные делятся на простые и улучшенные. Простые: сортировка обмена, вставки и выбора. Улучшенные: Шелл, пирамид, быстрые
2. Внешняя, в которой данные хранятся на внешнем устройстве с более медленном доступе и прежде всего надо снизить число обращений к этому устройству.

Метод подсчета

Этот метод подразумевает, что все данные, которые мы хотим отсортировать, являются целыми числами в диапазоне от 0 до k. Основная идея состоит в том, чтобы для каждого числа x определить, сколько чисел меньше x. Зная это, мы можем поместить число x на правильное место в отсортированном списке.

Вот пример кода на C++:

void countSort(int* arr, int n) {
	int min = arr[0], max = arr[0];
	for(int i = 1; i < n; i++) {
        if(arr[i] < min) min = arr[i];
        if(arr[i] > max) max = arr[i];
    }

    int range = max - min + 1;
    int* countArr = new int[n];
    for(int i = 0; i < n; i++) {
	    countArr[arr[i] - min]++;
    }
    for(int i = 1; i < range; i++) {
	    countArr[i] += countArr[i - 1];
    }

    int* sortedArr = new int[n];
    for(int i = n - 1; i >= 0; i--) {
	    int pos = countArr[arr[i] - min] - 1;
	    sortedArr[pos] = arr[i];
	    countArr[arr[i] - min]--;
    }

    for(int i = 0; i < n; i++) arr[i] = sortedArr[i];
}

Метод прямого включения (вставки)

При этом методе мы делим список на две части: отсортированную и неотсортированную. В начале отсортированной частью считается только первый элемент. Затем мы берем следующий элемент из неотсортированной части и вставляем его на правильное место в отсортированной части.

Вот пример кода на C++:

void insertionSort(int* arr, int n) {
	for(int i = 1; i < n; i++) {
		int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[i] > key) {
	        arr[j + 1] = arr[j];
	        j--;
        }

        arr[j + 1] = key;
    }
}

Максимальное количество сравнений ключей с i при i-ом проходе равно i - 1. Если предположить, что все перестановки из n элементов равновероятны, то среднее число сравнений равно i/2. Число перестановок M(i) = C(i) + 2. Этот алгоритм работает лучше всего, когда исходный список уже отсортирован, и хуже всего, когда элементы расположены в обратном порядке.

Метод прямого выбора

Этот метод сортировки работает так: мы делим массив на две части - отсортированную и неотсортированную. В начале считаем, что отсортированная часть пуста, а все элементы массива находятся в неотсортированной части. Затем мы ищем наименьший элемент в неотсортированной части и перемещаем его в конец отсортированной части. Этот процесс повторяется, пока весь массив не будет отсортирован.

void selectionSort(int* arr, int n) {
	for(int i = 0; i < n – 1; i++) {
		int minIndex = i;
		for(int j = i + 1; j < n ; i++) {
			if(arr[j] < arr[minIndex]) minIndex = j;
        }
swap(arr[i], arr[minIndex]);
    }
}

Пузырьковая сортировка

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

void bubbleSort(int* arr, int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Оба этих метода имеют свои преимущества и недостатки. Метод прямого выбора обычно работает быстрее, если элементы в начале массива уже почти отсортированы. Пузырьковая сортировка, с другой стороны, может быть более эффективной для больших массивов, но она может быть медленной, если массив изначально почти отсортирован. Если на каком-то проходе не произошло ни одного обмена, это означает, что список уже отсортирован, и алгоритм может быть завершен раньше времени. Это свойство делает пузырьковую сортировку идеальной для списков, которые уже почти отсортированы.

Шейкерная сортировка

Шейкерная сортировка(сортировка перемещиванием) – Алгоритм сортировки, которая улучшает сортировку пузырьком, проходя по массиву в обоих направлениях. Это позволяет уменьшить количество проходов, необходимых для полной сортировки массива. На каждом проходе справа налево минимальный элемент всплывает на первую позицию, а на проходе слева направо максимальный элемент тонет на последнюю позицию. Процесс повторяется, пока границы рабочей части массива не сойдутся. Число сравнений пузырька = (n^2 – n) / 2 . Шейкерная сортировка лучше пузырьковой за счет того, что шейкерная сортировка проходит с двух сторон, а пузырьковая только с одной стороны

void shakerSort(int* arr, int size) {
    int left = 0, right = size - 1;
    bool swapped = false;
    
    while(left < right) {
        for(int i = left; i < right; i++) {
            if(arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }    
        }
        
    right--;
    
    for(int i = right; i > left; i--) {
            if(arr[i] < arr[i - 1]) {
                swap(arr[i], arr[i - 1]);
                swapped = true;
            }
        }
        
left++;

if(!swapped) break;

swapped = false;
    }
}