Nazariy va amaliyotda saralash algoritmlari

Saralash - ob'ektlar ustida bajariladigan faoliyat yoki harakatlarning asosiy turlaridan biri. Hatto bolaligida ham bolalar fikrlashni rivojlantirib, tartiblashga o'rgatiladi. Kompyuterlar va dasturlar ham bundan mustasno emas. Algoritmlarning xilma-xilligi juda katta. Men sizga ularning nima ekanligini va qanday ishlashini ko'rib chiqishni taklif qilaman. Qolaversa, bir kuni intervyuda ulardan biri haqida so'ralsa-chi?

Kirish

Elementlarni saralash - ishlab chiquvchi o'rganishi kerak bo'lgan algoritmlar toifalaridan biridir. Agar bir paytlar men o‘qib yurgan paytimda informatika faniga unchalik jiddiy e’tibor berilmagan bo‘lsa, endi maktabda ular saralash algoritmlarini amalga oshirishi va ularni tushuna olishi kerak edi. Asosiy algoritmlar, eng oddiylari, loop yordamida amalga oshiriladi for. Tabiiyki, elementlar to'plamini, masalan, massivni saralash uchun siz qandaydir tarzda ushbu to'plamni kesib o'tishingiz kerak. Masalan:

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

Ushbu kod qismi haqida nima deya olasiz? int iBizda indeks qiymatini ( ) 0 dan massivning oxirgi elementiga o'zgartiradigan tsikl mavjud . Asosan, biz oddiygina massivdagi har bir elementni olib, uning mazmunini chop etamiz. Massivdagi elementlar qancha ko'p bo'lsa, kodning bajarilishi shunchalik uzoq davom etadi. Ya'ni, agar n - elementlar soni bo'lsa, n=10 bo'lganda dastur n=5 bo'lgandan 2 marta ko'proq vaqtni oladi. Bizning dasturimiz bitta tsiklga ega bo'lsa, bajarilish vaqti chiziqli ravishda oshadi: qancha elementlar bo'lsa, bajarilish shunchalik uzoq bo'ladi. Ma’lum bo‘lishicha, yuqoridagi kod algoritmi chiziqli vaqtda (n) ishlaydi. Bunday hollarda “algoritm murakkabligi” O(n) deb aytiladi. Ushbu belgi "katta O" yoki "asimptotik xatti-harakatlar" deb ham ataladi. Ammo siz shunchaki "algoritmning murakkabligini" eslab qolishingiz mumkin.

Eng oddiy saralash (Bubble Sort)

Shunday qilib, bizda massiv bor va uni takrorlashimiz mumkin. Ajoyib. Keling, uni o'sish tartibida saralashga harakat qilaylik. Bu biz uchun nimani anglatadi? Bu shuni anglatadiki, ikkita element berilgan (masalan, a=6, b=5), agar a b dan katta bo'lsa (a > b bo'lsa) a va b ni almashtirishimiz kerak. Indeks bo'yicha to'plam bilan ishlashda bu biz uchun nimani anglatadi (massivda bo'lgani kabi)? Bu shuni anglatadiki, agar a indeksli element b indeksli elementdan katta bo'lsa, (massiv[a] > massiv[b]), bunday elementlarni almashtirish kerak. Joylarni o'zgartirish ko'pincha almashtirish deb ataladi. Joylarni almashtirishning turli usullari mavjud. Lekin biz oddiy, tushunarli va eslab qolish oson koddan foydalanamiz:

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

Endi biz quyidagilarni yozishimiz mumkin:

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));

Ko'rib turganimizdek, elementlar haqiqatan ham joylarni o'zgartirgan. Biz bitta elementdan boshladik, chunki... agar massiv faqat bitta elementdan iborat bo'lsa, 1 < 1 ifodasi haqiqatga qaytmaydi va shu bilan biz o'zimizni bitta elementli yoki umuman ularsiz massiv holatlaridan himoya qilamiz va kod yaxshiroq ko'rinadi. Lekin bizning oxirgi massivimiz baribir tartiblanmagan, chunki... Bitta o'tishda hammani saralab bo'lmaydi. Biz tartiblangan massivga ega bo'lgunimizcha ketma-ket o'tishlarni amalga oshiradigan yana bir tsiklni qo'shishimiz kerak:

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));

