Алгоритми сортування в теорії та на практиці

Сортування — одне із базових видів активності чи дій, виконуваних над предметами. Ще в дитинстві дітей вчать сортувати, розвиваючи мислення. Комп'ютери та програми теж не виняток. Існує безліч алгоритмів. Пропоную подивитися, які є та як вони працюють. Крім того, раптом вас запитають про одного з них на співбесіді?

Вступ

Сортування елементів - одна з категорій алгоритмів, до яких розробник має звикнути. Якщо колись, коли я навчався, інформатика не сприймалася так серйозно, то зараз уже в школі повинні вміти реалізовувати алгоритми сортування та розуміти їх. Базові алгоритми, найпростіші, реалізовані за допомогою циклу for. Звичайно, щоб відсортувати колекцію елементів, наприклад, масив, потрібно по цій колекції якось пройти. Наприклад:

int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
	System.out.println(array[i]);
}

Що можна сказати про цю ділянку коду? Ми маємо цикл, у якому змінюємо значення індексу ( int i) з 0 до останнього елемента у масиві. Фактично ми просто беремо кожен елемент у масиві і друкуємо його вміст. Чим більше елементів у масиві, тим довше виконуватиметься код. Тобто, якщо n — кількість елементів, при n=10 програма виконуватиметься довше, ніж за n=5, у 2 рази. Коли в нашій програмі є один цикл, час виконання зростає лінійно: що більше елементів, то довше виконання. Виходить, що алгоритм коду працює за лінійний час (n). У разі говорять, що " складність алгоритму " дорівнює O(n). Це позначення ще називають "велике" або "асимптотичне поведінка". Але можна запам'ятати просто "складність алгоритму".

Найпростіше сортування (Bubble Sort)

Отже, ми маємо масив і можемо ним ітеруватися. Чудово. Давайте спробуємо його відсортувати за зростанням. Що це означає для нас? Це означає, що маючи два елементи (наприклад, a=6, b=5), ми повинні переставити місцями a та b, якщо a більше ніж b (якщо a > b). Що для нас це означає при роботі з колекцією за індексом (як у випадку з масивом)? Це означає, якщо елемент з індексом а більше, ніж елемент з індексом b, (array[a] > array[b]), такі елементи треба поміняти місцями. Зміну місць часто називають swap. Існують різні способи зміни місць. Але ми використовуємо простий, зрозумілий код, що легко запам'ятовується:

private void swap(int[] array, int ind1, int ind2) {
    int tmp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = tmp;
}

Тепер можемо написати таке:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i-1);
	}
}
System.out.println(Arrays.toString(array));

Як бачимо, елементи дійсно помінялися місцями. Ми почали із одного елемента, т.к. якщо масив буде всього з одного елемента, вираз 1 < 1 не поверне true і тим самим ми убезпечимо себе від випадків масиву в один елемент або зовсім без них, а код буде виглядати краще. Але наш підсумковий масив не відсортовано однаково, т.к. за один прохід не вдається відсортувати всіх. Прийде додати ще цикл, в якому ми будемо виконувати проходи один за одним до тих пір, поки не отримаємо відсортований масив:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
	needIteration = false;
	for (int i = 1; i < array.length; i++) {
		if (array[i] < array[i - 1]) {
			swap(array, i, i-1);
			needIteration = true;
		}
	}
}
System.out.println(Arrays.toString(array));

Ось наше перше сортування і відпрацювало. Ми ітеруємося у зовнішньому циклі (while) До тих пір, поки не вирішимо, що ітерацій більше не потрібно. За умовчанням перед кожною новою ітерацією ми припускаємо, що наш масив відсортований, і більше не хочемо ітеруватися. Тому ми проходимо елементи послідовно і перевіряємо це припущення. Але якщо елементи не по порядку, ми виконуємо swap елементів та розуміємо, що немає впевненості, що тепер елементи у правильному порядку. Отже хочемо виконати ще одну ітерацію. Наприклад, [3, 5, 2]. 5 більше трьох, все гаразд. Але 2 менше 5. Проте [3, 2, 5] потребує ще одного проходу, т.к. 3 > 2 та його треба поміняти місцями. Оскільки ми використовуємо цикл у циклі, виходить, що складність нашого алгоритму збільшується. За n елементів вона стає n * n, тобто O(n^2). Така складність називається квадратичною. Як ми розуміємо, ми можемо точно знати, скільки знадобиться ітерацій. Показник складності алгоритму має на меті показати тенденцію зростання складності, найгірший випадок. Наскільки сильно збільшуватиметься час роботи при зміні кількості елементів n. Сортування бульбашкою - одне з найпростіших і неефективних сортувань. Її ще іноді називають "дурним сортуванням". Матеріал на тему:

