7 Algoritma Yang Harus Diketahui Setiap Programmer

Sebagai mahasiswa pemrograman, Anda mungkin telah belajar banyak algoritma yang berbeda sepanjang karir Anda. Menjadi mahir dalam algoritma yang berbeda sangat penting untuk setiap programmer.

Dengan begitu banyak algoritme, mungkin sulit untuk melacak apa yang penting. Jika Anda sedang bersiap untuk wawancara atau sekadar meningkatkan keterampilan Anda, daftar ini akan membuatnya relatif mudah. Baca terus selagi kami membuat daftar algoritme paling penting untuk pemrogram.

1. Algoritma Dijkstra

Edsger Dijkstra adalah salah satu ilmuwan komputer paling berpengaruh pada masanya, dan dia berkontribusi untuk banyak bidang ilmu komputasi yang berbeda, termasuk sistem operasi, konstruksi kompiler, dan banyak lagi lagi. Salah satu kontribusi Dijkstra yang paling menonjol adalah kecerdikan algoritma jalur terpendeknya untuk grafik, juga dikenal sebagai Algoritma Jalur Terpendek Dijkstra.

Algoritma Dijkstra menemukan jalur terpendek tunggal dalam graf dari sumber ke semua simpul graf. Pada setiap iterasi algoritma, sebuah simpul ditambahkan dengan jarak minimum dari sumber dan satu simpul yang tidak ada di jalur terpendek saat ini. Ini adalah sifat serakah yang digunakan oleh algoritma Djikstra.

Algoritma biasanya diimplementasikan menggunakan satu set. Algoritma Dijkstra sangat efisien ketika diimplementasikan dengan Min Heap; Anda dapat menemukan jalur terpendek hanya dalam waktu O(V+ElogV) (V adalah jumlah simpul dan E adalah jumlah sisi dalam graf tertentu).

Algoritma Dijkstra memiliki keterbatasan; itu hanya bekerja pada grafik berarah dan tidak berarah dengan tepi berbobot positif. Untuk bobot negatif, algoritma Bellman-Ford biasanya lebih disukai.

Pertanyaan wawancara biasanya menyertakan algoritme Djikstra, jadi kami sangat menyarankan untuk memahami detail dan aplikasinya yang rumit.

2. Gabungkan Sortir

Kami memiliki beberapa algoritme pengurutan dalam daftar ini, dan pengurutan gabungan adalah salah satu algoritme terpenting. Ini adalah algoritma pengurutan yang efisien berdasarkan teknik pemrograman Divide and Conquer. Dalam skenario terburuk, merge sort dapat mengurutkan angka “n” hanya dalam waktu O(nlogn). Dibandingkan dengan teknik penyortiran primitif seperti Sortir Gelembung (yang membutuhkan waktu O(n^2)), merge sort sangat efisien.

Terkait: Pengantar Algoritma Merge Sort

Dalam merge sort, array yang akan diurutkan berulang kali dipecah menjadi subarray hingga setiap subarray terdiri dari satu nomor. Algoritma rekursif kemudian berulang kali menggabungkan subarray dan mengurutkan array.

3. sortir cepat

Quicksort adalah algoritma pengurutan lain berdasarkan teknik pemrograman Divide and Conquer. Dalam algoritma ini, elemen pertama dipilih sebagai pivot, dan seluruh array kemudian dipartisi di sekitar pivot ini.

Seperti yang mungkin sudah Anda duga, pivot yang baik sangat penting untuk sortir yang efisien. Pivot dapat berupa elemen acak, elemen media, elemen pertama, atau bahkan elemen terakhir.

Implementasi quicksort seringkali berbeda dalam cara mereka memilih pivot. Dalam kasus rata-rata, quicksort akan mengurutkan array besar dengan pivot yang bagus hanya dalam waktu O(nlogn).

Pseudocode umum quicksort berulang kali mempartisi array pada pivot dan memposisikannya di posisi subarray yang benar. Itu juga menempatkan elemen yang lebih kecil dari poros di sebelah kirinya dan elemen yang lebih besar dari poros di sebelah kanannya.

4. Pencarian Pertama Kedalaman

