L'ordinamento è uno dei tipi base di attività o azioni eseguite sugli oggetti. Anche durante l'infanzia, ai bambini viene insegnato a ordinare, sviluppando il loro pensiero. Anche i computer e i programmi non fanno eccezione. Esiste una grande varietà di algoritmi. Ti suggerisco di guardare cosa sono e come funzionano. Inoltre, cosa succederebbe se un giorno ti venisse chiesto di uno di questi durante un'intervista?
introduzione
L'ordinamento degli elementi è una delle categorie di algoritmi a cui uno sviluppatore deve abituarsi. Se una volta, quando studiavo, l’informatica non veniva presa così sul serio, ora a scuola dovrebbero essere in grado di implementare algoritmi di ordinamento e di capirli. Gli algoritmi base, quelli più semplici, vengono implementati utilizzando un loop for. Naturalmente, per ordinare una raccolta di elementi, ad esempio un array, è necessario in qualche modo attraversare questa raccolta. Per esempio:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Cosa puoi dire di questo pezzo di codice? Abbiamo un ciclo in cui cambiamo il valore dell'indice ( int i) da 0 all'ultimo elemento dell'array. In sostanza, stiamo semplicemente prendendo ogni elemento dell'array e stampandone il contenuto. Maggiore è il numero di elementi nell'array, maggiore sarà il tempo necessario per l'esecuzione del codice. Cioè, se n è il numero di elementi, con n=10 il programma impiegherà 2 volte più tempo per essere eseguito rispetto a n=5. Quando il nostro programma ha un ciclo, il tempo di esecuzione aumenta in modo lineare: maggiore è il numero di elementi, più lunga è l'esecuzione. Risulta che l'algoritmo del codice precedente viene eseguito in tempo lineare (n). In questi casi, si dice che la “complessità dell’algoritmo” sia O(n). Questa notazione è anche chiamata "grande O" o "comportamento asintotico". Ma puoi semplicemente ricordare “la complessità dell’algoritmo”.
L'ordinamento più semplice (Bubble Sort)
Quindi, abbiamo un array e possiamo scorrere su di esso. Grande. Proviamo ora a ordinarlo in ordine crescente. Cosa significa questo per noi? Ciò significa che dati due elementi (ad esempio a=6, b=5), dobbiamo scambiare a e b se a è maggiore di b (se a > b). Cosa significa questo per noi quando lavoriamo con una raccolta per indice (come nel caso di un array)? Ciò significa che se l'elemento con indice a è maggiore dell'elemento con indice b, (array[a] > array[b]), tali elementi devono essere scambiati. Il cambio di posto è spesso chiamato scambio. Esistono vari modi per cambiare posto. Ma usiamo un codice semplice, chiaro e facile da ricordare:
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));
Come possiamo vedere, gli elementi hanno effettivamente cambiato posto. Abbiamo iniziato con un elemento, perché... se l'array è composto da un solo elemento, l'espressione 1 < 1 non restituirà vero e quindi ci proteggeremo dai casi di un array con un elemento o senza di essi, e il codice avrà un aspetto migliore. Ma il nostro array finale non è comunque ordinato, perché... Non è possibile ordinare tutti in un unico passaggio. Dovremo aggiungere un altro ciclo in cui eseguiremo i passaggi uno per uno fino ad ottenere un array ordinato:
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));
Quindi il nostro primo ordinamento ha funzionato. Iteriamo nel ciclo esterno ( while) finché non decidiamo che non sono necessarie ulteriori iterazioni. Per impostazione predefinita, prima di ogni nuova iterazione, assumiamo che il nostro array sia ordinato e non vogliamo più iterare. Pertanto, esaminiamo gli elementi in sequenza e verifichiamo questo presupposto. Ma se gli elementi sono fuori ordine, li scambiamo e ci rendiamo conto che non siamo sicuri che gli elementi siano ora nell'ordine corretto. Pertanto, vogliamo eseguire un'altra iterazione. Ad esempio, [3, 5, 2]. 5 è più di tre, va tutto bene. Ma 2 è inferiore a 5. Tuttavia, [3, 2, 5] richiede un passaggio in più, perché 3 > 2 e devono essere scambiati. Poiché utilizziamo un ciclo all'interno di un ciclo, risulta che la complessità del nostro algoritmo aumenta. Con n elementi diventa n * n, cioè O(n^2). Questa complessità è chiamata quadratica. Come abbiamo capito, non possiamo sapere esattamente quante iterazioni saranno necessarie. L'indicatore della complessità dell'algoritmo ha lo scopo di mostrare la tendenza all'aumento della complessità, il caso peggiore. Quanto aumenterà il tempo di esecuzione quando cambia il numero di elementi n. Il Bubble sort è uno dei tipi più semplici e inefficienti. A volte viene anche chiamato "ordinamento stupido". Materiale correlato:
Un altro tipo è l'ordinamento per selezione. Ha anche complessità quadratica, ma ne parleremo più avanti. Quindi l'idea è semplice. Ogni passaggio seleziona l'elemento più piccolo e lo sposta all'inizio. In questo caso, inizia ogni nuovo passaggio spostandoti verso destra, ovvero il primo passaggio - dal primo elemento, il secondo passaggio - dal secondo. Apparirà così:
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));
Questo ordinamento è instabile, perché elementi identici (dal punto di vista della caratteristica in base alla quale ordiniamo gli elementi) possono cambiare la loro posizione. Un buon esempio è fornito nell'articolo di Wikipedia: Sorting_by-selection . Materiale correlato:
Anche l'ordinamento per inserzione ha complessità quadratica, poiché abbiamo ancora una volta un ciclo all'interno di un ciclo. In cosa differisce dall'ordinamento di selezione? Questo ordinamento è "stabile". Ciò significa che gli elementi identici non cambieranno il loro ordine. Identici in termini di caratteristiche in base alle quali selezioniamo.
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));
Tra i tipi semplici ce n'è un altro: lo smistamento a navetta. Ma preferisco la varietà della navetta. Mi sembra che parliamo raramente di navette spaziali e la navetta è più una corsa. Pertanto, è più facile immaginare come le navette vengano lanciate nello spazio. Ecco un'associazione con questo algoritmo. Qual è l'essenza dell'algoritmo? L'essenza dell'algoritmo è che iteriamo da sinistra a destra e, quando si scambiano gli elementi, controlliamo tutti gli altri elementi rimasti per vedere se lo scambio deve essere ripetuto.
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));
Un altro ordinamento semplice è l'ordinamento Shell. La sua essenza è simile al bubble sort, ma ad ogni iterazione abbiamo un divario diverso tra gli elementi confrontati. Ad ogni iterazione viene dimezzato. Ecco un esempio di implementazione:
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));
Oltre ai tipi semplici indicati, esistono tipi più complessi. Ad esempio, unisci ordinamento. Innanzitutto la ricorsione ci verrà in aiuto. In secondo luogo, la nostra complessità non sarà più quadratica, come siamo abituati. La complessità di questo algoritmo è logaritmica. Scritto come O(n log n). Quindi facciamolo. Per prima cosa scriviamo una chiamata ricorsiva al metodo di ordinamento:
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);}}
Ora aggiungiamo un'azione principale. Ecco un esempio del nostro supermetodo con implementazione:
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);}
Eseguiamo l'esempio chiamando il file mergeSort(array, 0, array.length-1). Come puoi vedere, l'essenza si riduce al fatto che prendiamo come input un array che indica l'inizio e la fine della sezione da ordinare. Quando inizia l'ordinamento, questo è l'inizio e la fine dell'array. Successivamente calcoliamo il delimitatore: la posizione del divisore. Se il divisore può dividersi in 2 parti, allora chiamiamo ordinamento ricorsivo per le sezioni in cui il divisore ha diviso l'array. Prepariamo un array di buffer aggiuntivo in cui selezioniamo la sezione ordinata. Successivamente posizioniamo il cursore all'inizio dell'area da ordinare e iniziamo a scorrere ogni elemento dell'array vuoto che abbiamo preparato e riempirlo con gli elementi più piccoli. Se l'elemento puntato dal cursore è più piccolo dell'elemento puntato dal divisore, posizioniamo questo elemento nell'array buffer e spostiamo il cursore. Altrimenti, posizioniamo l'elemento puntato dal separatore nell'array buffer e spostiamo il separatore. Non appena il separatore supera i limiti dell'area ordinata o riempiamo l'intero array, l'intervallo specificato viene considerato ordinato. Materiale correlato:
Ordinamento per conteggio e ordinamento per radice
Un altro algoritmo di ordinamento interessante è Counting Sort. La complessità algoritmica in questo caso sarà O(n+k), dove n è il numero di elementi e k è il valore massimo dell'elemento. C'è un problema con l'algoritmo: dobbiamo conoscere i valori minimo e massimo nell'array. Ecco un esempio di implementazione del counting sort:
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;}
Come abbiamo capito, è molto scomodo dover conoscere in anticipo i valori minimo e massimo. E poi c'è un altro algoritmo: Radix Sort. Presenterò qui l'algoritmo solo visivamente. Per l'implementazione, vedere i materiali:
Bene, per dessert, uno degli algoritmi più famosi: l'ordinamento rapido. Ha complessità algoritmica, cioè abbiamo O(n log n). Questo ordinamento è anche chiamato ordinamento Hoare. È interessante notare che l'algoritmo è stato inventato da Hoare durante il suo soggiorno in Unione Sovietica, dove ha studiato traduzione informatica all'Università di Mosca e stava sviluppando un frasario russo-inglese. Questo algoritmo viene utilizzato anche in un'implementazione più complessa in Arrays.sort in Java. Che dire di Collections.sort? Ti suggerisco di vedere di persona come vengono ordinati "sotto il cofano". Quindi, il codice:
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);}}
Tutto qui è molto spaventoso, quindi lo scopriremo. Per la int[]sorgente dell'array di input, impostiamo due marcatori, sinistro (L) e destro (R). Quando vengono chiamati per la prima volta, corrispondono all'inizio e alla fine dell'array. Successivamente, viene determinato l'elemento di supporto, ovvero pivot. Successivamente, il nostro compito è spostare i valori inferiori a pivot, a sinistra pivote quelli più grandi a destra. Per fare ciò, muoviamo prima il puntatore Lfinché non troviamo un valore maggiore di pivot. Se non viene trovato un valore inferiore, allora
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