Çeşidləmə obyektlər üzərində həyata keçirilən fəaliyyətlərin və ya hərəkətlərin əsas növlərindən biridir. Hətta uşaqlıqda uşaqlara düşüncələrini inkişaf etdirərək çeşidləməyə öyrədilir. Kompüterlər və proqramlar da istisna deyil. Çox sayda alqoritm var. Onların nə olduğunu və necə işlədiklərini nəzərdən keçirməyi təklif edirəm. Üstəlik, bir gün müsahibədə bunlardan biri haqqında soruşsanız nə olacaq?
Giriş
Elementlərin çeşidlənməsi, tərtibatçının öyrəşməli olduğu alqoritmlərin kateqoriyalarından biridir. Əgər bir vaxtlar mən oxuyanda informatika elminə bu qədər ciddi yanaşılmırdısa, indi məktəbdə çeşidləmə alqoritmlərini həyata keçirməyi, onları başa düşməyi bacarmalıdırlar. Əsas alqoritmlər, ən sadələri, bir döngə istifadə edərək həyata keçirilir for. Təbii ki, elementlər toplusunu, məsələn, massivi çeşidləmək üçün bu kolleksiyadan hansısa şəkildə keçmək lazımdır. Misal üçün:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Bu kod parçası haqqında nə deyə bilərsiniz? int iBizdə indeks dəyərini ( ) 0-dan massivin sonuncu elementinə dəyişdiyimiz bir döngə var . Əslində, biz sadəcə massivdəki hər bir elementi götürüb onun məzmununu çap edirik. Massivdə nə qədər çox element varsa, kodun icrası bir o qədər çox vaxt aparacaq. Yəni, əgər n elementlərin sayıdırsa, n=10 olduqda proqramın icrası n=5 ilə müqayisədə 2 dəfə çox çəkəcək. Proqramımızın bir döngəsi olduqda, icra müddəti xətti olaraq artır: nə qədər çox element varsa, icra müddəti bir o qədər uzun olur. Belə çıxır ki, yuxarıdakı kodun alqoritmi xətti zamanda (n) işləyir. Belə hallarda “alqoritmin mürəkkəbliyi” O(n) kimi deyilir. Bu qeyd "böyük O" və ya "asimptotik davranış" adlanır. Ancaq sadəcə olaraq "alqoritmin mürəkkəbliyini" xatırlaya bilərsiniz.
Ən sadə çeşidləmə (Bubble Sort)
Beləliklə, bir massivimiz var və onu təkrarlaya bilərik. Əla. İndi onu artan qaydada sıralamağa çalışaq. Bu bizim üçün nə deməkdir? Bu o deməkdir ki, iki element (məsələn, a=6, b=5) verildikdə, a b-dən böyükdürsə (a > b) a və b-ni dəyişdirməliyik. İndeks üzrə kolleksiya ilə işləyərkən (massivdə olduğu kimi) bu bizim üçün nə deməkdir? Bu o deməkdir ki, a indeksli element b indeksli elementdən böyükdürsə, (massiv[a] > massiv[b]), belə elementlər dəyişdirilməlidir. Yerlərin dəyişdirilməsi çox vaxt dəyişdirmə adlanır. Yerləri dəyişdirməyin müxtəlif yolları var. Lakin biz sadə, aydın və yadda qalan koddan istifadə edirik:
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));
Gördüyümüz kimi, elementlər həqiqətən də yerlərini dəyişiblər. Biz bir elementlə başladıq, çünki... əgər massiv yalnız bir elementdən ibarətdirsə, 1 < 1 ifadəsi doğru qayıtmayacaq və beləliklə, biz özümüzü bir elementli və ya onlarsız massiv hallarından qoruyacağıq və kod daha yaxşı görünəcək. Ancaq son massivimiz hər halda çeşidlənməyib, çünki... Hamını bir keçiddə sıralamaq mümkün deyil. Sıralanmış massiv əldə edənə qədər keçidləri bir-bir yerinə yetirəcəyimiz başqa bir döngə əlavə etməli olacağıq:
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));
Beləliklə, ilk çeşidləməmiz nəticə verdi. whileArtıq təkrarlamalara ehtiyac olmadığına qərar verənə qədər xarici döngədə ( ) təkrar edirik . Varsayılan olaraq, hər yeni iterasiyadan əvvəl massivimizin çeşidləndiyini güman edirik və daha çox təkrarlamaq istəmirik. Buna görə də, elementləri ardıcıl olaraq keçir və bu fərziyyəni yoxlayırıq. Amma elementlər sıradan çıxıbsa, biz elementləri dəyişdiririk və elementlərin indi düzgün qaydada olduğuna əmin olmadığımızı başa düşürük. Buna görə də biz daha bir iterasiya etmək istəyirik. Məsələn, [3, 5, 2]. 5 üçdən çoxdur, hər şey yaxşıdır. Lakin 2 5-dən azdır. Bununla belə, [3, 2, 5] daha bir keçid tələb edir, çünki 3 > 2 və onlar dəyişdirilməlidir. Döngə içərisində bir döngə istifadə etdiyimiz üçün, alqoritmimizin mürəkkəbliyinin artdığı ortaya çıxır. n elementlə n * n olur, yəni O(n^2). Bu mürəkkəblik kvadrat adlanır. Anladığımız kimi, nə qədər təkrarlama lazım olacağını dəqiq bilə bilmərik. Alqoritmin mürəkkəbliyi göstəricisi artan mürəkkəblik meylini, ən pis halda göstərmək məqsədinə xidmət edir. Elementlərin sayı n dəyişdikdə işləmə müddəti nə qədər artacaq. Bubble sort ən sadə və ən səmərəsiz növlərdən biridir. Buna bəzən “axmaq çeşidləmə” də deyirlər. Əlaqədar material:
Başqa bir növ seçim çeşididir. O, həmçinin kvadratik mürəkkəbliyə malikdir, lakin bu barədə daha sonra. Beləliklə, fikir sadədir. Hər keçid ən kiçik elementi seçir və onu başlanğıca aparır. Bu halda, hər bir yeni keçidə sağa doğru hərəkət edərək başlayın, yəni birinci keçid - birinci elementdən, ikinci keçid - ikincidən. Bu belə görünəcək:
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 çeşidləmə qeyri-sabitdir, çünki eyni elementlər (elementləri çeşidlədiyimiz xüsusiyyət nöqteyi-nəzərindən) öz mövqeyini dəyişə bilər. Yaxşı bir nümunə Vikipediya məqaləsində verilmişdir: Sorting_by-section . Əlaqədar material:
Daxiletmə çeşidi də kvadratik mürəkkəbliyə malikdir, çünki bizdə yenə bir döngə içərisində bir döngə var. Seçim növündən nə ilə fərqlənir? Bu çeşidləmə "sabitdir". Bu o deməkdir ki, eyni elementlər öz sırasını dəyişməyəcək. Sıraladığımız xüsusiyyətlərə görə eynidir.
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 elementint value = array[left];// Move through the elements that are before the pulled elementint i = left -1;for(; i >=0; i--){// If a smaller value is pulled out, move the larger element furtherif(value < array[i]){
array[i +1]= array[i];}else{// If the pulled element is larger, stopbreak;}}// Insert the extracted value into the freed space
array[i +1]= value;}System.out.println(Arrays.toString(array));
Sadə növlər arasında başqa biri də var - servis çeşidləmə. Amma mən servis çeşidinə üstünlük verirəm. Mənə elə gəlir ki, biz kosmik gəmilərdən çox az danışırıq və mekik daha çox qaçışdır. Buna görə də kosmosa şatlların necə buraxıldığını təsəvvür etmək daha asandır. Bu alqoritmlə əlaqə var. Alqoritmin mahiyyəti nədir? Alqoritmin mahiyyəti ondan ibarətdir ki, biz soldan sağa təkrar edirik və elementləri dəyişdirərkən geridə qalan bütün digər elementləri yoxlayırıq ki, dəyişdirmənin təkrarlanmasına ehtiyac varmı.
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));
Başqa bir sadə növ Shell çeşididir. Onun mahiyyəti qabarcıq sıralamasına bənzəyir, lakin hər iterasiyada müqayisə olunan elementlər arasında fərqli boşluq var. Hər iterasiya yarıya endirilir. Budur bir tətbiq nümunəsi:
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));// Calculate the gap between the checked elementsint gap = array.length /2;// As long as there is a difference between the elementswhile(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 itfor(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));
Göstərilən sadə növlərə əlavə olaraq, daha mürəkkəb növlər var. Məsələn, birləşmə çeşidi. Birincisi, rekursiya köməyimizə gələcək. İkincisi, bizim mürəkkəbliyimiz artıq adət etdiyimiz kimi kvadratik olmayacaq. Bu alqoritmin mürəkkəbliyi loqarifmikdir. O(n log n) kimi yazılmışdır. Beləliklə, bunu edək. Əvvəlcə çeşidləmə metoduna rekursiv çağırış yazaq:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint 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);}}
İndi ona əsas hərəkəti əlavə edək. Tətbiqlə supermetodumuzun bir nümunəsidir:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint 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 sizeint[] buffer =newint[right - left +1];// Starting from the specified left border, go through each elementint 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 sideif(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);}
Nümunəni çağıraraq işə salaq mergeSort(array, 0, array.length-1). Göründüyü kimi, mahiyyət ondan ibarətdir ki, biz giriş kimi çeşidlənəcək bölmənin başlanğıcını və sonunu göstərən massiv götürürük. Çeşidləmə başlayanda bu, massivin başlanğıcı və sonu olur. Sonra ayırıcı hesablayırıq - bölücü mövqeyi. Əgər bölücü 2 hissəyə bölünə bilirsə, o zaman bölücünün massivi böldüyü bölmələr üçün rekursiv çeşidləmə deyirik. Sıralanmış bölməni seçdiyimiz əlavə bufer massivi hazırlayırıq. Sonra kursoru çeşidlənəcək sahənin əvvəlinə qoyuruq və hazırladığımız boş massivin hər bir elementindən keçib ən kiçik elementlərlə doldurmağa başlayırıq. Əgər kursorun göstərdiyi element bölücünün göstərdiyi elementdən kiçikdirsə, bu elementi bufer massivinə yerləşdiririk və kursoru hərəkət etdiririk. Əks halda, ayırıcının göstərdiyi elementi bufer massivinə yerləşdiririk və ayırıcını hərəkət etdiririk. Ayırıcı çeşidlənmiş sahənin hüdudlarından kənara çıxanda və ya bütün massivi dolduran kimi, göstərilən diapazon çeşidlənmiş sayılır. Əlaqədar material:
Başqa bir maraqlı çeşidləmə alqoritmi sayma çeşididir. Bu halda alqoritmik mürəkkəblik O(n+k) olacaq, burada n elementlərin sayı, k isə elementin maksimum qiymətidir. Alqoritmdə bir problem var: massivdəki minimum və maksimum dəyərləri bilməliyik. Budur, sayma növünün tətbiqi nümunəsi:
publicstaticint[]countingSort(int[] theArray,int maxValue){// Array with "counters" ranging from 0 to the maximum valueint numCounts[]=newint[maxValue +1];// In the corresponding cell (index = value) we increase the counterfor(int num : theArray){
numCounts[num]++;}// Prepare array for sorted resultint[] sortedArray =newint[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 valuesfor(int k =0; k < count; k++){
sortedArray[currentSortedIndex]= n;
currentSortedIndex++;}}return sortedArray;}
Anladığımız kimi, minimum və maksimum dəyərləri əvvəlcədən bilməli olduğumuz zaman çox əlverişsizdir. Və sonra başqa bir alqoritm var - Radix Sort. Alqoritmi burada ancaq vizual olaraq təqdim edəcəm. İcra üçün materiallara baxın:
Yaxşı, desert üçün - ən məşhur alqoritmlərdən biri: sürətli çeşidləmə. Onun alqoritmik mürəkkəbliyi var, yəni bizdə O(n log n) var. Bu növə Hoare sort da deyilir. Maraqlıdır ki, alqoritmi Hoare Sovet İttifaqında olarkən icad edib, o, Moskva Universitetində kompüter tərcüməsi üzrə təhsil alıb və rus-ingilis dillərində danışıq kitabçası hazırlayırdı. Bu alqoritm Java-da Arrays.sort-da daha mürəkkəb icrada da istifadə olunur. Collections.sort haqqında nə demək olar? Onların "başlıq altında" necə çeşidləndiyini özünüz görmənizi təklif edirəm. Beləliklə, kod:
publicstaticvoidquickSort(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 pivotwhile(source[leftMarker]< pivot){
leftMarker++;}// Move the right marker until element is greater than pivotwhile(source[rightMarker]> pivot){
rightMarker--;}// Check if you don't need to swap elements pointed to by markersif(leftMarker <= rightMarker){// The left marker will only be less than the right marker if we have to swapif(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 partsif(leftMarker < rightBorder){quickSort(source, leftMarker, rightBorder);}if(leftBorder < rightMarker){quickSort(source, leftBorder, rightMarker);}}
Burada hər şey çox qorxuludur, ona görə də bunu anlayacağıq. Giriş massivinin int[]mənbəyi üçün iki marker təyin etdik, sol (L) və sağ (R). İlk dəfə çağırılanda onlar massivin əvvəli və sonuna uyğun gəlir. Sonra, dəstəkləyici element müəyyən edilir, aka pivot. pivotBundan sonra bizim vəzifəmiz dəyərləri -dən kiçik , sola pivot, böyükləri isə sağa köçürməkdir . LBunu etmək üçün əvvəlcə -dən böyük bir dəyər tapana qədər göstəricini hərəkət etdirin pivot. Daha kiçik bir dəyər tapılmırsa, o zaman
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 при помощи обмена. Материал:
Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой "
Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown —
AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на
sorting.at и
visualgo.net. Ну и весь Youtube к вашим услугам.
GO TO FULL VERSION