Proyek pangembangan nggunakake macem-macem algoritma luwih kerep tinimbang sing sampeyan pikirake. Contone, umpamane kita kudu ngurutake sawetara data kanthi paramèter tartamtu (kolom) supaya bisa navigasi liwat data tanpa gaweyan. Dadi ora aneh yen pewawancara kerja takon babagan algoritma dhasar tartamtu lan bisa uga menehi tugas kanggo ngetrapake nggunakake kode. Lan amarga sampeyan ana ing situs web iki, aku bakal kendel banget nganggep yen sampeyan nulis ing basa Jawa. Pramila dina iki aku menehi saran supaya sampeyan ngerti sawetara algoritma dhasar lan conto khusus babagan cara ngetrapake ing Jawa. Miturut "sawetara", maksudku:
Ringkesan algoritma ngurutake array:
jinis gelembung,
jinis pilihan,
urut-urutan sisipan,
Jenis cangkang,
quicksort,
merge sort,
Algoritma rakus
Algoritma Pathfinding
depth-first search
telusuran jembar-pisanan
Algoritma Shortest Path First Dijkstra
Inggih, tanpa ado maneh, ayo padha mudhun menyang bisnis.
1. Ringkesan algoritma ngurutake
Urut gelembung
Algoritma ngurutake iki dikenal utamane amarga kesederhanaan, nanging uga minangka salah sawijining sing paling alon. Minangka conto, ayo nimbang urutan gelembung kanggo nomer kanthi urutan munggah. Ayo mbayangno urutan nomer acak. Kita bakal nindakake langkah-langkah ing ngisor iki kanggo nomer kasebut, wiwit saka wiwitan urutan:
mbandhingaké rong nomer;
yen nomer ing sisih kiwa luwih gedhe, banjur ganti;
mindhah siji posisi menyang tengen.
Sawise nindakake langkah-langkah kasebut ing kabeh urutan, kita bakal nemokake manawa nomer paling gedhe ana ing pungkasan seri nomer. Banjur kita nggawe pass liyane liwat urutan, nglakokaké persis langkah padha ing ndhuwur. Nanging wektu iki kita ora bakal kalebu unsur pungkasan saka dhaftar, awit iku nomer paling gedhe lan wis persis ngendi iku kudu nalika nomer diurutake. Sawise maneh, kita bakal mindhah nomer paling gedhe sabanjure menyang mburi urutan kita. Mesthi, tegese rong nomer paling gedhe ngadeg ing papan sing cocog. Maneh, kita nggawe pass liwat urutan, ora kalebu unsur-unsur sing wis ana ing panggonane, nganti kabeh unsur ana ing urutan sing dibutuhake. Ayo goleki carane ngurutake gelembung ing kode Jawa:
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;
}
}
}
}
}
Nalika sampeyan bisa ndeleng, ora ana sing rumit ing kene. Kabeh katon apik lan bakal dadi yen ora ana kekurangan - jinis gelembung alon banget. Kerumitan wektu iku O(N²), amarga kita duwe puteran nested. Puteran njaba liwat unsur ditindakake N kaping. Daur ulang internal uga dieksekusi kaping N. Akibaté, kita entuk N*N, utawa N², iterasi.
Urut pilihan
Algoritma iki padha karo urutan gelembung, nanging kerjane luwih cepet. Maneh, minangka conto, ayo njupuk urutan nomer sing arep kita atur ing urutan munggah. Inti saka algoritma iki yaiku kanthi urutan ngulang kabeh nomer lan milih unsur sing paling cilik, sing dijupuk lan diganti karo unsur paling kiwa (unsur 0). Ing kene kita duwe kahanan sing padha karo urutan gelembung, nanging ing kasus iki unsur sing diurutake bakal dadi sing paling cilik. Mulane, pass sabanjuré liwat unsur bakal miwiti saka unsur karo indeks 1. Kita bakal mbaleni pass iki nganti kabeh unsur wis diurutake. Implementasine ing Jawa:
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;
}
}
}
Algoritma iki luwih unggul tinimbang ngurutake gelembung, amarga ing kene jumlah owah-owahan sing dibutuhake dikurangi saka O(N²) dadi O(N). Kita ora nyopir siji unsur ing kabeh dhaptar, nanging jumlah mbandhingake isih O(N²).
Urut selipan
Kita nimbang urutan nomer liyane sing pengin diatur kanthi urutan munggah. Algoritma iki kalebu nempatake panandha, ing ngendi kabeh unsur ing sisih kiwa tandha wis diurutake sebagian. Ing saben langkah algoritma, salah sawijining unsur bakal dipilih lan diselehake ing posisi sing dikarepake ing urutan sing diurutake sebagian. Mangkono, bagean sing diurutake bakal tuwuh nganti kabeh unsur wis ditliti. Apa sampeyan kepingin weruh carane njaluk subset saka unsur sing wis diurutake lan carane kita nemtokake ngendi kanggo nyelehake panandha? Nanging array sing kasusun saka unsur pisanan wis diurutake, ta? Ayo ndeleng implementasine ing Jawa:
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
}
}
}
Jinis jinis iki luwih unggul tinimbang sing kasebut ing ndhuwur, amarga senadyan kasunyatane nduweni wektu O(N²) sing padha, algoritma iki kaping pindho luwih cepet tinimbang urutan gelembung lan rada luwih cepet tinimbang urutan pilihan.
Urut cangkang
Urut iki ateges urutan sisipan sing diowahi. Aku ngomong apa? Ayo dadi luwih dhisik. Pisanan kita kudu milih interval. Ana akeh pendekatan kanggo nggawe pilihan iki. Kita ora bakal rinci babagan iki. Ayo dibagi dadi setengah lan entuk sawetara nomer - iki bakal dadi interval kita. Dadi, yen kita duwe 9 unsur ing array kita, interval kita bakal dadi 9/2 = 4.5. Kita mbuwang bagean pecahan lan entuk 4, amarga indeks array mung bisa dadi integer. Kita bakal nggunakake interval iki kanggo mbentuk grup kita. Yen unsur duwe indeks 0, banjur indeks saka unsur sabanjuré ing klompok sawijining 0 + 4, yaiku, 4. Unsur katelu bakal duwe indeks 4 + 4, papat - 8 + 4, lan ing. Ing klompok kapindho, unsur pisanan bakal dadi 1,5,9 ... Ing klompok katelu lan papat, kahanan bakal padha. Akibate, saka larik nomer {6,3,8,8,6,9,4,11,1} entuk papat klompok: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Padha tetep panggonan ing array umum, nanging kita wis ditandhani minangka anggota saka grup padha: {6,3,8,8,6,9,4,11,1} Sabanjure, sisipan Urut ditrapake kanggo grup kasebut, banjur katon kaya iki: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Ing susunan umum, sel sing dikuwasani klompok bakal tetep padha, nanging urutan internal bakal owah, miturut urutan klompok ing ndhuwur: {1,3,4,8,6,9,8,11,6} Array wis dadi a sethitik liyane dhawuh, wis ora iku? Interval sabanjure bakal dibagi 2: 4/2 = 2 Kita duwe rong klompok: I - {1,4,6,8,6} II - {3,8,9,11} Ing array umum, kita duwe : {1,3,4,8,6,9,8,11,6} Kita mbukak algoritma ngurutake sisipan ing loro grup, lan entuk array iki: {1,3,4,8,6,9,6, 11, 8} Saiki array kita meh diurutake. Kita kudu nindakake pengulangan pungkasan saka algoritma: kita dibagi interval kanthi 2: 2/2 = 1. Kita entuk klompok sing dumadi saka kabeh array: {1,3,4,8,6,9,6,11 ,8} Nglakokake algoritma ngurutake sisipan kasebut, kita entuk: {1,3,4,6,6,8,8,9,11} Ayo goleki kepiye carane bisa urip ing kode Jawa:
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
}
}
}
Ing wayahe, kinerja Shellsort ora gampang kanggo ciri, amarga asil beda-beda ing kahanan beda. Prakiraan eksperimen saka O(N 3/2 ) nganti O(N 7/6 ).
Quicksort
Iki minangka salah sawijining algoritma sing paling populer, mula kudu diwenehi perhatian khusus. Inti saka algoritma iki yaiku unsur pivot dipilih ing dhaptar unsur. Kita ngurutake kabeh unsur liyane sing ana gandhengane karo unsur poros. Nilai kurang saka unsur poros ana ing sisih kiwa. Nilai sing luwih gedhe tinimbang sing ana ing sisih tengen. Sabanjure, unsur poros uga dipilih ing sisih tengen lan kiwa, lan kedadeyan sing padha: nilai diurutake relatif marang unsur kasebut. Banjur unsur pivot dipilih ing bagean sing mentas dibentuk, lan sateruse nganti entuk urutan sing diurutake. Implementasi Java ing algoritma iki nggunakake rekursi:
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);
}
}
Tanpa mangu-mangu, algoritma quicksort paling populer, amarga ing umume kahanan mlaku luwih cepet tinimbang liyane. Kompleksitas wektu yaiku O(N*logN).
Gabung urut
Jenis iki uga populer. Iku salah siji saka akeh algoritma sing gumantung ing prinsip "dibagi lan nelukake". Algoritma kasebut pisanan mbagi masalah dadi bagean sing bisa diatur (quicksort minangka conto liyane saka algoritma kasebut). Dadi apa inti saka algoritma iki?
dibagi:
Array dipérang dadi rong bagéan kanthi ukuran sing kira-kira padha. Saben rong bagéyan iki dipérang dadi loro manèh, lan saterusé nganti tetep dadi bagéan sing paling cilik sing ora bisa dibagi. Kita duwe bagean paling cilik sing ora bisa dibagi nalika saben larik duwe siji unsur, yaiku larik sing wis diurutake.
nelukake:
Iki ngendi kita miwiti proses sing menehi algoritma jenenge: gabung. Kanggo nindakake iki, njupuk loro larik diurutake asil lan gabungke dadi siji. Ing kasus iki, unsur paling cilik saka rong larik ditulis ing larik asil. Operasi iki diulang nganti kabeh unsur ing rong susunan kasebut wis disalin. Yaiku, yen kita duwe rong larik minimal {6} lan {4}, kita mbandhingake nilai-nilai kasebut lan ngasilake asil gabungan iki: {4,6}. Yen kita wis ngurutake array {4,6} lan {2,8}, kita mbandhingake nilai 4 lan 2 dhisik, banjur nulis 2 menyang array sing diasilake. Sawise iku, 4 lan 8 bakal dibandhingake, lan kita bakal nulis 4. Pungkasan, 6 lan 8 bakal dibandhingake. Patut, kita bakal nulis 6, lan mung sawise iku kita bakal nulis 8. Akibaté, kita entuk array gabungan ing ngisor iki: {2,4,6,8}. Kepiye carane iki katon ing kode Jawa? Kanggo mbukak algoritma iki, bakal luwih trep kanggo nggunakake rekursi:
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;
}
}
Kaya ing Urut cepet, kita mindhah cara rekursif menyang cara penengah supaya pangguna mung perlu kanggo nyuplai array kanggo diurutake lan ora perlu kuwatir kanggo nyedhiyani sembarang bantahan standar tambahan. Algoritma iki nduweni podho karo quicksort, lan ora kaget kacepetan eksekusi padha: O(N*logN).
2. Algoritma rakus
Algoritma rakus minangka pendekatan ing ngendi keputusan optimal lokal digawe ing saben tahapan, kanthi asumsi yen solusi pungkasan uga bakal optimal. Solusi "optimal" bakal dadi solusi sing menehi keuntungan sing paling jelas lan langsung ing langkah / tahap tartamtu. Kanggo njelajah algoritma iki, ayo goleki masalah sing umum - masalah knapsack. Sedhela pura-pura yen sampeyan maling. Sampeyan wis bejat menyang toko ing wayah wengi karo knapsack (ransel). Ing ngarep sampeyan ana sawetara barang sing bisa dicolong. Nanging ing wektu sing padha, knapsack sampeyan duwe kapasitas winates. Bisa nggawa ora luwih saka 30 unit bobot. Sampeyan uga pengin nggawa barang sing paling larang regane sing pas karo tas ransel. Kepiye carane sampeyan nemtokake apa sing bakal dilebokake ing tas sampeyan? Dadi,
Pilih barang sing paling larang sing durung dijupuk.
Yen pas karo knapsack, lebokna. Yen ora, tinggalake.
Apa kita wis nyolong kabeh? Yen ora, kita bali menyang langkah 1. Yen ya, banjur kita cepet-cepet lunga saka toko, amarga kita wis ngrampungake apa sing kudu ditindakake.
Ayo dideleng iki, nanging ing Jawa. Mangkene carane kelas Item bakal katon:
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;
}
}
Ora ana sing khusus ing kene: telung kolom (jeneng, bobot, nilai) sing nemtokake karakteristik barang kasebut. Uga, sampeyan bisa ndeleng, antarmuka Comparable diimplementasikake kanggo ngidini kita ngurutake Barang miturut rega. Sabanjure, kita bakal ndeleng kelas Bag, sing nuduhake knapsack kita:
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 minangka kapasitas tas ransel, sing disetel nalika nggawe obyek;
item makili obyek ing tas ransel kita;
currentWeight , currentValue — kothak iki nyimpen bobot saiki lan nilai kabeh item ing tas ransel, kang nambah nalika kita nambah item anyar ing cara addItem.
Oalah, ayo saiki menyang kelas ing ngendi kabeh tumindak ditindakake:
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());
}
}
Pisanan, kita nggawe dhaptar item lan ngurutake. Kita nggawe obyek tas kanthi kapasitas 30 unit. Sabanjure, kita ngirim barang lan obyek tas menyang metode fillBackpack, sing ngisi knapsack miturut algoritma rakus:
Iku cukup prasaja: kita miwiti liwat dhaptar item diurutake miturut biaya lan sijine menyang tas yen kapasitas ngidini. Yen kamar ora cukup, item kasebut bakal dilewati lan kita bakal terus ngliwati item liyane nganti tekan pungkasan dhaptar. Sawise kita mbukak utama, iki output konsol sing bakal kita entuk:
Bobot knapsack yaiku 29. Nilai total barang ing knapsack yaiku 3700
Iki minangka conto algoritma rakus: ing saben langkah, solusi optimal lokal dipilih, lan ing pungkasan, sampeyan entuk solusi sing optimal sacara global. Ing kasus kita, pilihan sing paling apik yaiku barang sing paling larang. Nanging iki solusi sing paling apik? Apa sampeyan ora mikir manawa bisa nambah solusi supaya bisa ngisi tas ransel karo barang-barang sing duwe nilai total sing luwih gedhe? Ayo dipikirake carane iki bisa ditindakake.
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());
}
}
}
Ing kene kita ngetung rasio nilai-kanggo-bobot kanggo saben item. Iki ngandhani nilai saben unit item tartamtu. Banjur kita nggunakake rasio iki kanggo ngurutake barang lan ditambahake menyang tas. Ayo mlaku ing ngisor iki:
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());
Kita entuk output konsol iki:
Bobot knapsack yaiku 29. Total biaya barang ing knapsack yaiku 4150.
Luwih apik, ta? Algoritma rakus nggawe pilihan sing optimal sacara lokal ing saben langkah, ngarep-arep yen solusi pungkasan uga optimal. Asumsi iki ora mesthi bener, nanging kanggo akeh tugas, algoritma rakus ngasilake solusi final sing paling optimal. Kompleksitas wektu algoritma iki yaiku O (N). Cukup apik, huh?
Lan amarga sampeyan ana ing situs web iki, aku bakal kendel banget nganggep yen sampeyan nulis ing basa Jawa. Pramila dina iki aku menehi saran supaya sampeyan ngerti sawetara algoritma dhasar lan conto khusus babagan cara ngetrapake ing Jawa. Miturut "sawetara", maksudku:
GO TO FULL VERSION