Shunday qilib, bizning birinchi saralashimiz ishladi. whileBoshqa takrorlash kerak emas degan qarorga kelgunimizcha, tashqi tsiklda ( ) takrorlaymiz . Odatiy bo'lib, har bir yangi iteratsiyadan oldin biz massivimiz tartiblangan deb hisoblaymiz va biz endi takrorlashni xohlamaymiz. Shuning uchun biz elementlarni ketma-ket ko'rib chiqamiz va bu taxminni tekshiramiz. Ammo agar elementlar tartibsiz bo'lsa, biz elementlarni almashtiramiz va elementlarning to'g'ri tartibda ekanligiga ishonchimiz komil emasligini tushunamiz. Shuning uchun biz yana bir iteratsiya qilishni xohlaymiz. Masalan, [3, 5, 2]. 5 - uchtadan ko'p, hamma narsa yaxshi. Lekin 2 5 dan kichik. Biroq, [3, 2, 5] yana bitta o'tishni talab qiladi, chunki 3 > 2 va ularni almashtirish kerak. Biz halqa ichida tsikldan foydalanganimiz sababli, algoritmimizning murakkabligi oshadi. n ta element bilan u n * n ga aylanadi, ya'ni O(n^2). Bu murakkablik kvadratik deb ataladi. Biz tushunganimizdek, qancha takrorlash kerakligini aniq bila olmaymiz. Algoritmning murakkabligi ko'rsatkichi murakkablikning kuchayishi tendentsiyasini, eng yomon holatni ko'rsatish maqsadiga xizmat qiladi. Elementlar soni n o'zgarganda ish vaqti qanchaga oshadi. Bubble sort - eng oddiy va samarasiz turlardan biridir. Buni ba'zan "ahmoq saralash" deb ham atashadi. Tegishli materiallar:

• " HackerRank: Algoritmlar - Bubble Sort "

Tanlash saralash

Yana bir tur - tanlov turi. Bundan tashqari, kvadratik murakkablik bor, lekin bu haqda keyinroq. Shunday qilib, fikr oddiy. Har bir o'tish eng kichik elementni tanlaydi va uni boshiga o'tkazadi. Bunday holda, har bir yangi o'tishni o'ngga siljitish orqali boshlang, ya'ni birinchi o'tish - birinchi elementdan, ikkinchi o'tish - ikkinchidan. Bu shunday ko'rinadi:

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));

Bu saralash beqaror, chunki bir xil elementlar (biz elementlarni saralaydigan xarakteristikasi nuqtai nazaridan) o'z o'rnini o'zgartirishi mumkin. Yaxshi misol Vikipediya maqolasida keltirilgan: Saralash_bo'yicha tanlash . Tegishli materiallar:

• " JavaRush: Saralash algoritmlari. Tanlash tartibi "
• " CS50: Tanlovni saralash "

Kiritish tartibi

Qo'shish tartibi ham kvadratik murakkablikka ega, chunki bizda yana tsikl ichida halqa mavjud. U tanlovdan qanday farq qiladi? Ushbu saralash "barqaror". Bu shuni anglatadiki, bir xil elementlar o'z tartibini o'zgartirmaydi. Biz saralaydigan xususiyatlar jihatidan bir xil.

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Retrieve the value of the element
	int value = array[left];
	// Move through the elements that are before the pulled element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If a smaller value is pulled out, move the larger element further
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the pulled element is larger, stop
			break;
		}
	}
	// Insert the extracted value into the freed space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

Tegishli materiallar:

• Java qo'shish tartibi tushuntirildi
• CS50: Qo'shishni saralash
• JavaRush-da CS50: qo'shishni tartiblash

Shuttle Saralash