• " HackerRank: Algorithms - Bubble Sort "

Сортування вибором (Selection Sort)

Інше сортування – сортування вибором. Вона також має квадратичну складність, але про це трохи згодом. Отже, ідея проста. Кожен прохід вибиратиме найменший елемент і зміщувати його на початок. При цьому кожен новий прохід починати зрушуючи праворуч, тобто перший прохід - з першого елемента, другий прохід - з другого. Виглядати це буде так:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	int minInd = left;
	for (int i = left; i < array.length; i++) {
		if (array[i] < array[minInd]) {
			minInd = i;
		}
	}
	swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));

Ця сортування нестійка, т.к. однакові елементи (з погляду тієї характеристики, якою ми сортуємо елементи) можуть змінити своє становище. Хороший приклад наведено у статті на Вікіпедії: Сортування_вибором . Матеріал на тему:

• " JavaRush : Алгоритми сортування. Сортування вибором "
• " CS50 : Selection Sort "

Сортування вставками (Insertion Sort)

Сортування вставками також має квадратичну складність, тому що у нас знову цикл у циклі. У чому на відміну від сортування вибором? Дане сортування є "стійким". Це означає, що однакові елементи змінять свій порядок. Поодинокі з погляду характеристики, за якою ми сортуємо.

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Витягуємо значення елемента
	int value = array[left];
	// Переміщаємося елементами, які перед витягнутим елементом
	int i = left - 1;
	for (; i >= 0; i--) {
		// Якщо витягли менше значення — пересуваємо більший елемент далі
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// Якщо витягнутий елемент більше - зупиняємось
			break;
		}
	}
	// У місце, що звільнилося, вставляємо витягнуте значення
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

Матеріал на тему:

• Java Insertion Sort Explained
• CS50: Insertion Sort
• CS50 на JavaRush: Insertion Sort

Човникове сортування (Shuttle Sort)

Серед простих сортувань є ще одне – човникове сортування. Але мені більше подобається шатл сорт. Мені здається, ми рідко говоримо про космічні човники, а човниковий у нас скоріше біг. Тому простіше уявити, як у космос запускаються шатли. Ось вам асоціація із цим алгоритмом. У чому полягає суть алгоритму? Суть алгоритму в тому, що ми ітеруємося ліворуч, при цьому при виконанні swap елементів ми виконуємо перевірку всіх інших елементів, які залишабося позаду, чи не потрібно повторити swap.

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i - 1);
		for (int z = i - 1; (z - 1) >= 0; z--) {
			if (array[z] < array[z - 1]) {
				swap(array, z, z - 1);
			} else {
				break;
			}
		}
	}
}
System.out.println(Arrays.toString(array));

Матеріал на тему:

• AQA Decision 1 2.02a Introducing Shuttle Sort by Jack Brown

Сортування Шелла

Ще одним простим сортуванням є сортування Шелла. Суть її схожа на сортування бульбашкою, але кожну ітерацію ми маємо різний проміжок між елементами, що порівнюються. Кожну ітерацію він зменшується вдвічі. Ось приклад реалізації:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Вираховуємо проміжок між елементами, що перевіряються.
int gap = array.length / 2;
// Поки що різниця між елементами є
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Зміщуємо правий покажчик, доки зможемо знайти такий, що
        // між ним та елементом до нього не буде потрібного проміжку
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Перераховуємо розрив
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));

Матеріал на тему:

• Shell Sort | GeeksforGeeks
• AQA Decision 1 2.03a Shell Sort - an example with 8 numbers

Сортування злиттям (merge sort)

Крім зазначених простих сортувань є сортування і складніше. Наприклад, сортування злиттям. По-перше, нам допоможе прийде рекурсія. По-друге, складність у нас буде вже не квадратична, як ми з вами звикли. Складність даного алгоритму – логарифмічна. Записується як O(n log n). Отже, зробимо це. Спочатку напишемо рекурсивний виклик методу сортування:

public static void mergeSort(int[] source, int left, int right) {
        // Виберемо роздільник, тобто. розділимо навпіл вхідний масив
        int delimiter = left + ((right - left) / 2) + 1;
        // Виконаємо рекурсивно цю функцію для двох половинок (якщо зможемо розбити (
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}

Тепер, давайте до нього додамо основну дію. Ось приклад нашого суперметоду з реалізацією:

