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 ҳақиқӣ намегардад ва аз ин рӯ, мо худро аз ҳолатҳои массив бо як элемент ё умуман бидуни онҳо муҳофизат мекунем ва code беҳтар ба назар мерасад. Аммо массиви ниҳоии мо ба ҳар ҳол мураттаб нашудааст, зеро... Дар як гузаргоҳ ҳамаро ҷудо кардан мумкин нест. Мо бояд ҳалқаи дигареро илова кунем, ки дар он мо як ба як гузаришро иҷро мекунем, то даме ки массиви мураттабшуда ба даст орем:
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) то он даме, ки қарор кунем, ки такрори дигар лозим нест. Бо нобаёнӣ, пеш аз ҳар як такрори нав, мо тахмин мезанем, ки массиви мо мураттаб шудааст ва мо дигар такрор кардан намехоҳем. Аз ин рӯ, мо элементҳоро пай дар пай мегузарем ва ин тахминро тафтиш мекунем. Аммо агар элементҳо корношоям бошанд, мо элементҳоро иваз мекунем ва дарк мекунем, ки мо боварӣ надорем, ки унсурҳо ҳоло дар тартиби дуруст ҳастанд. Аз ин рӯ, мо мехоҳем як такрори дигарро иҷро кунем. Масалан, [3, 5, 2]. 5 аз се зиёд аст, ҳамааш хуб аст. Аммо 2 камтар аз 5 аст. Аммо, [3, 2, 5] як гузаришро талаб мекунад, зеро 3 > 2 ва онҳо бояд иваз карда шаванд. Азбаски мо ҳалқаро дар дохor як ҳалқа истифода мебарем, маълум мешавад, ки мураккабии алгоритми мо меафзояд. Бо n элемент он n * n мешавад, яъне O(n^2). Ин мураккабиро квадратӣ меноманд. Тавре ки мо мефаҳмем, мо аниқ намедонем, ки чанд такрор лозим аст. Нишондиҳандаи мураккабии алгоритм барои нишон додани тамоюли афзоиши мураккабӣ, ҳолати бадтарин хидмат мекунад. Ҳангоми тағир додани шумораи элементҳо n вақти кор чӣ қадар зиёд мешавад. Навъи ҳубобӣ яке аз навъҳои соддатарин ва бесамар аст. Онро баъзан "таъминкунии аблаҳон" низ меноманд. Маводи марбут:
Навъи дигар навъи интихоб аст. Он инчунин мураккабии квадратӣ дорад, аммо дар ин бора баъдтар. Пас, идея оддӣ аст. Ҳар як гузариш элементи хурдтаринро интихоб мекунад ва онро ба ибтидо мебарад. Дар ин ҳолат, ҳар як гузаргоҳи навро бо ҳаракат ба тарафи рост оғоз кунед, яъне гузариши аввал - аз элементи якум, гузариши дуюм - аз дуюм. Ин чунин хоҳад буд:
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));
Навъи воридкунӣ инчунин мураккабии квадратӣ дорад, зеро мо боз як ҳалқа дар дохor як ҳалқа дорем. Он аз навъҳои интихоб чӣ фарқ дорад? Ин гурӯҳбандӣ "устувор" аст. Ин маънои онро дорад, ки унсурҳои якхела тартиби худро тағир намедиҳанд. Аз рӯи хусусиятҳое, ки мо аз рӯи он ҷудо мекунем, якхелаанд.
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));
Дар байни навъхои оддй боз як навъ — навъбандии шуттл мавчуд аст. Аммо ман навъи shuttle-ро афзалтар медонам. Ба назари ман, мо дар бораи киштиҳои кайҳонӣ хеле кам гап мезанем ва «Шаттл» бештар ran аст. Бинобар ин, тасаввур кардан осонтар аст, ки чи тавр ба кайхон парвоз мекунанд. Ин аст ассотсиатсия бо ин алгоритм. Моҳияти алгоритм чист? Мохияти алгоритм аз он иборат аст, ки мо аз чап ба рост такрор мекунем ва хангоми иваз кардани элементхо хамаи элементхои дигарро, ки дар паси худ мондаанд, тафтиш мекунем, то бубинем, ки иваз кардан лозим аст ё не.
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));
Навъи дигари оддӣ навъбандии Shell мебошад. Моҳияти он ба навъбандии ҳубобӣ шабоҳат дорад, аммо ҳар як такрор дар байни унсурҳои муқоисашаванда фосилаи гуногун дорем. Ҳар як такрор он ду маротиба кам карда мешавад. Дар ин ҷо як мисоли амалӣ аст:
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));
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);}}
Акнун биёед як амали асосиро ба он илова кунем. Ин аст як мисоли суперметоди мо бо татбиқ:
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);}
Биёед мисолро бо занги mergeSort(array, 0, array.length-1). Тавре ки шумо мебинед, моҳият аз он бармеояд, ки мо ҳамчун вуруд массиверо мегирем, ки ибтидо ва охири қисмати ҷудошавандаро нишон медиҳад. Вақте ки ҷудокунӣ оғоз мешавад, ин ибтидо ва охири массив мебошад. Минбаъд мо ҷудокунанда - мавқеи тақсимкуниро ҳисоб мекунем. Агар тақсимкунанда ба 2 қисм тақсим карда тавонад, пас мо навъбандии рекурсивиро барои бахшҳое меномем, ки тақсимкунанда массивро ба онҳо тақсим кардааст. Мо як массиви буферии иловагӣ омода мекунем, ки дар он қисмати мураттабшударо интихоб мекунем. Баъдан, мо курсорро дар аввали майдони мураттабшаванда ҷойгир мекунем ва аз ҳар як элементи массиви холии омодакардаамон гузаштан ва онро бо элементҳои хурдтарин пур мекунем. Агар элементе, ки курсор ба он ишора мекунад, аз элементи тақсимкунанда хурдтар бошад, мо ин элементро дар массиви буферӣ ҷойгир мекунем ва курсорро ҳаракат медиҳем. Дар акси ҳол, мо элементеро, ки ҷудокунанда ба он ишора кардааст, ба массиви буферӣ ҷойгир мекунем ва ҷудокунандаро ҳаракат медиҳем. Ҳамин ки ҷудокунанда аз ҳудуди минтақаи ҷудошуда берун меравад ё мо тамоми массивро пур мекунем, диапазони муайяншуда мураттаб ҳисобида мешавад. Маводи марбут:
Боз як алгоритми ҷолиби ҷудокунӣ ин ҳисобкунии ҷудокунӣ мебошад. Дар ин ҳолат мураккабии алгоритмӣ O(n+k) хоҳад буд, ки дар он n шумораи элементҳо ва k арзиши максималии элемент аст. Дар алгоритм як мушкилот вуҷуд дорад: мо бояд арзишҳои ҳадди ақал ва максималиро дар массив донем. Дар ин ҷо як мисоли татбиқи навъбандии ҳисоб аст:
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;}
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);}}
Ҳама чиз дар ин ҷо хеле даҳшатнок аст, бинобар ин мо онро мефаҳмем. Барои манбаи массиви воридотӣ int[], мо ду маркер гузоштем, чап (L) ва рост (R). Вақте ки бори аввал даъват карда мешавад, онҳо ба аввал ва охири массив мувофиқат мекунанд. Минбаъд, унсури дастгирӣ муайян карда мешавад, ака pivot. Пас аз ин, вазифаи мо ин аст, ки арзишҳои камтар аз pivot, ба чап pivotва калонтар ба тарафи рост ҳаракат кунем. Барои ин, аввал нишондиҳандаро ҳаракат кунед, Lто он даме, ки мо арзиши бузургтар аз -ро пайдо кунем pivot. Агар арзиши хурдтар пайдо нашавад, пас
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