Ang pag-uuri ay isa sa mga pangunahing uri ng aktibidad o aksyon na ginagawa sa mga bagay. Kahit na sa pagkabata, ang mga bata ay tinuturuan na mag-uri-uriin, bumuo ng kanilang pag-iisip. Ang mga computer at program ay hindi rin eksepsiyon. Mayroong isang malaking iba't ibang mga algorithm. Iminumungkahi kong tingnan mo kung ano ang mga ito at kung paano gumagana ang mga ito. Dagdag pa, paano kung isang araw ay tanungin ka tungkol sa isa sa mga ito sa isang panayam?
Panimula
Ang pag-uuri ng mga elemento ay isa sa mga kategorya ng mga algorithm na dapat masanay ng isang developer. Kung noong unang panahon, noong nag-aaral ako, hindi masyadong sineseryoso ang computer science, ngayon sa paaralan ay dapat na nilang ipatupad ang mga algorithm ng pag-uuri at maunawaan ang mga ito. Ang mga pangunahing algorithm, ang pinakasimpleng, ay ipinatupad gamit ang isang loop for. Naturally, upang pag-uri-uriin ang isang koleksyon ng mga elemento, halimbawa, isang array, kailangan mong daanan ang koleksyon na ito kahit papaano. Halimbawa:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Ano ang masasabi mo tungkol sa piraso ng code na ito? Mayroon kaming loop kung saan binabago namin ang index value ( int i) mula 0 hanggang sa huling elemento sa array. Sa katunayan, kinuha lang namin ang bawat elemento sa array at i-print ang mga nilalaman nito. Ang mas maraming elemento sa array, mas matagal ang code na aabutin upang maisakatuparan. Iyon ay, kung ang n ay ang bilang ng mga elemento, na may n=10 ang programa ay tatagal ng 2 beses na mas matagal upang maisagawa kaysa sa n=5. Kapag ang aming programa ay may isang loop, ang execution time ay tumataas nang linearly: mas maraming elemento, mas mahaba ang execution. Lumalabas na ang algorithm ng code sa itaas ay gumagana sa linear time (n). Sa ganitong mga kaso, ang "algorithm complexity" ay sinasabing O(n). Ang notasyong ito ay tinatawag ding "big O" o "asymptotic behavior". Ngunit maaari mo lamang tandaan "ang pagiging kumplikado ng algorithm."
Ang pinakasimpleng pag-uuri (Bubble Sort)
Kaya, mayroon kaming isang array at maaaring umulit dito. Malaki. Subukan nating ayusin ito sa pataas na pagkakasunud-sunod. Ano ang ibig sabihin nito para sa atin? Nangangahulugan ito na binigyan ng dalawang elemento (halimbawa, a=6, b=5), dapat nating palitan ang a at b kung ang a ay mas malaki kaysa sa b (kung a > b). Ano ang ibig sabihin nito para sa amin kapag nagtatrabaho sa isang koleksyon sa pamamagitan ng index (tulad ng kaso sa isang array)? Nangangahulugan ito na kung ang elementong may index a ay mas malaki kaysa sa elementong may index b, (array[a] > array[b]), dapat na palitan ang mga naturang elemento. Ang pagpapalit ng mga lugar ay madalas na tinatawag na swap. Mayroong iba't ibang mga paraan upang baguhin ang mga lugar. Ngunit gumagamit kami ng simple, malinaw at madaling tandaan na code:
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));
Tulad ng nakikita natin, ang mga elemento ay talagang nagbago ng mga lugar. Nagsimula kami sa isang elemento, dahil... kung ang array ay binubuo lamang ng isang elemento, ang expression na 1 < 1 ay hindi babalik ng totoo at sa gayon ay mapoprotektahan natin ang ating sarili mula sa mga kaso ng array na may isang elemento o wala man lang, at magiging mas maganda ang code. Ngunit ang aming huling hanay ay hindi pa rin nakaayos, dahil... Hindi posibleng pag-uri-uriin ang lahat sa isang pass. Kakailanganin nating magdagdag ng isa pang loop kung saan magsasagawa tayo ng mga pass nang paisa-isa hanggang sa makakuha tayo ng pinagsunod-sunod na array:
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));
Kaya ang aming unang pag-uuri ay gumana. Umuulit kami sa panlabas na loop ( while) hanggang sa mapagpasyahan namin na wala nang mga pag-ulit ang kailangan. Bilang default, bago ang bawat bagong pag-ulit, ipinapalagay namin na ang aming array ay pinagsunod-sunod, at hindi na namin gustong umulit. Samakatuwid, dumaan tayo sa mga elemento nang sunud-sunod at suriin ang pagpapalagay na ito. Ngunit kung ang mga elemento ay wala sa ayos, ipinagpapalit natin ang mga elemento at napagtanto na hindi tayo sigurado na ang mga elemento ay nasa tamang pagkakasunud-sunod na ngayon. Samakatuwid, gusto naming magsagawa ng isa pang pag-ulit. Halimbawa, [3, 5, 2]. Ang 5 ay higit sa tatlo, lahat ay maayos. Ngunit ang 2 ay mas mababa sa 5. Gayunpaman, [3, 2, 5] ay nangangailangan ng isa pang pass, dahil 3 > 2 at kailangan silang palitan. Dahil gumagamit kami ng loop sa loob ng loop, lumalabas na tumataas ang pagiging kumplikado ng aming algorithm. Sa n elemento ito ay nagiging n * n, iyon ay O(n^2). Ang kumplikadong ito ay tinatawag na quadratic. Tulad ng naiintindihan namin, hindi namin alam kung gaano karaming mga pag-ulit ang kakailanganin. Ang tagapagpahiwatig ng pagiging kumplikado ng algorithm ay nagsisilbi sa layunin ng pagpapakita ng takbo ng pagtaas ng pagiging kumplikado, ang pinakamasamang kaso. Magkano ang tataas ng oras ng pagpapatakbo kapag nagbago ang bilang ng mga elemento. Ang pag-uuri ng bubble ay isa sa pinakasimple at hindi epektibong uri. Minsan din itong tinatawag na "stupid sorting". Kaugnay na materyal:
Ang isa pang uri ay ang uri ng pagpili. Mayroon din itong quadratic complexity, ngunit higit pa sa susunod. Kaya ang ideya ay simple. Pinipili ng bawat pass ang pinakamaliit na elemento at inililipat ito sa simula. Sa kasong ito, simulan ang bawat bagong pass sa pamamagitan ng paglipat sa kanan, iyon ay, ang unang pass - mula sa unang elemento, ang pangalawang pass - mula sa pangalawa. Magiging ganito ang hitsura:
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));
Ang pag-uuri na ito ay hindi matatag, dahil Ang mga magkakaparehong elemento (mula sa punto ng view ng katangian kung saan pinag-uuri-uriin natin ang mga elemento) ay maaaring magbago ng kanilang posisyon. Isang magandang halimbawa ang ibinigay sa artikulo sa Wikipedia: Sorting_by-selection . Kaugnay na materyal:
Ang insertion sort ay mayroon ding quadratic complexity, dahil muli tayong may loop sa loob ng loop. Paano ito naiiba sa uri ng pagpili? Ang pag-uuri na ito ay "matatag". Nangangahulugan ito na ang magkatulad na mga elemento ay hindi magbabago sa kanilang pagkakasunud-sunod. Magkapareho sa mga tuntunin ng mga katangian kung saan kami nag-uuri.
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));
Kabilang sa mga simpleng uri, mayroong isa pa - pag-uuri ng shuttle. Pero mas gusto ko yung shuttle variety. Para sa akin, bihira kaming mag-usap tungkol sa mga space shuttle, at ang shuttle ay higit pa sa isang run. Samakatuwid, mas madaling isipin kung paano inilunsad ang mga shuttle sa kalawakan. Narito ang isang kaugnayan sa algorithm na ito. Ano ang kakanyahan ng algorithm? Ang kakanyahan ng algorithm ay umulit tayo mula kaliwa hanggang kanan, at kapag nagpapalitan ng mga elemento, tinitingnan natin ang lahat ng iba pang elementong naiwan upang makita kung kailangang ulitin ang 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));
Ang isa pang simpleng uri ay Shell sort. Ang kakanyahan nito ay katulad ng bubble sort, ngunit ang bawat pag-ulit ay may iba't ibang agwat sa pagitan ng mga elementong inihahambing. Ang bawat pag-ulit ay hinahati ito. Narito ang isang halimbawa ng pagpapatupad:
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));
Bilang karagdagan sa mga simpleng uri na ipinahiwatig, mayroong mas kumplikadong mga uri. Halimbawa, pagsamahin ang pag-uuri. Una, ang recursion ay tutulong sa atin. Pangalawa, hindi na magiging quadratic ang complexity natin, gaya ng nakasanayan na natin. Ang pagiging kumplikado ng algorithm na ito ay logarithmic. Isinulat bilang O(n log n). Kaya gawin natin ito. Una, magsulat tayo ng recursive na tawag sa paraan ng pag-uuri:
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);}}
Ngayon, magdagdag tayo ng pangunahing aksyon dito. Narito ang isang halimbawa ng aming supermethod na may pagpapatupad:
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);}
Patakbuhin natin ang halimbawa sa pamamagitan ng pagtawag sa mergeSort(array, 0, array.length-1). Tulad ng nakikita mo, ang kakanyahan ay bumaba sa katotohanan na kinukuha namin bilang input ang isang array na nagpapahiwatig ng simula at pagtatapos ng seksyon na pag-uri-uriin. Kapag nagsimula ang pag-uuri, ito ang simula at pagtatapos ng array. Susunod na kalkulahin namin ang delimiter - ang posisyon ng divider. Kung ang divider ay maaaring hatiin sa 2 bahagi, pagkatapos ay tinatawag naming recursive sorting para sa mga seksyon kung saan hinati ng divider ang array. Naghahanda kami ng karagdagang buffer array kung saan pipiliin namin ang pinagsunod-sunod na seksyon. Susunod, inilalagay namin ang cursor sa simula ng lugar na pag-uri-uriin at magsimulang dumaan sa bawat elemento ng walang laman na hanay na inihanda namin at punan ito ng pinakamaliit na elemento. Kung ang elementong itinuturo ng cursor ay mas maliit kaysa sa elementong itinuturo ng divisor, inilalagay namin ang elementong ito sa buffer array at inililipat ang cursor. Kung hindi, inilalagay namin ang elementong itinuro ng separator sa buffer array at ilipat ang separator. Sa sandaling lumampas ang separator sa mga hangganan ng pinagsunod-sunod na lugar o napuno namin ang buong hanay, ang tinukoy na hanay ay itinuturing na pinagsunod-sunod. Kaugnay na materyal:
Ang isa pang kawili-wiling algorithm ng pag-uuri ay ang Pagbibilang ng Pag-uuri. Ang pagiging kumplikado ng algorithm sa kasong ito ay magiging O(n+k), kung saan ang n ay ang bilang ng mga elemento, at ang k ay ang pinakamataas na halaga ng elemento. Mayroong isang problema sa algorithm: kailangan nating malaman ang minimum at maximum na mga halaga sa array. Narito ang isang halimbawang pagpapatupad ng pagbibilang ng uri:
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;}
Tulad ng naiintindihan namin, ito ay napaka-inconvenient kapag kailangan naming malaman ang minimum at maximum na mga halaga nang maaga. At pagkatapos ay mayroong isa pang algorithm - Radix Sort. Ipapakita ko ang algorithm dito visually lamang. Para sa pagpapatupad, tingnan ang mga materyales:
Well, para sa dessert - isa sa mga pinakasikat na algorithm: mabilis na pag-uuri. Mayroon itong algorithmic complexity, iyon ay, mayroon tayong O(n log n). Ang uri na ito ay tinatawag ding Hoare sort. Kapansin-pansin, ang algorithm ay naimbento ni Hoare sa panahon ng kanyang pananatili sa Unyong Sobyet, kung saan nag-aral siya ng pagsasalin ng computer sa Moscow University at bumubuo ng isang Russian-English na phrasebook. Ginagamit din ang algorithm na ito sa isang mas kumplikadong pagpapatupad sa Arrays.sort sa Java. Paano ang Collections.sort? Iminumungkahi ko na makita mo para sa iyong sarili kung paano sila pinagsunod-sunod "sa ilalim ng hood". Kaya, ang code:
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);}}
Lahat ng bagay dito ay nakakatakot, kaya't aalamin natin ito. Para sa input array int[]source, nagtakda kami ng dalawang marker, kaliwa (L) at kanan (R). Kapag tinawag sa unang pagkakataon, tumutugma sila sa simula at dulo ng array. Susunod, tinutukoy ang sumusuportang elemento, aka pivot. Pagkatapos nito, ang aming gawain ay ilipat ang mga halagang mas mababa sa pivot, sa kaliwa pivot, at mas malaki sa kanan. Upang gawin ito, ilipat muna ang pointer Lhanggang sa makakita kami ng value na mas malaki kaysa sa pivot. Kung ang isang mas maliit na halaga ay hindi natagpuan, kung gayon
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