public static void mergeSort(int[] source, int left, int right) {
        // Виберемо роздільник, тобто. розділимо навпіл вхідний масив
        int delimiter = left + ((right - left) / 2) + 1;
        // Виконаємо рекурсивно цю функцію для двох половинок (якщо зможемо розбити (
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Створюємо тимчасовий масив із потрібним розміром
        int[] buffer = new int[right - left + 1];
        // Починаючи від зазначеної лівої межі йдемо по кожному елементу
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // Ми використовуємо delimeter щоб вказувати на елемент з правої частини
            // Якщо delimeter > right, отже, у правій частині не залишилося недоданих елементів
            if (delimiter > right || source[cursor] > source[delimiter]) {
                buffer[i] = source[cursor];
                cursor++;
            } else {
                buffer[i] = source[delimiter];
                delimiter++;
            }
        }
        System.arraycopy(buffer, 0, source, left, buffer.length);
}

Запустимо приклад за допомогою виклику методуmergeSort(array, 0, array.length-1). Як видно, суть зводиться до того, що ми приймаємо на вхід масив із зазначенням початку та кінця ділянки для сортування. На початку сортування - це початок і кінець масиву. Далі ми обчислюємо delimiter - становище дільника. Якщо дільник може розділити на 2 частини, значить рекурсивно викликаємо сортування для ділянок, на які дільник розбив масив. Готуємо додатковий буферний масив, у якому виділяємо відсортовану ділянку. Далі встановлюємо курсор на початок ділянки, що сортується, і починаємо йти по кожному елементу порожнього масиву, який ми підготували, і заповнюємо його найменшими елементами. Якщо елемент, який вказує курсор менше, ніж елемент, який вказує дільник — поміщаємо в буферний масив цей елемент і зсуваємо курсор. В іншому випадку поміщаємо в буферний масив елемент, на який вказує роздільник та зрушуємо роздільник. Як тільки роздільник піде за межі ділянки, що сортується, або ми заповнимо весь масив, зазначений діапазон вважається відсортованим. Матеріал на тему:

• JavaRush: Алгоритми сортування. Сортування злиттям
• CS50: Merge Sort

Сортування підрахунком (Counting Sort) та Порозрядне сортування (Radix Sort)

Іншим цікавим алгоритмом сортування є сортування підрахунком (Counting Sort). Алгоритмічна складність у разі буде O(n+k), де n — кількість елементів, а k — максимальне значення елемента. Є з алгоритмом одна невдача: нам потрібно знати мінімальне та максимальне значення у масиві. Ось приклад реалізації сортування підрахунком:

