Proyek pengembangan menggunakan berbagai algoritme lebih sering daripada yang Anda kira. Misalnya, kita perlu mengurutkan beberapa data berdasarkan parameter (kolom) tertentu sehingga kita dapat menavigasi data tanpa banyak usaha. Jadi tidak aneh sama sekali jika pewawancara kerja bertanya kepada Anda tentang algoritma dasar tertentu dan mungkin memberikan tugas untuk mengimplementasikannya menggunakan kode. Dan karena Anda berada di situs web ini, saya berani berasumsi bahwa Anda menulis dalam bahasa Jawa. Itu sebabnya hari ini saya menyarankan agar Anda membiasakan diri dengan beberapa algoritme dasar dan contoh spesifik tentang cara mengimplementasikannya di Java. Dengan "beberapa", maksud saya:
Gambaran umum algoritma pengurutan array:
semacam gelembung,
pengurutan seleksi,
semacam penyisipan,
Semacam cangkang,
pengurutan cepat,
mengurutkan gabungan,
Algoritma serakah
Algoritma pencarian jalan
pencarian kedalaman-pertama
pencarian luas-pertama
Algoritma Shortest Path First Dijkstra
Baiklah, tanpa basa-basi lagi, mari kita langsung ke bisnis.
1. Tinjauan tentang algoritma pengurutan
Semacam gelembung
Algoritme pengurutan ini dikenal terutama karena kesederhanaannya, tetapi juga merupakan salah satu yang paling lambat. Sebagai contoh, mari pertimbangkan pengurutan gelembung untuk angka dalam urutan menaik. Bayangkan urutan angka acak. Kami akan melakukan langkah-langkah berikut pada angka-angka ini, mulai dari awal urutan:
membandingkan dua angka;
jika angka di sebelah kiri lebih besar, maka tukarkan;
pindah satu posisi ke kanan.
Setelah melakukan langkah-langkah ini di seluruh urutan, kita akan menemukan bahwa angka terbesar ada di akhir rangkaian angka kita. Kemudian kami membuat urutan lain melewati, menjalankan langkah-langkah yang persis sama seperti di atas. Tapi kali ini kita tidak akan menyertakan elemen terakhir dari daftar, karena ini adalah angka terbesar dan sudah tepat berada di tempat yang seharusnya saat angka diurutkan. Sekali lagi, kita akan memindahkan angka terbesar berikutnya ke akhir urutan kita. Tentu saja, itu berarti dua angka terbesar berdiri di tempatnya masing-masing. Sekali lagi, kami melewati urutan, mengecualikan elemen yang sudah ada di tempatnya, hingga semua elemen berada dalam urutan yang diperlukan. Mari kita lihat bagaimana bubble sort diimplementasikan dalam kode 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;
}
}
}
}
}
Seperti yang Anda lihat, tidak ada yang rumit di sini. Segalanya tampak hebat dan itu akan terjadi jika bukan karena satu kekurangan - bubble sort sangat, sangat lambat. Kompleksitas waktunya adalah O(N²), karena kita memiliki loop bersarang. Loop luar atas elemen dilakukan N kali. Loop bagian dalam juga dieksekusi N kali. Hasilnya, kita mendapatkan iterasi N*N, atau N².
Sortir seleksi
Algoritme ini mirip dengan pengurutan gelembung, tetapi bekerja sedikit lebih cepat. Sekali lagi, sebagai contoh, mari kita ambil urutan angka yang ingin kita susun dalam urutan menaik. Inti dari algoritme ini adalah untuk mengulangi semua angka secara berurutan dan memilih elemen terkecil, yang kami ambil dan tukar dengan elemen paling kiri (elemen ke-0). Di sini kita memiliki situasi yang mirip dengan pengurutan gelembung, tetapi dalam kasus ini elemen terurut kita akan menjadi yang terkecil. Oleh karena itu, melewati elemen selanjutnya akan dimulai dari elemen dengan indeks 1. Kami akan mengulangi langkah ini sampai semua elemen telah diurutkan. Implementasi di 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 ini lebih unggul dari bubble sort, karena di sini jumlah shift yang dibutuhkan berkurang dari O(N²) menjadi O(N). Kami tidak mengarahkan satu elemen ke seluruh daftar, tetapi jumlah perbandingannya masih O(N²).
Sortir penyisipan
Kami mempertimbangkan urutan angka lain yang ingin kami atur dalam urutan menaik. Algoritme ini terdiri dari penempatan penanda, di mana semua elemen di sebelah kiri penanda sudah disortir sebagian di antara mereka sendiri. Pada setiap langkah algoritma, salah satu elemen akan dipilih dan ditempatkan pada posisi yang diinginkan dalam urutan yang diurutkan sebagian. Dengan demikian, bagian yang disortir akan tumbuh hingga semua elemen diperiksa. Apakah Anda bertanya-tanya bagaimana Anda mendapatkan subset elemen yang sudah disortir dan bagaimana kami menentukan di mana harus meletakkan penanda? Tapi array yang terdiri dari elemen pertama sudah diurutkan, bukan? Mari kita lihat implementasinya di Java:
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
}
}
}
Jenis pengurutan ini lebih unggul daripada yang dijelaskan di atas, karena meskipun memiliki waktu pengoperasian O(N²) yang sama, algoritme ini dua kali lebih cepat dari pengurutan gelembung dan sedikit lebih cepat daripada pengurutan seleksi.
Semacam cangkang
Jenis ini pada dasarnya adalah jenis penyisipan yang dimodifikasi. Apa yang saya bicarakan? Mari kita mengutamakan hal-hal pertama. Pertama-tama kita harus memilih interval. Ada banyak pendekatan untuk membuat pilihan ini. Kami tidak akan membahas terlalu banyak detail tentang ini. Mari kita membagi array kita menjadi dua dan mendapatkan beberapa angka — ini akan menjadi interval kita. Jadi, jika kita memiliki 9 elemen dalam array kita, maka interval kita adalah 9/2 = 4,5. Kami membuang bagian pecahan dan mendapatkan 4, karena indeks array hanya bisa berupa bilangan bulat. Kami akan menggunakan interval ini untuk membentuk grup kami. Jika suatu elemen memiliki indeks 0, maka indeks elemen berikutnya dalam grupnya adalah 0+4, yaitu 4. Elemen ketiga akan memiliki indeks 4+4, elemen keempat — 8+4, dan seterusnya. Di grup kedua, elemen pertama adalah 1,5,9... Di grup ketiga dan keempat, situasinya akan sama. Sebagai akibat, dari larik bilangan {6,3,8,8,6,9,4,11,1} didapat empat golongan: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Mereka mempertahankan tempat mereka di array umum, tetapi kami telah menandai sebagai anggota grup yang sama: {6,3,8,8,6,9,4,11,1} Selanjutnya, penyisipan sort diterapkan ke grup ini, dan kemudian terlihat seperti ini: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Dalam larik umum, sel yang ditempati oleh grup akan tetap sama, tetapi urutan internalnya akan berubah, sesuai dengan urutan grup di atas: {1,3,4,8,6,9,8,11,6} Array telah menjadi sedikit lebih banyak dipesan, bukan? Interval berikutnya akan dibagi dengan 2: 4/2 = 2 Kita memiliki dua grup: I — {1,4,6,8,6} II — {3,8,9,11} Dalam larik umum, kita memiliki : {1,3,4,8,6,9,8,11,6} Kami menjalankan algoritma insertion sort pada kedua grup, dan mendapatkan array ini: {1,3,4,8,6,9,6, 11, 8} Sekarang array kita hampir terurut. Kita perlu melakukan iterasi terakhir dari algoritme: kita membagi interval dengan 2: 2/2 = 1. Kita mendapatkan grup yang terdiri dari seluruh larik: {1,3,4,8,6,9,6,11 ,8} Dengan menjalankan algoritme pengurutan penyisipan, kita mendapatkan: {1,3,4,6,6,8,8,9,11} Mari kita lihat bagaimana kita dapat menghidupkan pengurutan ini dalam kode 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
}
}
}
Saat ini, kinerja Shellsort tidak mudah dicirikan, karena hasilnya berbeda dalam situasi yang berbeda. Estimasi eksperimental berkisar dari O(N 3/2 ) hingga O(N 7/6 ).
Quicksort
Ini adalah salah satu algoritme paling populer, jadi perlu diperhatikan secara khusus. Inti dari algoritma ini adalah elemen pivot dipilih dalam daftar elemen. Kami mengurutkan semua elemen lain relatif terhadap elemen pivot. Nilai yang kurang dari elemen pivot ada di sebelah kiri. Nilai lebih besar dari itu ada di sebelah kanan. Selanjutnya, elemen pivot juga dipilih di bagian kanan dan kiri, dan hal yang sama terjadi: nilainya diurutkan relatif terhadap elemen ini. Kemudian elemen pivot dipilih di bagian yang baru dibentuk, dan seterusnya hingga kita mendapatkan urutan yang terurut. Implementasi Java berikut dari algoritma ini menggunakan 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);
}
}
Tidak diragukan lagi, algoritma quicksort adalah yang paling populer, karena dalam banyak situasi ia bekerja lebih cepat daripada yang lain. Kompleksitas waktunya adalah O(N*logN).
Menggabungkan mengurutkan
Jenis ini juga populer. Ini adalah salah satu dari banyak algoritma yang mengandalkan prinsip "membagi dan menaklukkan". Algoritme semacam itu pertama-tama membagi masalah menjadi bagian-bagian yang dapat dikelola (quicksort adalah contoh lain dari algoritme semacam itu). Jadi apa inti dari algoritma ini?
Membagi:
Array dibagi menjadi dua bagian dengan ukuran yang kira-kira sama. Masing-masing dari dua bagian ini dibagi menjadi dua lagi, dan seterusnya hingga bagian terkecil yang mungkin tidak dapat dibagi tetap ada. Kami memiliki bagian terkecil yang tidak dapat dibagi ketika setiap array memiliki satu elemen, yaitu array yang sudah diurutkan.
Menaklukkan:
Di sinilah kita memulai proses yang memberi nama algoritme: penggabungan. Untuk melakukan ini, kami mengambil dua array terurut yang dihasilkan dan menggabungkannya menjadi satu. Dalam hal ini, elemen pertama terkecil dari dua larik ditulis ke dalam larik yang dihasilkan. Operasi ini diulang sampai semua elemen dalam dua larik ini telah disalin. Artinya, jika kita memiliki dua larik minimal {6} dan {4}, kita membandingkan nilainya dan menghasilkan hasil gabungan ini: {4,6}. Jika kita telah mengurutkan larik {4,6} dan {2,8}, pertama-tama kita membandingkan nilai 4 dan 2, lalu menulis 2 ke dalam larik yang dihasilkan. Setelah itu, 4 dan 8 akan dibandingkan, dan kita akan menulis 4. Terakhir, 6 dan 8 akan dibandingkan. Oleh karena itu, kita akan menulis 6, dan hanya setelah itu kita akan menulis 8. Hasilnya, kita mendapatkan larik gabungan berikut: {2,4,6,8}. Bagaimana tampilannya dalam kode Java? Untuk menjalankan algoritme ini, akan lebih mudah bagi kita untuk menggunakan 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;
}
}
Seperti dalam penyortiran cepat, kami memindahkan metode rekursif ke metode perantara sehingga pengguna hanya perlu menyediakan array yang akan diurutkan dan tidak perlu khawatir tentang memberikan argumen default tambahan. Algoritme ini memiliki kemiripan dengan quicksort, dan tidak mengherankan jika kecepatan eksekusinya sama: O(N*logN).
2. Algoritma serakah
Algoritma serakah adalah pendekatan di mana keputusan optimal lokal dibuat pada setiap tahap, dengan asumsi bahwa solusi akhir juga akan optimal. Solusi "optimal" adalah solusi yang menawarkan manfaat paling jelas dan langsung pada setiap langkah/tahapan tertentu. Untuk mempelajari algoritme ini, mari kita ambil masalah yang cukup umum — masalah knapsack. Berpura-pura sejenak bahwa Anda adalah seorang pencuri. Anda telah membobol toko di malam hari dengan ransel (ransel). Di depan Anda ada beberapa barang yang bisa Anda curi. Tetapi pada saat yang sama, ransel Anda memiliki kapasitas yang terbatas. Itu dapat membawa tidak lebih dari 30 unit berat. Anda juga ingin membawa set barang paling berharga yang muat ke dalam ransel. Bagaimana Anda menentukan apa yang harus dimasukkan ke dalam tas Anda? Jadi,
Pilih barang termahal yang belum diambil.
Jika muat di ransel, masukkan. Jika tidak, biarkan saja.
Apakah kita sudah mencuri semuanya? Jika tidak, kita kembali ke langkah 1. Jika ya, maka kita segera keluar dari toko, karena kita telah menyelesaikan apa yang harus kita lakukan.
Mari kita lihat ini, tetapi di Jawa. Ini adalah bagaimana kelas Item akan terlihat:
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;
}
}
Tidak ada yang istimewa di sini: tiga bidang (nama, bobot, nilai) yang menentukan karakteristik item. Selain itu, seperti yang Anda lihat, antarmuka Sebanding diterapkan untuk memungkinkan kami mengurutkan Barang berdasarkan harga. Selanjutnya, kita akan melihat kelas Bag, yang mewakili 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 adalah kapasitas ransel kita, yang diatur saat kita membuat objek;
item mewakili objek di ransel kami;
currentWeight , currentValue — kolom ini menyimpan berat dan nilai saat ini dari semua item di ransel, yang kita tingkatkan saat kita menambahkan item baru dalam metode addItem.
Ngomong-ngomong, sekarang mari kita pergi ke kelas tempat semua tindakan berlangsung:
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());
}
}
Pertama, kami membuat daftar item dan mengurutkannya. Kami membuat objek tas dengan kapasitas 30 unit. Selanjutnya, kita meneruskan item dan objek tas ke metode fillBackpack, yang mengisi ransel sesuai dengan algoritme serakah kita:
Ini cukup sederhana: kita mulai menelusuri daftar barang yang diurutkan berdasarkan biaya dan memasukkannya ke dalam tas jika kapasitasnya memungkinkan. Jika tidak ada cukup ruang, maka item tersebut akan dilewati dan kami akan terus melintasi item lainnya hingga kami mencapai akhir daftar. Setelah kita menjalankan main, inilah keluaran konsol yang akan kita dapatkan:
Berat knapsack adalah 29. Total nilai barang di dalam knapsack adalah 3700
Ini adalah contoh algoritma rakus: pada setiap langkah, solusi optimal lokal dipilih, dan pada akhirnya, Anda mendapatkan solusi optimal global. Dalam kasus kami, pilihan terbaik adalah barang yang paling mahal. Tapi apakah ini solusi terbaik? Tidakkah menurut Anda mungkin untuk sedikit meningkatkan solusi kami untuk mengisi ransel kami dengan barang-barang yang memiliki nilai total lebih besar? Mari kita lihat bagaimana ini bisa dilakukan.
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());
}
}
}
Di sini pertama-tama kita menghitung rasio nilai terhadap berat untuk setiap item. Ini memberi tahu kita nilai setiap unit dari item yang diberikan. Dan kemudian kami menggunakan rasio ini untuk menyortir barang kami dan menambahkannya ke tas kami. Mari jalankan yang berikut ini:
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());
Kami mendapatkan keluaran konsol ini:
Berat ransel adalah 29. Total biaya barang di ransel adalah 4150
Sedikit lebih baik, bukan? Algoritma serakah membuat pilihan optimal secara lokal di setiap langkah, berharap solusi akhir juga akan optimal. Asumsi ini tidak selalu valid, tetapi untuk banyak tugas, algoritme rakus menghasilkan solusi akhir yang optimal. Kompleksitas waktu dari algoritma ini adalah O(N). Cukup bagus, ya?
Dan karena Anda berada di situs web ini, saya berani berasumsi bahwa Anda menulis dalam bahasa Jawa. Itu sebabnya hari ini saya menyarankan agar Anda membiasakan diri dengan beberapa algoritme dasar dan contoh spesifik tentang cara mengimplementasikannya di Java. Dengan "beberapa", maksud saya:
GO TO FULL VERSION