Projekty deweloperskie wykorzystują różne algorytmy częściej niż mogłoby się wydawać. Załóżmy na przykład, że musimy posortować niektóre dane według określonych parametrów (kolumn), abyśmy mogli poruszać się po danych bez większego wysiłku. Nie byłoby więc niczym dziwnym, gdyby osoba przeprowadzająca rozmowę kwalifikacyjną zapytała Cię o konkretny podstawowy algorytm i być może dała zadanie zaimplementowania go za pomocą kodu. A ponieważ jesteś na tej stronie, ośmielę się założyć, że piszesz w Javie. Dlatego dzisiaj proponuję zapoznać się z kilkoma podstawowymi algorytmami oraz konkretnymi przykładami ich implementacji w Javie. Przez "niektóre" mam na myśli:
Przegląd algorytmów sortowania tablic:
sortowanie bąbelkowe,
sortowanie przez wybór,
sortowanie przez wstawianie,
sortowanie skorupowe,
szybkie sortowanie,
sortowanie przez scalanie,
Chciwe algorytmy
Algorytmy wyszukiwania ścieżek
przeszukiwanie w głąb
wyszukiwanie wszerz
Algorytm najkrótszej ścieżki Dijkstry
Cóż, bez zbędnych ceregieli, przejdźmy do rzeczy.
1. Przegląd algorytmów sortowania
Sortowanie bąbelkowe
Ten algorytm sortowania znany jest przede wszystkim ze swojej prostoty, ale jest też jednym z najwolniejszych. Jako przykład rozważmy sortowanie bąbelkowe dla liczb w porządku rosnącym. Wyobraźmy sobie losowy ciąg liczb. Wykonamy następujące kroki na tych liczbach, zaczynając od początku sekwencji:
porównaj dwie liczby;
jeśli liczba po lewej stronie jest większa, zamień je;
przesunąć o jedną pozycję w prawo.
Po wykonaniu tych kroków na całej sekwencji stwierdzimy, że największa liczba znajduje się na końcu naszego ciągu liczb. Następnie ponownie przechodzimy przez sekwencję, wykonując dokładnie te same kroki, co powyżej. Ale tym razem nie uwzględnimy ostatniego elementu listy, ponieważ jest to największa liczba i już dokładnie tam, gdzie powinna być podczas sortowania liczb. Ponownie przesuniemy następną największą liczbę na koniec naszej sekwencji. Oczywiście oznacza to, że dwie największe liczby stoją na swoich właściwych miejscach. Ponownie przechodzimy nad sekwencją, wyłączając elementy, które są już na swoich miejscach, aż wszystkie elementy ułożą się w wymaganej kolejności. Przyjrzyjmy się, jak sortowanie bąbelkowe jest zaimplementowane w kodzie Java:
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;
}
}
}
}
}
Jak widać, nie ma tu nic skomplikowanego. Wszystko wydaje się po prostu świetne i byłoby, gdyby nie jedna wada — sortowanie bąbelkowe jest bardzo, bardzo powolne. Złożoność czasowa wynosi O(N²), ponieważ mamy zagnieżdżone pętle. Zewnętrzna pętla nad elementami jest wykonywana N razy. Wewnętrzna pętla jest również wykonywana N razy. W rezultacie otrzymujemy N*N lub N² iteracji.
Sortowanie przez wybór
Ten algorytm jest podobny do sortowania bąbelkowego, ale działa trochę szybciej. Ponownie, jako przykład, weźmy sekwencję liczb, które chcemy ułożyć w porządku rosnącym. Istotą tego algorytmu jest sekwencyjne iterowanie wszystkich liczb i wybranie najmniejszego elementu, który bierzemy i zamieniamy z elementem najbardziej wysuniętym na lewo (elementem 0). Tutaj mamy sytuację podobną do sortowania bąbelkowego, ale w tym przypadku nasz posortowany element będzie najmniejszy. Dlatego następne przejście przez elementy rozpocznie się od elementu o indeksie 1. Będziemy powtarzać te przejścia, aż wszystkie elementy zostaną posortowane. Implementacja w Javie:
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;
}
}
}
Ten algorytm jest lepszy od sortowania bąbelkowego, ponieważ tutaj liczba wymaganych przesunięć jest zmniejszona z O(N²) do O(N). Nie przeprowadzamy jednego elementu przez całą listę, ale liczba porównań nadal wynosi O(N²).
Sortowanie przez wstawianie
Rozważamy kolejną sekwencję liczb, którą chcemy ułożyć w porządku rosnącym. Algorytm ten polega na umieszczeniu znacznika, w którym wszystkie elementy na lewo od znacznika są już częściowo posortowane między sobą. Na każdym kroku algorytmu jeden z elementów zostanie wybrany i umieszczony na żądanej pozycji w częściowo posortowanej sekwencji. W ten sposób posortowana część będzie rosła, dopóki wszystkie elementy nie zostaną zbadane. Zastanawiasz się, w jaki sposób uzyskujesz podzbiór elementów, które są już posortowane i jak określamy, gdzie umieścić znacznik? Ale tablica złożona z pierwszego elementu jest już posortowana, prawda? Rzućmy okiem na implementację w Javie:
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
}
}
}
Ten typ sortowania jest lepszy od opisanych powyżej, ponieważ pomimo tego, że ma taki sam czas działania O(N²), algorytm ten jest dwa razy szybszy niż sortowanie bąbelkowe i nieco szybszy niż sortowanie przez wybieranie.
Sortowanie skorupowe
To sortowanie jest zasadniczo zmodyfikowanym sortowaniem przez wstawianie. o czym ja mówię? Postawmy na pierwszym miejscu. Musimy najpierw wybrać interwał. Istnieje wiele podejść do dokonania tego wyboru. Nie będziemy wdawać się w ten temat zbyt szczegółowo. Podzielmy naszą tablicę na pół i uzyskajmy pewną liczbę — to będzie nasz przedział. Tak więc, jeśli mamy 9 elementów w naszej tablicy, to nasz przedział będzie wynosił 9/2 = 4,5. Odrzucamy część ułamkową i otrzymujemy 4, ponieważ indeksy tablicy mogą być tylko liczbami całkowitymi. Wykorzystamy ten odstęp czasu do utworzenia naszych grup. Jeśli element ma indeks 0, to indeks następnego elementu w jego grupie to 0+4, czyli 4. Trzeci element będzie miał indeks 4+4, czwarty — 8+4 i tak dalej. W drugiej grupie pierwszym elementem będzie 1,5,9... W trzeciej i czwartej grupie sytuacja będzie taka sama. W rezultacie, z tablicy liczbowej {6,3,8,8,6,9,4,11,1} otrzymujemy cztery grupy: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Zachowują swoje miejsca w tablicy ogólnej, ale zaznaczyliśmy jako członków tej samej grupy: {6,3,8,8,6,9,4,11,1} Następnie wstawienie sortowanie jest stosowane do tych grup, a następnie wyglądają one tak: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} W tablicy ogólnej komórki zajmowane przez grupy pozostaną takie same, ale ich wewnętrzna kolejność ulegnie zmianie, zgodnie z kolejnością grup powyżej: {1,3,4,8,6,9,8,11,6} Tablica stała się trochę bardziej uporządkowane, prawda? Następny przedział zostanie podzielony przez 2: 4/2 = 2 Mamy dwie grupy: I — {1,4,6,8,6} II — {3,8,9,11} W ogólnej tablicy mamy : {1,3,4,8,6,9,8,11,6} Uruchamiamy algorytm sortowania przez wstawianie dla obu grup i otrzymujemy następującą tablicę: {1,3,4,8,6,9,6, 11, 8} Teraz nasza tablica jest prawie posortowana. Musimy wykonać ostatnią iterację algorytmu: dzielimy przedział przez 2: 2/2 = 1. Otrzymujemy grupę złożoną z całej tablicy: {1,3,4,8,6,9,6,11 ,8} Uruchamiając algorytm sortowania przez wstawianie, otrzymujemy: {1,3,4,6,6,8,8,9,11} Przyjrzyjmy się, jak możemy ożywić to sortowanie w kodzie Java:
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
}
}
}
W tej chwili wydajność Shellsort nie jest łatwa do scharakteryzowania, ponieważ wyniki różnią się w różnych sytuacjach. Szacunki eksperymentalne wahają się od O(N 3/2 ) do O(N 7/6 ).
Szybkie sortowanie
Jest to jeden z najpopularniejszych algorytmów, dlatego warto zwrócić na niego szczególną uwagę. Istotą tego algorytmu jest wybranie elementu obrotowego z listy elementów. Sortujemy wszystkie pozostałe elementy względem elementu przestawnego. Wartości mniejsze niż element obrotowy znajdują się po lewej stronie. Wartości większe niż są po prawej stronie. Następnie wybierane są również elementy przestawne w prawej i lewej części i dzieje się to samo: wartości są sortowane względem tych elementów. Następnie wybierane są elementy obrotowe w nowo uformowanych częściach i tak dalej, aż otrzymamy posortowaną sekwencję. Poniższa implementacja tego algorytmu w Javie wykorzystuje rekursję:
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);
}
}
Bez wątpienia algorytm quicksort jest najpopularniejszy, ponieważ w większości sytuacji działa szybciej niż inne. Jego złożoność czasowa wynosi O(N*logN).
Sortuj przez scalanie
Ten rodzaj jest również popularny. Jest to jeden z wielu algorytmów, który opiera się na zasadzie „dziel i zwyciężaj”. Takie algorytmy najpierw dzielą problem na części, którymi można zarządzać (szybkie sortowanie jest kolejnym przykładem takiego algorytmu). Jaka jest więc istota tego algorytmu?
Dzielić:
Tablica jest podzielona na dwie części o mniej więcej tej samej wielkości. Każda z tych dwóch części jest podzielona na dwie kolejne i tak dalej, aż pozostaną najmniejsze możliwe niepodzielne części. Najmniejsze niepodzielne części mamy wtedy, gdy każda tablica ma jeden element, czyli tablicę już posortowaną.
Podbić:
W tym miejscu rozpoczynamy proces, który nadał algorytmowi swoją nazwę: scalanie. Aby to zrobić, bierzemy dwie wynikowe posortowane tablice i łączymy je w jedną. W tym przypadku najmniejszy z pierwszych elementów dwóch tablic jest zapisywany w wynikowej tablicy. Ta operacja jest powtarzana, aż wszystkie elementy w tych dwóch tablicach zostaną skopiowane. Oznacza to, że jeśli mamy dwie minimalne tablice {6} i {4}, porównujemy ich wartości i generujemy ten połączony wynik: {4,6}. Jeśli mamy posortowane tablice {4,6} i {2,8}, najpierw porównujemy wartości 4 i 2, a następnie wpisujemy 2 do wynikowej tablicy. Następnie porównamy 4 i 8 i zapiszemy 4. Na koniec porównamy 6 i 8. W związku z tym zapiszemy 6, a dopiero potem zapiszemy 8. W rezultacie otrzymamy następującą tablicę scaloną: {2,4,6,8}. Jak to będzie wyglądać w kodzie Java? Aby uruchomić ten algorytm, wygodnie będzie nam użyć rekurencji:
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;
}
}
Podobnie jak w przypadku sortowania szybkiego, przenosimy metodę rekurencyjną do metody pośredniej, dzięki czemu użytkownik musi tylko podać tablicę do posortowania i nie musi się martwić o podanie żadnych dodatkowych domyślnych argumentów. Algorytm ten jest podobny do algorytmu szybkiego sortowania i, jak można się było spodziewać, jego szybkość wykonania jest taka sama: O(N*logN).
2. Algorytmy zachłanne
Algorytm zachłanny to podejście, w którym na każdym etapie podejmowane są lokalnie optymalne decyzje, przy założeniu, że ostateczne rozwiązanie również będzie optymalne. „Optymalne” rozwiązanie to takie, które oferuje najbardziej oczywiste i natychmiastowe korzyści na każdym konkretnym etapie/etapie. Aby zbadać ten algorytm, weźmy dość powszechny problem — problem plecakowy. Udawaj przez chwilę, że jesteś złodziejem. Włamałeś się w nocy do sklepu z plecakiem. Przed tobą kilka towarów, które możesz ukraść. Ale jednocześnie twój plecak ma ograniczoną pojemność. Może przenosić nie więcej niż 30 jednostek wagi. Chcesz też wywieźć ze sobą najcenniejszy zestaw towarów, który zmieści się do plecaka. Jak określić, co włożyć do torby? Więc,
Wybierz najdroższy przedmiot, który nie został jeszcze zabrany.
Jeśli zmieści się do plecaka, włóż go. Jeśli nie, to zostaw.
Czy ukradliśmy już wszystko? Jeśli nie, wracamy do kroku 1. Jeśli tak, to szybko uciekamy ze sklepu, ponieważ osiągnęliśmy to, po co przyszliśmy.
Spójrzmy na to, ale w Javie. Tak będzie wyglądać klasa Item:
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;
}
}
Nie ma tu nic specjalnego: trzy pola (nazwa, waga, wartość) określające cechy przedmiotu. Ponadto, jak widać, interfejs Porównywalny został zaimplementowany, aby umożliwić nam sortowanie naszych produktów według ceny. Następnie przyjrzymy się klasie Bag, która reprezentuje nasz plecak:
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();
}
}
maxWeight to pojemność naszego plecaka, którą ustalamy podczas tworzenia obiektu;
items reprezentuje obiekty w naszym plecaku;
currentWeight , currentValue — te pola przechowują aktualną wagę i wartość wszystkich przedmiotów w plecaku, którą zwiększamy dodając nowy przedmiot w metodzie addItem.
W każdym razie przejdźmy teraz do klasy, w której toczy się cała akcja:
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());
}
}
Najpierw tworzymy listę elementów i sortujemy ją. Tworzymy obiekt typu worek o pojemności 30 jednostek. Następnie przekazujemy przedmioty i obiekt bag do metody fillBackpack, która zapełnia plecak zgodnie z naszym zachłannym algorytmem:
To całkiem proste: zaczynamy przeglądać listę przedmiotów posortowanych według kosztów i umieszczać je w torbie, jeśli jej pojemność na to pozwala. Jeśli nie ma wystarczającej ilości miejsca, element zostanie pominięty i będziemy przeglądać pozostałe elementy, aż dotrzemy do końca listy. Gdy uruchomimy main, oto dane wyjściowe konsoli, które otrzymamy:
Waga plecaka to 29. Łączna wartość przedmiotów w plecaku to 3700
To jest przykład algorytmu zachłannego: na każdym kroku wybierane jest rozwiązanie optymalne lokalnie, a na koniec otrzymuje się rozwiązanie optymalne globalnie. W naszym przypadku najlepszą opcją jest najdroższy przedmiot. Ale czy to najlepsze rozwiązanie? Nie sądzisz, że można nieco ulepszyć nasze rozwiązanie, aby zapełnić nasz plecak przedmiotami o jeszcze większej wartości całkowitej? Przyjrzyjmy się, jak można to zrobić.
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());
}
}
}
Tutaj najpierw obliczamy stosunek wartości do wagi dla każdej pozycji. Mówi nam to o wartości każdej jednostki danego przedmiotu. Następnie używamy tych proporcji do sortowania naszych przedmiotów i dodawania ich do naszej torby. Uruchommy następujące:
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());
Otrzymujemy to wyjście konsoli:
Waga plecaka to 29. Całkowity koszt przedmiotów w plecaku to 4150
Trochę lepiej, prawda? Algorytm zachłanny na każdym kroku dokonuje lokalnie optymalnego wyboru, mając nadzieję, że ostateczne rozwiązanie również będzie optymalne. To założenie nie zawsze jest słuszne, ale w przypadku wielu zadań algorytmy zachłanne dają optymalne rozwiązanie końcowe. Złożoność czasowa tego algorytmu wynosi O(N). Nieźle, co?
A ponieważ jesteś na tej stronie, ośmielę się założyć, że piszesz w Javie. Dlatego dzisiaj proponuję zapoznać się z kilkoma podstawowymi algorytmami oraz konkretnymi przykładami ich implementacji w Javie. Przez "niektóre" mam na myśli:
GO TO FULL VERSION