public static int[] countingSort(int[] theArray, int maxValue) {
        // Масив із "лічильниками" розміром від 0 до максимального значення
        int numCounts[] = new int[maxValue + 1];
        // У відповідному осередку (індекс = значення) збільшуємо лічильник
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Підготовляємо масив для відсортованого результату
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // йдемо масивом з "лічильниками"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // йдемо за кількістю значень
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

Як ми розуміємо, дуже незручно, коли ми повинні знати наперед мінімальне та максимальне значення. І тут є інший алгоритм – Radix Sort. Я тут наведу алгоритм лише візуально. Реалізацію див. у матеріалах: Матеріали:

• Відео про Counting Sort

Швидке сортування Java (Quick Sort)

Ну і на солодке — один із найвідоміших алгоритмів: швидке сортування. Вона має алгоритмічну складність, тобто маємо O(n log n). Це сортування ще називають сортуванням Хоара. Цікаво, що алгоритм придумали Хоар під час його перебування в Радянському Союзі, де він навчався в Московському університеті комп'ютерного перекладу і займався розробкою російсько-англійського розмовника. А ще даний алгоритм у більш складній реалізації використовується в Arrays.sort Java. А що із Collections.sort? Пропоную подивитися самостійно, як вони сортуються "під капотом". Отже, код:

public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Рухаємо лівий маркер зліва направо поки що елемент менше, ніж pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Рухаємо правий маркер, поки елемент більше ніж pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Перевіримо, чи не потрібно обміняти місцями елементи, на які вказують маркери
            if (leftMarker <= rightMarker) {
                // Лівий маркер буде менше правого, тільки якщо ми повинні виконати swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Зрушуємо маркери, щоб отримати нові кордони
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Виконуємо рекурсивно для елементів
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}

Тут все дуже страшно, тож розбиратимемося. Для вхідного масиву int[]source виставляємо два маркери, лівий (L) та правий (R). При першому виклику вони відповідають початку та кінцю масиву. Далі визначається опорний елемент, він pivot. Після цього наше завдання — перемістити значення, менші ніж pivot, на ліву pivotчастину, а більші — на праву. Для цього спочатку рухаємо покажчик L, доки не знайдемо значення, більше ніж pivot. Якщо менше значення не знайшли, то L збігається з pivot. Потім рухаємо покажчик доки Rзнайдемо менше, ніж pivotзначення. Якщо меншого значення не знайшли, то Rзбігається з pivot. Далі, якщо вказівник Lзнаходиться до покажчика Rабо збігається з ним, то намагаємося виконати обмін елементів, якщо елемент Lменше, ніж R. Далі Lзрушуємо праворуч на 1 позицію, Rзрушуємо ліворуч на одну позицію. Коли лівий маркер Lвиявиться за правим маркером Rце означатиме, що обмін закінчено, зліва від pivotменші значення, праворуч від pivot- Великі значення. Після цього рекурсивно викликаємо таке ж сортування для ділянок масиву від початку ділянки, що сортується до правого маркера і від лівого маркера до кінця сортованої ділянки. Чому від початку до правого? Тому що наприкінці ітерації так і вийде, що правий маркер зрушить настільки, що стане межею частини зліва. Цей алгоритм складніший, ніж просте сортування, тому його краще замалювати. Візьмемо білий аркуш паперу, запишемо: 4 2 6 7 3 , а Pivotцентром, тобто. число 6. Обведемо їх у коло. Під 4 напишемо L, під 3 напишемо R. 4 менше 6, 2 менше 6. Разом, Lперемістився на становище pivot, т.к. за умовою Lне може піти далі, ніж pivot. Напишемо знову 4 2 6 7 3 , обведемо 6 навколо ( pivot) і поставимо під ним L. Тепер рухаємо покажчик R. 3 менше ніж 6, тому ставимо маркер Rцифру 3. Оскільки 3 менше, ніж pivot 6виконуємо swap, тобто. обмін. Запишемо результат: 4 2 3 7 6 обводимо 6 кругом, т.к. він як і раніше pivot. Покажчик Lна цифрі 3, покажчик Rна цифрі 6. Ми пам'ятаємо, що рухаємо покажчики доти, доки Lне зайдемо за R. Lрухаємо на наступну цифру. Тут хочеться розібрати два варіанти: якби передостання цифра була 7 і якби вона була не 7, а 1. Передостання цифра 1: Зрушабо покажчик Lцифру 1, т.к. ми можемо рухати Lдоти, доки покажчик Lвказує на цифру, меншу ніж pivot. А от Rми можемо зрушити з 6, т.к. R ми не можемо рухати тільки якщо вказівник Rвказує на цифру, яка більше ніж pivot. swapне робимо, т.к. 1 менше 6. Записуємо положення: 4 2 3 1 6, обводимо pivot 6. Lзрушується pivotі більше не рухається. Rтакож не рухається. Обмін не робимо. Зсуваємо Lі Rодну позицію і підписуємо цифру 1 маркером R, а Lвиходить поза числом. Т.к. Lпоза числом — нічого не робимо, а ось частину 4 2 3 1 виписуємо знову, т.к. це наша ліва частина, менша, ніж pivot 6. Виділяємо новий pivotі починаємо знову ) Передостання цифра 7: Зрушабо вказати Lна цифру 7, правий покажчик можемо рухати, т.к. він уже вказує на pivot. т.к. 7 більше, ніж pivot, то робимо swap. Запишемо результат: 4 2 3 6 7, обводимо 6 кружком, т.к. він pivot. Покажчик Lтепер зсувається на цифру 7, а покажчик Rзсувається на цифру 3. Частина від Lкінця немає сенсу сортувати, т.к. там лише 1 елемент, а ось частину від 4 до покажчика Rвідправляємо на сортування. Вибираємо pivotі починаємо все знову ) Може на перший погляд здатися, що якщо розставити багато однакових з pivotзначень це зламає алгоритм, але це не так. Можна вигадувати каверзних варіантів і на папірці переконатися, що все правильно і здивуватися, як такі прості дії надають такий надійний механізм. Єдиний мінус — таке сортування не є стабільним. Т.к. при виконанні обміну однакові елементи можуть змінити свій порядок, якщо один з них зустрівся до того pivot, як інший елемент потрапив у частину pivotза допомогою обміну. Матеріал:

• Фоксфорд: Алгоритми пошуку та сортування: Швидке сортування Хоара

Підсумок

Вище ми розглянули "джентльменський" набір алгоритмів сортування, реалізованих на Java. Алгоритми взагалі штука корисна як з прикладної точки зору, так і з точки зору розвитку мислення. Деякі з них простіші, деякі складніші. За якимись розумні люди захищали різні роботи на ступені, а за іншими писали товсті-товсті книги. Сподіваюся, прикладений до статті матеріал дозволить вам дізнатися ще більше, оскільки це оглядова стаття, яка і так вийшла важкою. І мета її – дати невеликий вступ. Про введення в алгоритми можна також прочитати ознайомитися з книгою " Грочаємо Алгоріми " . Також мені подобається плейлист від Jack Brown - AQA Decision 1 1.01 Tracing an Algorithm . Заради інтересу можна побачити візуалізацію алгоритмів на sorting.atі visualgo.net . Ну і весь Youtube до ваших послуг.