Implementasi Algoritma Quicksort di Java

1. Ikhtisar

Dalam tutorial ini, kita akan menjelajahi algoritma QuickSort secara detail, dengan fokus pada implementasi Java-nya.

Kami juga akan membahas kelebihan dan kekurangannya dan kemudian menganalisis kompleksitas waktunya.

2. Algoritma QuickSort

Quicksort adalah algoritma pengurutan, yang memanfaatkan prinsip divide-and-conquer. Ini memiliki kompleksitas O (n log n) rata-rata dan ini adalah salah satu algoritma pengurutan yang paling banyak digunakan, terutama untuk volume data besar.

Penting untuk diingat bahwa Quicksort bukanlah algoritme yang stabil. Algoritme pengurutan yang stabil adalah algoritme di mana elemen-elemen dengan nilai yang sama muncul dalam urutan yang sama dalam keluaran yang diurutkan seperti yang muncul di daftar masukan.

Daftar masukan dibagi menjadi dua sub-daftar oleh elemen yang disebut pivot; satu sub-daftar dengan elemen kurang dari poros dan satu lagi dengan elemen lebih besar dari poros. Proses ini berulang untuk setiap sub-daftar.

Akhirnya, semua sub-daftar yang diurutkan bergabung untuk membentuk hasil akhir.

2.1. Langkah Algoritma

  1. Kami memilih elemen dari daftar, yang disebut pivot. Kami akan menggunakannya untuk membagi daftar menjadi dua sub-daftar.
  2. Kami menyusun ulang semua elemen di sekitar pivot - elemen dengan nilai lebih kecil ditempatkan sebelumnya, dan semua elemen lebih besar dari pivot setelahnya. Setelah langkah ini, poros berada di posisi akhirnya. Ini adalah langkah partisi penting.
  3. Kami menerapkan langkah-langkah di atas secara rekursif ke kedua sub-daftar di kiri dan kanan pivot.

Seperti yang bisa kita lihat, quicksort secara alami adalah algoritma rekursif, seperti setiap pendekatan divide and conquer.

Mari kita ambil contoh sederhana untuk lebih memahami algoritma ini.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Misalkan kita memilih 5 sebagai poros untuk kesederhanaan
  2. Pertama-tama kita akan meletakkan semua elemen kurang dari 5 di posisi pertama larik: {3, 4, 5, 6, 5, 9}
  3. Kami kemudian akan mengulanginya untuk sub-larik kiri {3,4}, mengambil 3 sebagai poros
  4. Tidak ada elemen yang kurang dari 3
  5. Kami menerapkan quicksort pada sub-larik di sebelah kanan pivot, yaitu {4}
  6. Sub-larik ini hanya terdiri dari satu elemen yang diurutkan
  7. Kita lanjutkan dengan bagian kanan dari larik asli, {6, 5, 9} sampai kita mendapatkan larik terurut terakhir

2.2. Memilih Pivot Optimal

Poin krusial dalam QuickSort adalah memilih pivot terbaik. Elemen tengah, tentu saja, adalah yang terbaik, karena akan membagi daftar menjadi dua sub-daftar yang sama.

Tetapi menemukan elemen tengah dari daftar yang tidak berurutan itu sulit dan memakan waktu, itulah mengapa kami mengambil elemen pertama sebagai pivot, elemen terakhir, median atau elemen acak lainnya.

3. Implementasi di Jawa

Metode pertama adalah quickSort () yang mengambil parameter array yang akan diurutkan, indeks pertama dan terakhir. Pertama, kami memeriksa indeks dan melanjutkan hanya jika masih ada elemen yang akan diurutkan.

Kami mendapatkan indeks dari pivot yang diurutkan dan menggunakannya untuk memanggil metode partition () secara rekursif dengan parameter yang sama seperti metode quickSort () , tetapi dengan indeks yang berbeda:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Mari lanjutkan dengan metode partisi () . Untuk mempermudah, fungsi ini mengambil elemen terakhir sebagai poros. Kemudian, periksa setiap elemen dan tukar sebelum pivot jika nilainya lebih kecil.

Pada akhir pembagian, semua elemen yang kurang dari poros berada di sebelah kiri dan semua elemen yang lebih besar dari poros berada di sebelah kanannya. Pivot berada pada posisi terakhir yang diurutkan dan fungsi mengembalikan posisi ini:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Analisis Algoritma

4.1. Kompleksitas Waktu

Dalam kasus terbaik, algoritme akan membagi daftar menjadi dua sub-daftar berukuran sama. Jadi, iterasi pertama dari daftar lengkap berukuran n membutuhkan O (n) . Menyortir dua sub-daftar yang tersisa dengan n / 2 elemen masing-masing membutuhkan 2 * O (n / 2) . Alhasil, algoritma QuickSort memiliki kompleksitas O (n log n) .

Dalam kasus terburuk, algoritme akan memilih hanya satu elemen di setiap iterasi, jadi O (n) + O (n-1) +… + O (1) , yang sama dengan O (n2) .

Rata-rata QuickSort memiliki kompleksitas O (n log n) , sehingga cocok untuk volume data besar.

4.2. QuickSort vs MergeSort

Mari kita bahas dalam kasus mana kita harus memilih QuickSort daripada MergeSort.

Meskipun Quicksort dan Mergesort memiliki kompleksitas waktu rata-rata O (n log n) , Quicksort adalah algoritme yang lebih disukai, karena memiliki kompleksitas ruang O (log (n)) . Mergesort, di sisi lain, membutuhkan O (n) penyimpanan ekstra, yang membuatnya cukup mahal untuk array.

Quicksort perlu mengakses indeks yang berbeda untuk operasinya, tetapi akses ini tidak secara langsung dimungkinkan dalam daftar tertaut, karena tidak ada blok kontinu; oleh karena itu untuk mengakses elemen kita harus mengulang melalui setiap node dari awal daftar tertaut. Selain itu, Mergesort diimplementasikan tanpa ruang ekstra untuk LinkedLists.

Dalam kasus seperti itu, peningkatan overhead untuk Quicksort dan Mergesort umumnya lebih disukai.

5. Kesimpulan

Quicksort adalah algoritme pengurutan elegan yang sangat berguna dalam banyak kasus.

Biasanya ini adalah algoritme "di tempat", dengan kompleksitas waktu rata-rata O (n log n).

Hal menarik lainnya untuk disebutkan adalah bahwa metode Java's Arrays.sort () menggunakan Quicksort untuk mengurutkan array primitif. Implementasinya menggunakan dua pivot dan berperforma jauh lebih baik daripada solusi sederhana kami, itulah sebabnya untuk kode produksi, biasanya lebih baik menggunakan metode library.

Seperti biasa, kode untuk implementasi algoritme ini dapat ditemukan di repositori GitHub kami.