A fejlesztési projektek gyakrabban használnak különféle algoritmusokat, mint gondolná. Tegyük fel például, hogy bizonyos adatokat bizonyos paraméterek (oszlopok) szerint kell rendeznünk, hogy különösebb erőfeszítés nélkül navigálhassunk az adatok között. Így egyáltalán nem lenne furcsa, ha egy állásinterjút megkérdezne egy konkrét alapalgoritmusról, és esetleg azt a feladatot adná, hogy azt kód segítségével implementálja. És mivel ezen a webhelyen tartózkodik, olyan merész leszek, hogy feltételezzem, hogy Java nyelven ír. Ezért ma azt javaslom, hogy ismerkedjen meg néhány alapvető algoritmussal és konkrét példákkal, hogyan implementálhatja azokat Java-ban. A "néhány" alatt azt értem, hogy:
A tömbrendezési algoritmusok áttekintése:
buborékos fajta,
kiválasztási rendezés,
beillesztési rendezés,
Shell fajta,
gyors válogatás,
egyesített rendezés,
Mohó algoritmusok
Útkereső algoritmusok
mélységi keresés
szélesség-első keresés
Dijkstra legrövidebb út első algoritmusa
Nos, minden további nélkül, térjünk a dologra.
1. A rendezési algoritmusok áttekintése
Buborékos fajta
Ez a rendezési algoritmus elsősorban az egyszerűségéről ismert, de egyben az egyik leglassabb is. Példaként vegyünk egy buborékos rendezést a számok növekvő sorrendjében. Képzeljünk el egy véletlenszerű számsorozatot. A következő lépéseket hajtjuk végre ezeken a számokon, a sorozat elejétől kezdve:
hasonlítson össze két számot;
ha a bal oldali szám nagyobb, cserélje ki őket;
mozgassa egy pozíciót jobbra.
Miután elvégeztük ezeket a lépéseket a teljes sorozaton, azt találjuk, hogy a legnagyobb szám a számsorunk végén található. Ezután egy újabb lépést hajtunk végre a sorozaton, pontosan ugyanazokat a lépéseket végrehajtva, mint fent. A lista utolsó elemét azonban ezúttal nem vesszük fel, mivel ez a legnagyobb szám, és már pontosan ott van, ahol a számok rendezésekor lennie kell. Ismét a következő legnagyobb számot mozgatjuk a sorozatunk végére. Természetesen ez azt jelenti, hogy a két legnagyobb szám a maga helyén áll. Ismét áthaladunk a sorozaton, kizárva a már a helyükön lévő elemeket, amíg az összes elem a kívánt sorrendbe nem kerül. Nézzük meg, hogyan valósul meg a buborékok rendezése a Java kódban:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
Amint látja, nincs itt semmi bonyolult. Minden nagyszerűnek tűnik, és az is lenne, ha nem lenne egy hiányosság – a buborékok rendezése nagyon-nagyon lassú. Ennek időbonyolultsága O(N²), mivel beágyazott hurkokat alkalmazunk. Az elemek feletti külső hurok N-szer kerül végrehajtásra. A belső ciklus szintén N-szer kerül végrehajtásra. Ennek eredményeként N*N vagy N² iterációkat kapunk.
Kijelölés rendezése
Ez az algoritmus hasonló a buborékos rendezéshez, de egy kicsit gyorsabban működik. Ismét példaként vegyünk egy számsort, amelyet növekvő sorrendbe szeretnénk rendezni. Ennek az algoritmusnak az a lényege, hogy szekvenciálisan iteráljuk az összes számot, és kiválasztjuk a legkisebb elemet, amit veszünk és felcserélünk a bal szélső elemre (a 0. elemre). Itt a buborékos rendezéshez hasonló helyzet áll előttünk, de ebben az esetben a rendezett elemünk lesz a legkisebb. Ezért az elemek következő lépése az 1-es indexű elemtől kezdődik. Ezeket az áthaladásokat addig ismételjük, amíg az összes elemet rendeztük. Megvalósítás Java nyelven:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
Ez az algoritmus jobb, mint a buborékos rendezés, mivel itt a szükséges eltolások száma O(N²)-ről O(N-ra) csökken. Egy elemet sem vezetünk végig a teljes listán, de az összehasonlítások száma továbbra is O(N²).
Beillesztési rendezés
Egy újabb számsort veszünk figyelembe, amelyet növekvő sorrendbe szeretnénk rendezni. Ez az algoritmus egy jelölő elhelyezéséből áll, ahol a markertől balra lévő összes elem már részben rendezve van egymás között. Az algoritmus minden lépésében kiválasztódik az egyik elem, és a részlegesen rendezett sorrendben a kívánt helyre kerül. Így a rendezett rész addig nő, amíg az összes elemet meg nem vizsgáltuk. Érdekelne, hogyan kaphatja meg a már rendezett elemek részhalmazát, és hogyan határozhatjuk meg, hová helyezzük a jelölőt? De az első elemből álló tömb már rendezve van, nem? Nézzük meg a Java implementációt:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
Ez a fajta rendezés felülmúlja a fent leírtakat, mert annak ellenére, hogy azonos O(N²) futási idővel rendelkezik, ez az algoritmus kétszer olyan gyors, mint a buborékos rendezés, és valamivel gyorsabb, mint a kiválasztási rendezés.
Shell fajta
Ez a rendezés lényegében egy módosított beillesztési rendezés. miről beszélek? Tegyük az első dolgokat az első helyre. Először ki kell választanunk egy intervallumot. Számos megközelítés létezik ennek a választásnak a meghozatalára. Ezt nem részletezzük túlságosan. Osszuk ketté a tömbünket, és kapjunk egy számot – ez lesz az intervallumunk. Tehát, ha a tömbünkben 9 elem van, akkor az intervallumunk 9/2 = 4,5 lesz. Eldobjuk a tört részt, és 4-et kapunk, mivel a tömb indexei csak egész számok lehetnek. Ezt az intervallumot fogjuk használni csoportjaink kialakításához. Ha egy elem indexe 0, akkor a csoport következő elemének indexe 0+4, azaz 4. A harmadik elem indexe 4+4, a negyediké 8+4, és így tovább. A második csoportban az első elem 1,5,9 lesz... A harmadik és negyedik csoportban is hasonló lesz a helyzet. Ennek eredményeként a {6,3,8,8,6,9,4,11,1} számtömbből négy csoportot kapunk: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Megtartják helyüket az általános tömbben, de ugyanannak a csoportnak a tagjaiként jelöltük meg: {6,3,8,8,6,9,4,11,1} Következő, beillesztés Ezekre a csoportokra a rendezést alkalmazzuk, majd így néznek ki: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Az általános tömbben a a csoportok által elfoglalt cellák változatlanok maradnak, de belső sorrendjük megváltozik, a fenti csoportok sorrendjének megfelelően: {1,3,4,8,6,9,8,11,6} A tömb egy egy kicsit több megrendelt, nem? A következő intervallumot 2-vel osztjuk: 4/2 = 2 Két csoportunk van: I — {1,4,6,8,6} II — {3,8,9,11} Az általános tömbben : {1,3,4,8,6,9,8,11,6} Mindkét csoporton futtatjuk a beillesztési rendezési algoritmust, és ezt a tömböt kapjuk: {1,3,4,8,6,9,6, 11, 8} Most a tömbünk majdnem rendezve van. El kell végeznünk az algoritmus utolsó iterációját: az intervallumot elosztjuk 2-vel: 2/2 = 1. Kapunk egy csoportot, amely a teljes tömbből áll: {1,3,4,8,6,9,6,11 ,8} Ezen a beillesztési rendezési algoritmust futtatva a következőket kapjuk: {1,3,4,6,6,8,8,9,11} Nézzük meg, hogyan kelthetjük életre ezt a rendezést Java kódban:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
A Shellsort teljesítményét jelenleg nem könnyű jellemezni, mivel az eredmények különböző helyzetekben eltérőek. A kísérleti becslések O(N 3/2 ) és O(N 7/6 ) között mozognak.
Quicksort
Ez az egyik legnépszerűbb algoritmus, ezért érdemes külön odafigyelni rá. Ennek az algoritmusnak a lényege, hogy egy pivot elemet kiválasztunk az elemek listájában. Az összes többi elemet a pivot elemhez viszonyítva rendezzük. A pivot elemnél kisebb értékek a bal oldalon találhatók. Ennél nagyobb értékek a jobb oldalon vannak. Ezután a jobb és bal oldalon is kijelöljük a pivot elemeket, és ugyanez történik: az értékek ezekhez az elemekhez viszonyítva rendeződnek. Ezután pivot elemeket választunk ki az újonnan kialakított részekben, és így tovább, amíg egy rendezett sorozatot nem kapunk. Ennek az algoritmusnak a következő Java-megvalósítása rekurziót használ:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
Kétségtelenül a Quicksort algoritmus a legnépszerűbb, mivel a legtöbb helyzetben gyorsabban fut, mint mások. Időbonyolultsága O(N*logN).
Összevonás rendezés
Ez a fajta is népszerű. Ez egy a sok algoritmus közül, amely az „oszd meg és uralkodj” elvén támaszkodik. Az ilyen algoritmusok először a problémát kezelhető részekre osztják (a gyorsrendezés egy másik példa az ilyen algoritmusokra). Tehát mi ennek az algoritmusnak a lényege?
Feloszt:
A tömb két, megközelítőleg azonos méretű részre oszlik. E két rész mindegyikét további két részre osztjuk, és így tovább, amíg a lehető legkisebb oszthatatlan rész megmarad. A legkisebb oszthatatlan részeink akkor vannak, ha minden tömbnek van egy eleme, azaz egy már rendezett tömb.
Meghódítani:
Itt kezdjük meg azt a folyamatot, amely az algoritmus nevét adta: összevonás. Ehhez vesszük a kapott két rendezett tömböt, és egyesítjük őket egybe. Ebben az esetben a két tömb első elemei közül a legkisebbet írjuk be a kapott tömbbe. Ezt a műveletet addig ismételjük, amíg a két tömb összes elemét át nem másoljuk. Ez azt jelenti, hogy ha van két minimális tömbünk ({6} és {4}), összehasonlítjuk az értékeket, és létrehozzuk ezt az egyesített eredményt: {4,6}. Ha rendeztük a {4,6} és a {2,8} tömböket, először a 4-es és a 2-es értékeket hasonlítjuk össze, majd írunk 2-t a kapott tömbbe. Ezután a 4-et és a 8-at összehasonlítjuk, majd 4-et írunk. Végül a 6-ot és a 8-at hasonlítjuk össze. Ennek megfelelően 6-ot írunk, és csak ezután írunk 8-at. Ennek eredményeként a következő összevont tömböt kapjuk: {2,4,6,8}. Hogyan fog ez kinézni a Java kódban? Ennek az algoritmusnak a futtatásához kényelmes lesz a rekurzió használata:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
A gyors rendezéshez hasonlóan a rekurzív metódust egy köztes metódusba helyezzük át, így a felhasználónak csak a rendezendő tömböt kell megadnia, és nem kell aggódnia további alapértelmezett argumentumok megadása miatt. Ez az algoritmus hasonlóságokat mutat a gyorsszortírozással, és nem meglepő módon a végrehajtási sebessége is megegyezik: O(N*logN).
2. Mohó algoritmusok
A mohó algoritmus egy olyan megközelítés, ahol minden szakaszban helyileg optimális döntéseket hoznak, azzal a feltételezéssel, hogy a végső megoldás is optimális lesz. Az „optimális” megoldás az lesz, amely a legnyilvánvalóbb és legközvetlenebb hasznot kínálja bármely adott lépésben/szakaszban. Ennek az algoritmusnak a feltárásához vegyünk egy meglehetősen gyakori problémát – a hátizsák problémát. Tegyél úgy, mintha egy pillanatra tolvaj lennél. Éjszaka betörtél egy boltba egy hátizsákkal (hátizsákkal). Előtted van több áru, amit ellophatsz. Ugyanakkor a hátizsákja korlátozott kapacitású. Legfeljebb 30 egységnyi súlyt szállíthat. A legértékesebb árukészletet is el akarja vinni, ami befér a hátizsákba. Hogyan határozod meg, hogy mit rakj a táskádba? Így,
Válassza ki a legdrágább terméket, amelyet még nem vett el.
Ha elfér a hátizsákban, tedd bele. Ha nem, akkor hagyd.
Elloptunk már mindent? Ha nem, akkor térjünk vissza az 1. lépéshez. Ha igen, akkor gyorsan kiszökünk az üzletből, hiszen teljesítettük, amit csináltunk.
Nézzük ezt, de Java-ban. Így fog kinézni az item osztály:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
Nincs itt semmi különös: három mező (név, súly, érték), amelyek meghatározzák a tétel jellemzőit. Ezenkívül, amint láthatja, az Összehasonlítható felület lehetővé teszi a tételek ár szerinti rendezését. Ezután megnézzük a Bag osztályt, amely a hátizsákunkat képviseli:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
A maxWeight a hátizsákunk kapacitása, amelyet az objektum létrehozásakor állítunk be;
tárgyak a hátizsákunkban lévő tárgyakat képviseli;
currentWeight , currentValue — ezek a mezők tárolják a hátizsákban lévő összes elem aktuális súlyát és értékét, amelyet akkor növelünk, ha az addItem metódusban új elemet adunk hozzá.
Na mindegy, most menjünk abba az osztályba, ahol minden cselekmény zajlik:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
Először létrehozunk egy listát az elemekről, és rendezzük azt. 30 egységnyi kapacitású táska tárgyat készítünk. Ezután átadjuk a tárgyakat és a táska tárgyát a fillBackpack metódusnak, amely a mi mohó algoritmusunk szerint kitölti a hátizsákot:
Ez nagyon egyszerű: elkezdjük átnézni a tételek listáját költség szerint rendezve, és betesszük a táskába, ha a kapacitása engedi. Ha nincs elég hely, akkor az elem kimarad, és tovább haladunk a többi elemen, amíg el nem érjük a lista végét. A main futtatása után a következő konzol kimenetet kapjuk:
A hátizsák súlya 29. A hátizsákban lévő tárgyak összértéke 3700
Ez egy példa egy mohó algoritmusra: minden lépésben kiválasztunk egy lokálisan optimális megoldást, és végül egy globálisan optimális megoldást kapunk. Esetünkben a legjobb megoldás a legdrágább tétel. De vajon ez a legjobb megoldás? Nem gondolja, hogy lehetséges egy kicsit javítani a megoldásunkon, hogy a hátizsákunkat megtöltsük olyan tárgyakkal, amelyek összértéke még nagyobb? Nézzük meg, hogyan lehet ezt megtenni.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Itt először kiszámítjuk az egyes tételek érték-súly arányát. Ez megmondja nekünk az adott cikk egyes egységeinek értékét. Aztán ezeket az arányokat használjuk a tárgyak válogatására és a táskánkba való hozzáadására. Futtassuk a következőt:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
Ezt a konzol kimenetet kapjuk:
A hátizsák súlya 29. A hátizsákban lévő tárgyak összköltsége 4150
Egy kicsit jobb, nem? A mohó algoritmus minden lépésnél helyileg optimális választást hoz, remélve, hogy a végső megoldás is optimális lesz. Ez a feltevés nem mindig érvényes, de sok feladatnál a mohó algoritmusok optimális végső megoldást adnak. Ennek az algoritmusnak az időbonyolultsága O(N). Elég jó, mi?
És mivel ezen a webhelyen tartózkodik, olyan merész leszek, hogy feltételezzem, hogy Java nyelven ír. Ezért ma azt javaslom, hogy ismerkedjen meg néhány alapvető algoritmussal és konkrét példákkal, hogyan implementálhatja azokat Java-ban. A "néhány" alatt azt értem, hogy:
GO TO FULL VERSION