Depth First Search (DFS) adalah salah satu algoritma grafik pertama yang diajarkan kepada siswa. DFS adalah algoritma yang efisien digunakan untuk melintasi atau mencari grafik. Itu juga dapat dimodifikasi untuk digunakan dalam traversal pohon.

Traversal DFS dapat dimulai dari sembarang node, dan menyelam ke setiap simpul yang berdekatan. Algoritme mundur ketika tidak ada simpul yang belum dikunjungi, atau ada jalan buntu. DFS biasanya diimplementasikan dengan stack dan array boolean untuk melacak node yang dikunjungi. DFS mudah diterapkan dan sangat efisien; ia bekerja (V+E), di mana V adalah jumlah simpul dan E adalah jumlah tepi.

Aplikasi khas dari traversal DFS termasuk pengurutan topologi, mendeteksi siklus dalam grafik, pencarian jalur, dan menemukan komponen yang terhubung kuat.

5. Pencarian Luas-Pertama

Breadth-First Search (BFS) juga dikenal sebagai traversal urutan level untuk pohon. BFS bekerja dalam O(V+E) mirip dengan algoritma DFS. Namun, BFS menggunakan antrian alih-alih tumpukan. DFS menyelami grafik, sedangkan BFS melintasi grafik secara luas.

Algoritma BFS menggunakan antrian untuk melacak simpul. Vertikal berdekatan yang belum dikunjungi dikunjungi, ditandai, dan diantrekan. Jika simpul tidak memiliki simpul yang berdekatan, maka simpul dihapus dari antrian dan dieksplorasi.

BFS umumnya digunakan dalam jaringan peer-to-peer, jalur terpendek dari graf tidak berbobot, dan untuk menemukan pohon rentang minimum.

6. Pencarian Biner

Pencarian Biner adalah algoritma sederhana untuk menemukan elemen yang diperlukan dalam array yang diurutkan. Ia bekerja dengan berulang kali membagi array menjadi dua. Jika elemen yang dibutuhkan lebih kecil dari elemen paling tengah, maka sisi kiri elemen tengah diproses lebih lanjut; jika tidak, sisi kanan dibelah dua dan dicari lagi. Proses ini diulang sampai elemen yang dibutuhkan ditemukan.

Kompleksitas waktu terburuk dari pencarian biner adalah O(logn) yang membuatnya sangat efisien dalam mencari array linier.

7. Algoritma Pohon Rentang Minimum

Pohon merentang minimum (MST) dari suatu graf memiliki biaya minimum di antara semua pohon merentang yang mungkin. Biaya pohon merentang tergantung pada berat tepinya. Penting untuk dicatat bahwa mungkin ada lebih dari satu pohon merentang minimum. Ada dua algoritma utama MST, yaitu Kruskal dan Prim.

Algoritma Kruskal menciptakan MST dengan menambahkan tepi dengan biaya minimum ke set yang berkembang. Algoritme pertama-tama mengurutkan tepi berdasarkan bobotnya dan kemudian menambahkan tepi ke MST mulai dari minimum.

Penting untuk dicatat bahwa algoritme tidak menambahkan tepi yang membentuk siklus. Algoritma Kruskal lebih disukai untuk graf sparse.

Algoritma Prim juga menggunakan properti serakah dan ideal untuk grafik padat. Ide sentral dalam MST Prim adalah memiliki dua set simpul yang berbeda; satu set berisi MST yang sedang tumbuh, sedangkan yang lain berisi simpul yang tidak digunakan. Pada setiap iterasi, tepi bobot minimum yang akan menghubungkan dua set dipilih.

Algoritme pohon rentang minimum sangat penting untuk analisis klaster, taksonomi, dan jaringan siaran.

Seorang Pemrogram yang Efisien Mahir Dengan Algoritma

Pemrogram terus-menerus belajar dan mengembangkan keterampilan mereka, dan ada beberapa inti penting yang harus dikuasai setiap orang. Seorang programmer yang terampil mengetahui algoritma yang berbeda, kelebihan dan kekurangan masing-masing, dan algoritma mana yang paling sesuai untuk skenario tertentu.

Pengantar Algoritma Penyortiran Shell

Meskipun penyortiran cangkang bukanlah metode yang paling efisien, para pemula memiliki banyak manfaat dari mempraktikkannya.

Baca Selanjutnya

Tentang Penulis