Oddiy turlar orasida yana biri bor - shattle saralash. Lekin men shuttle turini afzal ko'raman. Menimcha, biz kosmik kemalar haqida kamdan-kam gapiramiz va bu ko'proq yugurishdir. Shu sababli, kosmosga mokilar qanday uchirilishini tasavvur qilish osonroq. Mana bu algoritm bilan bog'lanish. Algoritmning mohiyati nimada? Algoritmning mohiyati shundan iboratki, biz chapdan o'ngga takrorlaymiz va elementlarni almashtirganda, biz almashtirishni takrorlash kerakmi yoki yo'qligini bilish uchun orqada qolgan barcha boshqa elementlarni tekshiramiz.

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));

Tegishli materiallar:

• AQA qarori 1 2.02a Jek Braun tomonidan Shuttle Sortni joriy etish

Shell tartiblash

Yana bir oddiy tur - Shell sort. Uning mohiyati pufakchali saralashga o'xshaydi, lekin har bir iteratsiya bizda solishtirilayotgan elementlar o'rtasida har xil bo'shliq mavjud. Har bir takrorlashda u ikki baravar kamayadi. Mana bir misol amalga oshirish:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a difference between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right pointer until we can find one that
        // there won't be enough space between it and the element before it
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Recalculate the gap
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));

Tegishli materiallar:

• Shell Sort | GeeksforGeeks
• AQA Decision 1 2.03a Shell Sort - 8 ta raqamdan iborat misol

Birlashtirish tartibi

Ko'rsatilgan oddiy turlarga qo'shimcha ravishda, yanada murakkab turlar mavjud. Misol uchun, birlashtirish tartibi. Birinchidan, rekursiya yordamimizga keladi. Ikkinchidan, bizning murakkabligimiz endi biz o'rganib qolganimizdek kvadratik bo'lmaydi. Ushbu algoritmning murakkabligi logarifmikdir. O(n log n) shaklida yozilgan. Shunday qilib, keling, buni qilaylik. Birinchidan, tartiblash usuliga rekursiv chaqiruv yozamiz:

public static void mergeSort(int[] source, int left, int right) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}

Endi unga asosiy harakatni qo'shamiz. Amalga oshirish bilan bizning supermetodimizga misol:

public static void mergeSort(int[] source, int left, int right) {
        // Choose a separator, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Execute this function recursively for the two halves (if we can split(
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the desired size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left border, go through each element
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use the delimeter to point to the element from the right side
            // If delimeter > right, then there are no unadded elements left on the right side
            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);
}

ni chaqirish orqali misolni ishga tushiramiz mergeSort(array, 0, array.length-1). Ko'rib turganingizdek, mohiyat shundan iboratki, biz kirish sifatida saralanadigan bo'limning boshi va oxirini ko'rsatadigan massivni olamiz. Saralash boshlanganda, bu massivning boshi va oxiri. Keyinchalik biz ajratuvchini hisoblaymiz - bo'linuvchining holati. Agar bo'luvchi 2 qismga bo'linishi mumkin bo'lsa, u holda bo'luvchi massivni ajratgan bo'limlar uchun rekursiv tartiblash deb ataladi. Biz qo'shimcha bufer massivini tayyorlaymiz, unda biz tartiblangan qismni tanlaymiz. Keyinchalik, kursorni tartiblanadigan maydonning boshiga qo'yamiz va biz tayyorlagan bo'sh massivning har bir elementidan o'tishni boshlaymiz va uni eng kichik elementlar bilan to'ldiramiz. Kursor ko'rsatgan element bo'linuvchi ko'rsatgan elementdan kichikroq bo'lsa, biz bu elementni bufer massiviga joylashtiramiz va kursorni siljitamiz. Aks holda, ajratuvchi ko'rsatgan elementni bufer massiviga joylashtiramiz va ajratgichni harakatlantiramiz. Ajratuvchi tartiblangan maydon chegarasidan tashqariga chiqishi yoki biz butun massivni to'ldirishimiz bilan ko'rsatilgan diapazon tartiblangan hisoblanadi. Tegishli materiallar:

