Sorting adalah salah satu operasi dasar yang kita lakukan pada objek. Bahkan di masa kanak-kanak, anak-anak diajari memilah saat mereka mengembangkan keterampilan berpikir mereka. Komputer dan perangkat lunak tidak terkecuali. Ada berbagai macam algoritma sorting di Java . Saya sarankan Anda memeriksa apa itu dan bagaimana cara kerjanya. Bagaimana jika Anda ditanya tentang salah satu dari mereka di sebuah wawancara suatu hari nanti?
Perkenalan
Sorting element merupakan salah satu kategori algoritma yang harus diketahui oleh seorang developer. Jika ilmu komputer dulunya tidak dianggap serius ketika masih sekolah, siswa sekarang harus bisa mengimplementasikan dan memahami algoritma pengurutan. Algoritme dasar, yang paling sederhana, diimplementasikan menggunakan loop for . Secara alami, untuk mengurutkan koleksi elemen, seperti array, Anda harus menelusuri koleksi tersebut. Misalnya:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Apa yang bisa dikatakan tentang segmen kode ini? Kami memiliki loop di mana kami mengubah indeks ( int i) dari 0 ke elemen terakhir dalam array. Faktanya, kami hanya mengambil setiap elemen dalam larik dan mencetak isinya. Semakin banyak elemen dalam array, semakin lama kode akan selesai. Artinya, jika nadalah jumlah elemen, saat n = 10program akan berjalan dua kali lebih lama daripada saat n = 5. Jika program kita memiliki satu putaran, waktu eksekusi bertambah secara linier: semakin banyak elemen, semakin lama waktu eksekusi. Ternyata algoritma di atas bekerja dalam waktu linier (fungsi linier n). Dalam kasus seperti itu, kami mengatakan bahwa kompleksitas algoritme adalah "O(n)". Notasi ini juga disebut "O besar" atau "perilaku asimtotik". Tapi ingat saja"
Algoritma pengurutan paling sederhana (bubble sort)
Misalkan kita memiliki sebuah array dan kita dapat mengulanginya. Besar. Sekarang mari kita coba mengurutkannya dalam urutan menaik. Apa artinya ini? Ini berarti bahwa diberikan dua elemen (misalnya, a = 6, b = 5), kita harus mengatur ulang adan bjika alebih besar dari b(jika a > b). Apa artinya ini ketika kita menggunakan indeks untuk bekerja dengan koleksi (seperti halnya dengan array)? Artinya, jika elemen dengan indeks a lebih besar dari elemen dengan indeks b( array[a] > array[b]), maka elemen tersebut harus ditukar. Ada berbagai cara untuk mengubah tempat. Namun kami akan menggunakan teknik yang sederhana, mudah dipahami, dan mudah diingat:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Sekarang kita dapat menulis yang berikut:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Seperti yang Anda lihat, elemennya benar-benar ditukar. Kita mulai dengan indeks 1, karena jika array hanya memiliki satu elemen, ekspresi array[i] < array[i-1]tidak valid untuk index 0. Melakukan hal ini juga melindungi kita dari kasus di mana array tidak memiliki elemen atau hanya satu elemen, dan membuat kode terlihat lebih baik. Tetapi array yang dihasilkan masih belum tersortir, karena satu pass saja tidak cukup untuk melakukan sorting. Kita harus menambahkan loop lain di mana kita akan melakukan operan lagi dan lagi sampai kita mendapatkan larik yang diurutkan:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Jadi kami menyelesaikan algoritme pengurutan pertama kami. Kami mengulangi loop luar ( while) sampai kami memutuskan bahwa tidak diperlukan iterasi lagi. Secara default, sebelum setiap iterasi baru, kami menganggap bahwa array kami diurutkan dan kami tidak perlu mengulang lagi. Karenanya, kami bergerak secara berurutan melalui elemen dan memeriksa asumsi ini. Tetapi jika elemennya tidak beraturan, maka kami menukar elemen dan memahami bahwa kami sekarang tidak memiliki jaminan bahwa elemen tersebut berada dalam urutan yang benar. Ini berarti bahwa kita perlu melakukan iterasi lain. Sebagai contoh, misalkan kita memiliki [3, 5, 2]. 5lebih dari 3- semuanya baik-baik saja. Tapi 2kurang dari 5. Namun, [3, 2, 5]membutuhkan izin lain, karena3 > 2dan mereka perlu ditukar. Karena kami menggunakan loop dalam satu loop, kompleksitas algoritme kami meningkat. Diberikan nelemen, menjadi n * n, yaitu O(n^2). Ini disebut kompleksitas kuadrat. Secara umum, kita tidak dapat mengetahui dengan pasti berapa banyak iterasi yang dibutuhkan. Ekspresi kompleksitas suatu algoritma menunjukkan bagaimana kompleksitas meningkat dalam kasus terburuk. Artinya, ini menunjukkan berapa banyak waktu eksekusi akan meningkat seiring dengan perubahan jumlah elemen n. Bubble sort adalah salah satu algoritma sorting yang paling sederhana dan tidak efisien. Ini juga terkadang disebut "jenis bodoh". Materi tentang topik ini:
Algoritma pengurutan lainnya adalah pengurutan seleksi. Ini juga memiliki kompleksitas kuadrat, tetapi lebih dari itu nanti. Jadi idenya sederhana. Pada setiap lintasan, kami memilih elemen terkecil dan menggesernya ke awal. Selain itu, setiap operan dimulai satu langkah ke kanan. Dengan kata lain, lintasan pertama dimulai dari elemen ke-nol, lintasan kedua dari elemen pertama, dll. Ini akan terlihat seperti ini:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Pengurutan ini tidak stabil, karena elemen identik (dalam hal karakteristik apa pun yang kita gunakan untuk mengurutkan elemen) dapat mengubah posisi relatifnya. Ada contoh yang bagus di artikel Wikipedia tentang seleksi sort . Materi tentang topik ini:
Jenis penyisipan juga memiliki kompleksitas kuadrat, karena sekali lagi kita memiliki loop di dalam loop. Apa yang membuat jenis penyisipan berbeda? Algoritme pengurutan ini "stabil". Ini berarti bahwa unsur-unsur yang identik tidak akan mengubah urutan relatifnya. Sekali lagi, maksud kami identik dalam hal karakteristik yang kami sortir.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Jenis antar-jemput
Ada algoritma sorting sederhana lainnya: shuttle sort. Ini juga dikenal sebagai jenis gelembung dua arah atau jenis pengocok koktail. Nama alternatif ini memberi tahu kita bahwa jenis pesawat ulang-alik bukanlah tentang pesawat ulang-alik. Ini tentang sesuatu yang bergerak bolak-balik. Sekarang Anda dapat memikirkannya saat memikirkan algoritme ini. Apa esensi dari algoritma? Inti dari algoritme ini adalah kita mengulangi dari kiri ke kanan, menukar elemen dan memeriksa apakah ada elemen yang tersisa di arah lain yang perlu ditukar.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Algoritma pengurutan sederhana lainnya adalah pengurutan shell. Intinya mirip dengan pengurutan gelembung, tetapi di setiap iterasi kami memiliki jarak yang berbeda antara elemen yang dibandingkan. Itu dipotong setengah dengan setiap iterasi. Berikut implementasinya:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Selain algoritma pengurutan sederhana tersebut, ada juga algoritma pengurutan yang lebih rumit. Misalnya, menggabungkan semacam. Ada dua hal yang perlu diperhatikan. Pertama, rekursi datang untuk menyelamatkan kita di sini. Kedua, kompleksitas algoritme tidak lagi kuadrat, seperti yang biasa kita lakukan. Kompleksitas algoritma ini adalah logaritmik. Ini ditulis sebagai O(n log n). Jadi mari kita terapkan. Pertama, kita akan menulis panggilan rekursif ke metode pengurutan:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Sekarang, mari tambahkan tindakan utama ke implementasi kita. Inilah metode super kami:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Kita dapat menjalankan contoh kita dengan meneleponmergeSort(array, 0, array.length-1). Seperti yang Anda lihat, prosesnya bermuara pada menerima larik input bersama dengan indikasi awal dan akhir bagian yang perlu diurutkan. Saat penyortiran dimulai, ini adalah awal dan akhir dari array. Kemudian kami menghitung pembatas, yaitu indeks tempat kami akan membagi array. Jika array dapat dibagi menjadi 2 bagian, maka kita memanggil metode pengurutan secara rekursif untuk kedua bagian array tersebut. Kami menyiapkan buffer tambahan tempat kami akan memasukkan bagian yang diurutkan. Selanjutnya, atur indeks di awal bagian yang akan diurutkan dan mulai menelusuri setiap elemen dari buffer kosong, mengisinya dengan elemen terkecil. Jika elemen yang ditunjuk oleh indeks lebih kecil dari elemen yang ditunjuk oleh pembatas, kami menempatkan elemen di buffer dan menggeser indeks. Jika tidak, kami menempatkan elemen yang ditunjuk oleh pembatas ke dalam buffer dan menggeser pembatas. Segera setelah pembatas melampaui batas bagian yang sedang diurutkan atau kami mengisi seluruh larik, rentang yang ditentukan dianggap telah diurutkan.Materi tentang topik ini:
Algoritma sorting lain yang menarik adalah count sort. Kompleksitas algoritmik di sini adalah O(n+k), dimana nadalah jumlah elemen dan kmerupakan nilai maksimum dari suatu elemen. Algoritma ini memang memiliki satu kekurangan: kita perlu mengetahui nilai minimum dan maksimum dalam array. Berikut adalah contoh pengurutan penghitungan:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Anda dapat memahami bahwa sangat merepotkan ketika kita perlu mengetahui terlebih dahulu nilai minimum dan maksimumnya. Dan kami punya algoritme lain di sini: radix sort. Saya hanya akan menyajikan algoritme di sini secara visual. Lihat bahan pelengkap pelaksanaannya : Bahan :
Nah, saatnya untuk pencuci mulut — penyortiran cepat, salah satu algoritme penyortiran yang paling terkenal. Ini memiliki kompleksitas logaritmik: O(n log n). Algoritma pengurutan ini dikembangkan oleh Tony Hoare. Menariknya, dia menemukannya saat tinggal di Uni Soviet, di mana dia belajar terjemahan mesin di Universitas Moskow dan mengembangkan buku frasa Rusia-Inggris. Terlebih lagi, Java menggunakan versi yang lebih kompleks dari algoritme ini dalam Arrays.sort. Bagaimana Collections.sort? Mengapa tidak melihat bagaimana hal-hal diurutkan "di bawah tenda"? Ini kodenya:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Ini semua adalah hal yang sangat menakutkan, jadi mari kita gali lebih dalam. Untuk larik input ( int[]sumber), kami membuat dua penanda: kiri ( L) dan kanan ( R). Selama pemanggilan metode pertama, mereka sesuai dengan awal dan akhir array. Kemudian kami mengidentifikasi elemen pivot, yang diberi nama tepat pivot. Setelah ini, tugas kita adalah memindahkan nilai yang lebih kecil dari pivotke kiri pivot, dan yang lebih besar — ke kanan. Untuk melakukannya, pertama-tama kita pindahkan Lpenanda hingga kita menemukan nilai yang lebih besar dari pivot. Jika tidak ditemukan nilai yang lebih kecil, maka
L menjadi sama dengan
pivot. Kemudian kita pindahkan
Rpenanda hingga kita menemukan nilai yang lebih kecil dari
pivot. Jika tidak ditemukan nilai yang lebih besar, maka
Rmenjadi sama dengan
pivot. Selanjutnya jika
Lmarker berada sebelum
Rmarker atau berhimpitan dengannya, maka kita coba menukar elemennya jika elemennya
Llebih kecil dari
Relemennya. Kemudian kita bergeser
Lke kanan sebesar 1, dan kita bergeser
Rke kiri sebesar 1. Saat
Lpenanda bergerak melewati
Rpenanda, berarti penukaran selesai: nilai yang lebih kecil berada di sebelah kiri
pivot, nilai yang lebih besar berada di sebelah kanan
pivot. Setelah ini, kami memanggil metode pengurutan yang sama secara rekursif pada subarray - dari awal bagian yang akan diurutkan ke penanda kanan, dan dari penanda kiri hingga akhir bagian yang akan diurutkan. Mengapa dari awal ke penanda yang tepat? Karena pada akhir iterasi, ternyata penanda kanan bergerak cukup menjadi batas bagian kiri. Algoritme ini lebih kompleks daripada penyortiran sederhana, jadi yang terbaik adalah membuat sketsa. Ambil selembar kertas putih dan tulis: 4 2 6 7 3. Kemudian tulis
pivotdi tengah, yaitu di bawah angka 6. Lingkari. Di bawah 4, tulis
L, dan di bawah 3, tulis
R. 4 kurang dari 6, 2 kurang dari 6. Kita akhirnya pindah
Lke
pivotposisi tersebut, karena
Ltidak bisa melewatinya
pivot, sesuai kondisi. Tulis lagi 4 2 6 7 3. Lingkari 6 (
pivot) dan taruh
Ldi bawahnya. Sekarang pindahkan
Rpenanda. 3 kurang dari 6, jadi beri
Rtanda pada 3. Karena 3 kurang dari 6 (
pivot), kita melakukan a
swap. Tulis hasilnya: 4 2 3 7 6. Lingkari 6, karena masih
pivot. Penanda
Lada di 3.
RPenanda ada di 6. Ingat bahwa kita memindahkan penanda sampai
Lmelewati
R. Pindah
Lke nomor berikutnya. Di sini saya ingin menjelajahi dua kemungkinan: 1) kasus di mana angka kedua dari belakang adalah 7 dan 2) kasus di mana 1, bukan 7.
Jika angka kedua dari belakang adalah 1: Pindahkan
Lpenanda ke 1, karena kita dapat memindahkan
Lselama
Lmarker menunjuk ke angka yang lebih kecil dari
pivot. Tapi kita tidak bisa berpindah
Rdari 6, karena kita hanya bisa memindahkan R jika
Rpenanda menunjuk ke angka yang lebih besar dari
pivot. Kita tidak melakukan a
swap, karena 1 kurang dari 6. Tulislah situasi saat ini: 4 2 3 1 6. Lingkari 6 (
pivot).
Lbergeser
pivotdan berhenti bergerak.
Rtidak bergerak. Kami tidak melakukan swap. Pergeseran
Ldan
Rsatu posisi. Tulis
Rpenanda di bawah 1.
LPenanda di luar batas. Karena
Ldi luar batas, kita tidak melakukan apa-apa. Tapi, kita tuliskan 4 2 3 1 lagi, karena ini adalah ruas kiri kita yang kurang dari
pivot(6). Pilih yang baru
pivotdan mulai semuanya lagi :)
Jika angka kedua dari belakang adalah 7:Pindahkan
Lmarker ke 7. Kita tidak bisa memindahkan marker yang benar, karena sudah mengarah ke pivot. 7 lebih besar dari
pivot, jadi kami melakukan a
swap. Tulis hasilnya: 4 2 3 6 7. Lingkari 6, karena merupakan
pivot. Penanda
Lsekarang digeser ke 7, dan
Rpenanda digeser ke 3. Tidak masuk akal untuk mengurutkan bagian dari
Lsampai akhir, karena hanya ada 1 elemen. Namun, kami mengirimkan bagian dari 4 ke
Rpenanda untuk disortir. Kami memilih
pivotdan memulai dari awal lagi :) Sekilas, mungkin terlihat jika Anda menambahkan banyak nilai sama dengan
pivot, maka Anda akan merusak algoritme. Tapi ini bukan masalahnya. Anda dapat memikirkan kombinasi rumit dan meyakinkan diri sendiri di atas kertas bahwa semuanya benar dan kagum bahwa tindakan sederhana seperti itu menerapkan mekanisme penyortiran yang andal. Satu-satunya downside adalah algoritma pengurutan ini tidak stabil. Karena penukaran dapat mengubah urutan relatif dari elemen yang identik jika salah satunya ditemukan sebelumnya
pivotsebelum elemen lainnya ditukar ke bagian sebelumnya
pivot.
Garis bawah
Di atas, kami melihat sekumpulan algoritme pengurutan "gentleman" yang diterapkan di Java. Algoritma umumnya berguna, baik dari perspektif terapan maupun dalam hal belajar cara berpikir. Ada yang lebih sederhana, ada yang lebih rumit. Orang pintar mempertahankan disertasi mereka untuk beberapa orang. Bagi yang lain, mereka menulis buku super tebal. Semoga bahan pelengkapnya bisa membantu Anda belajar lebih banyak lagi, karena artikel ini hanyalah ikhtisar yang ternyata sudah berbobot. Dan tujuannya adalah untuk memberikan pengenalan kecil. Anda juga dapat menemukan pengantar algoritma jika Anda membaca
"Grokking Algorithms ". Saya juga suka playlist dari Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Untuk bersenang-senang, Anda dapat melihat visualisasi algoritme saat
menyortir.visualgo.net .
GO TO FULL VERSION