A rendezés az egyik alapvető művelet, amelyet az objektumokon végzünk. A gyerekeket már gyermekkorukban is megtanítják válogatni, ahogy fejlesztik gondolkodási készségeiket. Ez alól a számítógépek és a szoftverek sem kivételek. A Java nyelven nagyon sokféle rendezési algoritmus létezik . Azt javaslom, nézze meg, mik ezek és hogyan működnek. Mi van, ha egyszer megkérdeznek valamelyikükről egy interjún?
Bevezetés
Az elemek rendezése az algoritmusok egyik kategóriája, amelyet a fejlesztőnek ismernie kell. Ha egykor az informatikát nem vették komolyan iskolás koromban, akkor a mai diákoknak tudniuk kell rendezési algoritmusokat megvalósítani és megérteni. Az alapvető algoritmusok, a legegyszerűbbek, for ciklus segítségével valósulnak meg . Természetesen egy elemgyűjtemény, például egy tömb rendezéséhez valamilyen módon végig kell mennie a gyűjteményen. Például:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Mit mondhatunk erről a kódrészletről? int iVan egy ciklusunk, amelyben az indexet ( ) 0-ról a tömb utolsó elemére változtatjuk . Valójában egyszerűen kivesszük a tömb minden elemét, és kinyomtatjuk a tartalmát. Minél több elem van a tömbben, annál tovább tart a kód befejezése. Vagyis ha naz elemek száma, amikor n = 10a program futtatása kétszer annyi ideig tart, mint amikor n = 5. Ha a programunknak egyetlen ciklusa van, akkor a végrehajtási idő lineárisan nő: minél több elem van, annál hosszabb a végrehajtási idő. Kiderült, hogy a fenti algoritmus lineáris időben működik (n lineáris függvénye). Ilyen esetekben azt mondjuk, hogy az algoritmus bonyolultsága "O(n)". Ezt a jelölést "nagy O"-nak vagy "aszimptotikus viselkedésnek" is nevezik. De csak emlékezhetsz"
A legegyszerűbb rendezési algoritmus (buborékos rendezés)
Tegyük fel, hogy van egy tömbünk, és tudjuk iterálni rajta. Nagy. Most próbáljuk meg növekvő sorrendbe rendezni. Mit is jelent ez? Ez azt jelenti, hogy adott két elem (például , a = 6) b = 5, át kell rendeznünk a, és bha anagyobb, mint b(ha a > b). Mit jelent ez, ha indexet használunk egy gyűjtemény kezelésére (mint egy tömb esetében)? Ez azt jelenti, hogy ha az a indexű elem nagyobb, mint a b( array[a] > array[b]) indexű elem, akkor az elemeket fel kell cserélni. A helyváltoztatásnak különböző módjai vannak. De olyan technikát fogunk alkalmazni, amely egyszerű, érthető és könnyen megjegyezhető:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Most a következőket írhatjuk:
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));
Mint látható, az elemek valóban felcserélődtek. Az 1-es indexszel kezdtük, mert ha a tömbnek csak egy eleme van, akkor a kifejezés array[i] < array[i-1]érvénytelen az index számára 0. Ezzel megvéd minket azoktól az esetektől is, amikor a tömbnek nincs eleme, vagy csak egy eleme van, és ezáltal a kód jobban néz ki. De az eredményül kapott tömb még mindig nincs rendezve, mert egy lépés nem elég a rendezéshez. Hozzá kell adnunk egy újabb ciklust, amelyben újra és újra el kell végeznünk az áthaladásokat, amíg egy rendezett tömböt nem kapunk:
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));
Így befejeztük az első rendezési algoritmust. Addig ismételjük a külső ciklust ( while), amíg úgy nem döntünk, hogy nincs szükség további iterációkra. Alapértelmezés szerint minden új iteráció előtt azt feltételezzük, hogy a tömbünk rendezve van, és többé nem kell hurkolnunk. Ennek megfelelően sorban haladunk az elemek között, és ellenőrizzük ezt a feltevést. De ha az elemek nincsenek rendben, akkor felcseréljük az elemeket, és megértjük, hogy most nincs garancia arra, hogy az elemek a megfelelő sorrendben vannak. Ez azt jelenti, hogy egy újabb iterációt kell végrehajtanunk. Tegyük fel például, hogy van [3, 5, 2]. 5több mint 3– minden rendben van. De 2kevesebb, mint 5. Ehhez azonban [3, 2, 5]újabb bérlet szükséges, mivel3 > 2és cserélni kell őket. Mivel hurkot használunk a hurkon belül, az algoritmusunk bonyolultsága növekszik. Adott nelemekből , n * nazaz O(n^2). Ezt nevezik másodfokú komplexitásnak. Általában nem tudhatjuk pontosan, hány iterációra lesz szükség. Egy algoritmus komplexitásának kifejezése megmutatja, hogy a bonyolultság a legrosszabb esetben hogyan növekszik. Azaz azt jelzi, hogy az elemek számának változásával mennyivel nő a végrehajtási idő n. A buborékos rendezés az egyik legegyszerűbb és leghatékonyabb rendezési algoritmus. Néha "hülye fajta"-nak is nevezik. Anyag ebben a témában:
Egy másik rendezési algoritmus a kiválasztási rendezés. Ennek is van négyzetes összetettsége, de erről később. Szóval az ötlet egyszerű. Minden lépésnél kiválasztjuk a legkisebb elemet, és eltoljuk az elejére. Ezenkívül minden lépés egy lépéssel jobbra kezdődik. Más szóval, az első lépés a nulladik elemtől kezdődik, a második lépés az elsőtől stb. Így fog kinézni:
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));
Ez a rendezés instabil, mert az azonos elemek (bármilyen jellemzőt is használunk az elemek rendezésére) megváltoztathatják egymáshoz viszonyított helyzetüket. Erre jó példa van a Wikipédia kijelölési rendezésről szóló cikkében . Anyag ebben a témában:
A beillesztési rendezésnek másodfokú összetettsége is van, mivel ismét van egy ciklus a cikluson belül. Mitől más a beillesztési sorrend? Ez a rendezési algoritmus "stabil". Ez azt jelenti, hogy az azonos elemek nem változtatják meg egymáshoz viszonyított sorrendjüket. Ismét ugyanazt értjük azon jellemzők tekintetében, amelyek alapján rendezünk.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Shuttle fajta
Létezik egy másik egyszerű rendezési algoritmus is: ingajáratos rendezés. Ezt kétirányú buborékos rendezésnek vagy koktél shakernek is nevezik. Ezek az alternatív nevek azt sugallják, hogy az űrsiklófajta nem az űrsiklóról szól. Valamiről szól, ami ide-oda mozog. Most már erre gondolhat, ha erre az algoritmusra gondol. Mi az algoritmus lényege? Az algoritmus lényege, hogy balról jobbra iterálunk, felcseréljük az elemeket, és ellenőrizzük, hogy a másik irányban maradt elemek közül nem kell-e felcserélni.
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));
Egy másik egyszerű rendezési algoritmus a shell-rendezés. Lényege hasonló a buborékos rendezéshez, de minden iterációban más rés van az összehasonlított elemek között. Minden iterációnál félbevágják. Íme egy megvalósítás:
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 gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap 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));
Ezeken az egyszerű rendezési algoritmusokon kívül léteznek bonyolultabb rendezési algoritmusok is. Például a rendezés összevonása. Két dolgot kell megjegyezni. Először is a rekurzió jön segítségünkre itt. Másodszor, az algoritmus bonyolultsága már nem másodfokú, mint ahogy azt megszoktuk. Ennek az algoritmusnak a bonyolultsága logaritmikus. Ez így van írva O(n log n). Tehát hajtsuk végre. Először írunk egy rekurzív hívást a rendezési metódusra:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Most pedig adjuk hozzá a fő műveletet a megvalósításunkhoz. Íme a szuper módszerünk:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
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);
}
Példánkat lefuttathatjuk hívássalmergeSort(array, 0, array.length-1). Amint láthatja, a folyamat egy bemeneti tömb elfogadásában áll le, valamint a rendezendő szakasz kezdetére és végére vonatkozó jelzéseket. Amikor a rendezés elkezdődik, ez a tömb eleje és vége. Ezután kiszámítjuk a határolót, amely az az index, ahol felosztjuk a tömböt. Ha a tömb 2 részre osztható, akkor a tömb két felére rekurzívan hívjuk meg a rendezési metódust. Készítünk egy segédpuffert, ahová beillesztjük a rendezett részt. Ezután állítsa be az indexet a rendezendő szakasz elején, és kezdje el végigjárni az üres puffer minden elemét, feltöltve azokat a legkisebb elemekkel. Ha az index által mutatott elem kisebb, mint a határoló által mutatott elem, akkor az elemet a pufferbe helyezzük, és eltoljuk az indexet. Másképp, a határoló által mutatott elemet a pufferbe helyezzük és a határolót eltoljuk. Amint a határoló túllép a rendezett szakasz határain, vagy a teljes tömböt kitöltjük, a megadott tartomány rendezettnek minősül.Anyag ebben a témában:
Egy másik érdekes rendezési algoritmus a számláló rendezés. Az algoritmus bonyolultsága itt O(n+k), ahol naz elemek száma és kegy elem maximális értéke. Ennek az algoritmusnak van egy hiányossága: ismernünk kell a tömb minimális és maximális értékét. Íme egy példa a számolási rendezésre:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Megértheti, hogy nagyon kényelmetlen, ha előre tudnunk kell a minimális és maximális értékeket. És van itt egy másik algoritmusunk is: radix sort. Itt csak vizuálisan mutatom be az algoritmust. Lásd a megvalósításhoz szükséges kiegészítő anyagokat: Anyagok:
Nos, itt az ideje a desszertnek – a gyors válogatásnak, az egyik leghíresebb válogatási algoritmusnak. Ennek logaritmikus összetettsége van: O(n log n). Ezt a rendezési algoritmust Tony Hoare fejlesztette ki. Érdekes módon a Szovjetunióban élve találta ki, ahol gépi fordítást tanult a Moszkvai Egyetemen, és kifejlesztett egy orosz-angol nyelvű kifejezéstárat. Sőt, a Java ennek az algoritmusnak egy bonyolultabb változatát használja a -ban Arrays.sort. Mi a helyzet Collections.sort? Miért nem nézzük meg, hogyan rendeződnek a dolgok "a motorháztető alatt"? Íme a kód:
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 as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Ez az egész nagyon ijesztő dolog, úgyhogy ássunk bele. A bemeneti tömbhöz ( int[]forrás) két jelölőt hozunk létre: bal ( L) és jobb ( R). Az első metódushívás során ezek megfelelnek a tömb elejének és végének. Ezután azonosítjuk a pivot elemet, amelyet találóan neveznek el pivot. pivotEzek után az a feladatunk, hogy a -nál kisebb értékeket balra pivot, a nagyobbakat pedig jobbra mozgassuk . Ehhez először addig mozgassuk a Ljelölőt, amíg nem találunk nál nagyobb értéket pivot. Ha nem találunk kisebb értéket, akkor
L egyenlővé válik
pivot. Ezután mozgassuk a
Rjelölőt, amíg nem találunk kisebb értéket, mint
pivot. Ha nem található nagyobb érték, akkor
Regyenlővé válik a -val
pivot. Ezután, ha a
Lmarker a
Rmarker előtt van, vagy egybeesik vele, akkor megpróbáljuk felcserélni az elemeket, ha az
Lelem kisebb, mint az
Relem.
LEzután 1-gyel jobbra,
R1-gyel balra toljuk . Ha a
Lmarker túllép a
Rmarkeren, az azt jelenti, hogy a csere befejeződött: a kisebb értékek balra
pivot, a nagyobb értékek a jobbra vannak.
pivot. Ezt követően ugyanazt a rendezési metódust hívjuk meg rekurzívan az altáblákon – a rendezendő szakasz elejétől a jobb oldali jelölőig, és a bal jelölőtől a rendezendő szakasz végéig. Miért az elejétől a megfelelő jelzőig? Mert az iteráció végén kiderül, hogy a jobb oldali marker eleget mozog ahhoz, hogy a bal oldali rész határává váljon. Ez az algoritmus összetettebb, mint az egyszerű rendezés, ezért a legjobb, ha felvázolja. Vegyünk egy fehér papírlapot, és írjuk be: 4 2 6 7 3. Majd írjuk
pivotközépre, azaz a 6-os szám alá. Karikázzuk be! 4 alá írjon
L, 3 alá pedig
R.
L4 kevesebb, mint 6, 2 kevesebb, mint 6. Végül a pozícióba lépünk
pivot, mert
Lnem tudunk elmenni
pivot, állapotának megfelelően. Írd újra 4 2 6 7 3. Karikázd be a 6-ost (
pivot), és tedd
Lalá! Most mozgassa a
Rjelölőt. A 3 kisebb, mint 6, ezért tegye a
Rjelölőt 3-ra. Mivel a 3 kisebb, mint 6 (
pivot), végrehajtunk egy
swap. Írd le az eredményt: 4 2 3 7 6. Karikázd be a 6-ost, mert ez még mindig a
pivot. A
Lmarker a 3-on van. A
Rmarker a 6-on van. Ne feledje, hogy addig mozgatjuk a markereket, amíg
Ltúl nem lép
R. Ugrás
La következő számra. Itt két lehetőséget szeretnék megvizsgálni: 1) azt az esetet, amikor az utolsó előtti szám 7 és 2) azt az esetet, amikor az 1, nem pedig 7.
Ha az utolsó előtti szám 1: Mozgassa a
Ljelölőt 1-re, mert mozoghatunk
Lamíg a
La jelölő a -nál kisebb számra mutat
pivot. De nem léphetünk
Rle 6-ról, mert csak akkor tudjuk elmozdítani az R-t, ha a
Rmarker olyan számra mutat, amely nagyobb, mint
pivot. Nem hajtunk végre -t
swap, mert 1 kisebb, mint 6. Írd le az aktuális helyzetet: 4 2 3 1 6. Karika 6 (
pivot).
Leltolódik
pivotés megáll.
Rnem mozdul. Nem hajtunk végre cserét. Váltás
Lés
Regy pozícióval. Írja a
Rjelölőt 1 alá. A
Ljelölő határon kívül van. Mivel
Ltúl van a határokon, nem teszünk semmit. De ismét 4 2 3 1-et írunk, mert ez a bal oldalunk, ami kisebb, mint
pivot(6). Válaszd ki az újat
pivot, és kezdj újra mindent :)
Ha az utolsó előtti szám 7:Mozgassa a
Lmarkert a 7-re. A jobb oldali jelölőt nem tudjuk mozgatni, mert az már a forgópontra mutat. 7 nagyobb mint
pivot, ezért végrehajtunk egy
swap. Írd le az eredményt: 4 2 3 6 7. Karikázd be a 6-ost, mert ez a
pivot. A
Ljelölő most 7-re, a
Rmarker pedig 3-ra van eltolva. Nincs értelme a részt
La végére rendezni, mert csak 1 elem van. A 4-es részt azonban a jelölőhöz küldjük
Rválogatásra. Válasszunk egyet
pivot, és kezdjük elölről :) Első pillantásra úgy tűnhet, hogy ha sok olyan értéket adunk hozzá,
pivot, akkor megtöri az algoritmust. De ez nem így van. Trükkös kombinációkat találhat ki, és papíron meggyőzheti magát arról, hogy minden helyes, és csodálkozhat, hogy az ilyen egyszerű műveletek ilyen megbízható válogatási mechanizmust valósítanak meg. Az egyetlen hátránya, hogy ez a rendezési algoritmus nem stabil. Mivel a csere megváltoztathatja az azonos elemek egymáshoz viszonyított sorrendjét, ha az egyiket korábban találja,
pivotmielőtt a másik elemet az előtti részre cserélné
pivot.
Alsó vonal
Fentebb a Java nyelven megvalósított rendezési algoritmusok "úriemberek" halmazát néztük meg. Az algoritmusok általában hasznosak, mind alkalmazott szempontból, mind a gondolkodás megtanulása szempontjából. Van, amelyik egyszerűbb, van, amelyik bonyolultabb. Okos emberek egyesek megvédték a szakdolgozatukat. Mások számára szuper vastag könyveket írtak. Remélem, hogy a kiegészítő anyagok még többet segítenek, mert ez a cikk csak egy áttekintés, amely már most is jelentősnek bizonyult. Célja pedig egy kis bevezető. Bevezetést is találhat az algoritmusokhoz, ha elolvassa a
"Grokking Algoritmusok " részt. Tetszik még a Jack Brown lejátszási listája:
AQA Decision 1 1.01 Tracing an Algorithm . A szórakozás kedvéért algoritmus vizualizációkat láthat a
rendezésnél.visualgo.net .
GO TO FULL VERSION