• JavaRush: Saralash algoritmlari. Birlashtirish tartibi
• CS50: Birlashtirish saralash

Hisoblash va Radix Saralash

Saralashning yana bir qiziqarli algoritmi - tartiblash sanash. Bu holda algoritmik murakkablik O(n+k) bo'ladi, bu erda n - elementlar soni, k - elementning maksimal qiymati. Algoritmda bitta muammo bor: biz massivdagi minimal va maksimal qiymatlarni bilishimiz kerak. Hisoblash tartibini amalga oshirish misoli:

public static int[] countingSort(int[] theArray, int maxValue) {
        // Array with "counters" ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // In the corresponding cell (index = value) we increase the counter
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Prepare array for sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // go through the array with "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // go by the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

Biz tushunganimizdek, minimal va maksimal qiymatlarni oldindan bilishimiz kerak bo'lsa, bu juda noqulay. Va keyin yana bir algoritm bor - Radix Sort. Men bu erda algoritmni faqat vizual tarzda taqdim etaman. Amalga oshirish uchun materiallarga qarang: Materiallar:

• Sanoqni tartiblash haqida video

Java tez tartiblash

Xo'sh, shirinlik uchun - eng mashhur algoritmlardan biri: tez tartiblash. U algoritmik murakkablikka ega, ya'ni bizda O(n log n) mavjud. Bu turga Hoare navi ham deyiladi. Qizig‘i shundaki, algoritmni Xoar Sovet Ittifoqida bo‘lganida ixtiro qilgan, u Moskva universitetida kompyuter tarjimasi bo‘yicha tahsil olgan va ruscha-inglizcha so‘zlashuv kitobini ishlab chiqqan. Ushbu algoritm Java-dagi Arrays.sort-da murakkabroq amalga oshirishda ham qo'llaniladi. Collections.sort haqida nima deyish mumkin? Men sizni "kaput ostida" qanday tartiblanganligini o'zingiz ko'rishni taklif qilaman. Shunday qilib, kod:

public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Move the left marker from left to right while element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker until element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check if you don't need to swap elements pointed to by markers
            if (leftMarker <= rightMarker) {
                // The left marker will only be less than the right marker if we have to swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Move markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Execute recursively for parts
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}

Bu erda hamma narsa juda qo'rqinchli, shuning uchun biz buni aniqlaymiz. Kirish massivi int[]manbai uchun biz ikkita markerni o'rnatamiz, chap (L) va o'ng (R). Birinchi marta chaqirilganda ular massivning boshi va oxiriga mos keladi. Keyinchalik, qo'llab-quvvatlovchi element aniqlanadi, aka pivot. pivotShundan so'ng, bizning vazifamiz dan kichikroq qiymatlarni chapga pivotva kattaroqlarni o'ngga siljitishdir . Buni amalga oshirish uchun avval ko'rsatgichni Ldan kattaroq qiymat topgunimizcha harakatlantiring pivot. Agar kichikroq qiymat topilmasa, u holda L совпадёт с pivot. Потом двигаем указатель R пока не найдём меньшее, чем pivot meaning. Если меньшее meaning не нашли, то R совпадёт с pivot. Далее, если указатель L находится до указателя R or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент L меньше, чем R. Далее L сдвигаем вправо на 1 позицию, R сдвигаем влево на одну позицию. Когда левый маркер L окажется за правым маркером R это будет означать, что обмен закончен, слева от pivot меньшие значения, справа от pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем L, под 3 напишем R. 4 меньше чем 6, 2 меньше чем 6. Total, L переместился на положение pivot, т.к. по условию L не может уйти дальше, чем pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг ( pivot) и поставим под ним L. Теперь двигаем указатель R. 3 меньше чем 6, поэтому ставим маркер R на цифру 3. Так How 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 значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до pivot до того, How другой элемент попал в часть до pivot при помощи обмена. Материал:

• Фоксфорд: Алгоритмы поиска и сортировки: Быстрая sorting Хоара

Итог

Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой " Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown — AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на sorting.at и visualgo.net. Ну и весь Youtube к вашим услугам.