Algoritma QuickSort

Dalam tutorial ini, Anda akan mempelajari cara kerja quicksort. Selain itu, Anda akan menemukan contoh kerja quicksort di C, C ++ Python, dan Java.

Quicksort adalah algoritma yang didasarkan pada pendekatan divide and conquer di mana array dipecah menjadi subarray dan sub-array ini dipanggil secara rekursif untuk mengurutkan elemen.

Bagaimana QuickSort Bekerja?

1. Elemen pivot dipilih dari larik. Anda dapat memilih elemen apa pun dari larik sebagai elemen pivot.
   Di sini, kita telah mengambil bagian paling kanan (yaitu elemen terakhir) dari larik sebagai elemen pivot. Pilih elemen pivot
2. Elemen yang lebih kecil dari elemen pivot diletakkan di sebelah kiri dan elemen yang lebih besar dari elemen pivot diletakkan di sebelah kanan. Letakkan semua elemen yang lebih kecil di sebelah kiri dan lebih besar di sebelah kanan elemen pivot
   Pengaturan di atas dicapai dengan langkah-langkah berikut.
   1. Sebuah pointer dipasang di elemen pivot. Elemen pivot dibandingkan dengan elemen yang dimulai dari indeks pertama. Jika elemen yang lebih besar dari elemen pivot tercapai, penunjuk kedua disetel untuk elemen itu.
   2. Sekarang, elemen pivot dibandingkan dengan elemen lainnya (penunjuk ketiga). Jika elemen yang lebih kecil dari elemen pivot tercapai, elemen yang lebih kecil ditukar dengan elemen lebih besar yang ditemukan sebelumnya. Perbandingan elemen pivot dengan elemen lainnya
   3. Proses ini berlangsung hingga elemen terakhir kedua tercapai.
      Terakhir, elemen pivot ditukar dengan penunjuk kedua. Tukar elemen pivot dengan penunjuk kedua
   4. Sekarang bagian kiri dan kanan dari elemen pivot ini diambil untuk diproses lebih lanjut dalam langkah-langkah di bawah ini.
3. Elemen pivot dipilih lagi untuk sub-bagian kiri dan kanan secara terpisah. Dalam sub-bagian ini, elemen pivot ditempatkan di posisi yang tepat. Kemudian, langkah 2 diulangi. Pilih elemen poros di setiap bagian dan letakkan di tempat yang benar menggunakan rekursi
4. Sub-bagian sekali lagi dibagi menjadi sub-bagian yang lebih kecil sampai setiap sub-bagian terbentuk dari satu elemen.
5. Pada titik ini, array sudah diurutkan.

Quicksort menggunakan rekursi untuk menyortir sub-bagian.

Berdasarkan pendekatan Divide and conquer, algoritma quicksort dapat dijelaskan sebagai:

• Divide
  Array dibagi menjadi beberapa sub-bagian yang menggunakan pivot sebagai titik partisi. Elemen yang lebih kecil dari poros ditempatkan di sebelah kiri poros dan elemen yang lebih besar dari poros ditempatkan di sebelah kanan.
• Taklukkan Subbagian
  kiri dan kanan dipartisi lagi menggunakan dengan memilih elemen pivot untuk mereka. Ini dapat dicapai dengan meneruskan subbagian ke dalam algoritma secara rekursif.
• Gabungkan
  Langkah ini tidak memainkan peran penting dalam quicksort. Array sudah diurutkan di akhir langkah penaklukan.

Anda dapat memahami cara kerja quicksort dengan bantuan ilustrasi di bawah ini.

Menyortir elemen di kiri pivot menggunakan rekursi Menyortir elemen di sebelah kanan pivot menggunakan rekursi

Algoritma Pengurutan Cepat

 quickSort (array, leftmostIndex, rightmostIndex) jika (leftmostIndex <rightmostIndex) pivotIndex <- partisi (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmostIndex) partisi (larik, indeks paling kiri, indeks paling kanan) ) set rightmostIndex sebagai pivotIndex storeIndex <- leftmostIndex - 1 untuk i <- leftmostIndex + 1 ke rightmostIndex jika elemen (i) <pivotElement swap element (i) dan elemen (storeIndex) storeIndex ++ swap pivotElement dan elemen (storeIndex + 1) return storeIndex + 1

Contoh Python, Java dan C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Kompleksitas Quicksort

Kompleksitas Waktu

• Kompleksitas Kasus Terburuk (Big-O) : Ini terjadi ketika elemen pivot yang dipilih adalah elemen terbesar atau terkecil. Kondisi ini mengarah ke kasus di mana elemen pivot berada di ujung ekstrem dari larik yang diurutkan. Satu sub-larik selalu kosong dan sub-larik lainnya berisi elemen. Jadi, quicksort hanya dipanggil pada sub-larik ini. Namun, algoritme pengurutan cepat memiliki kinerja yang lebih baik untuk pivot yang tersebar.O(n2)
n - 1

• Kompleksitas Kasus Terbaik (Big-omega) : O(n*log n)
  Ini terjadi ketika elemen pivot selalu merupakan elemen tengah atau dekat dengan elemen tengah.
• Average Case Complexity (Big-theta) : O(n*log n)
  Terjadi jika kondisi di atas tidak terjadi.

Kompleksitas Ruang

Kompleksitas ruang untuk quicksort adalah O(log n).

Aplikasi Quicksort

Quicksort diimplementasikan saat

• bahasa pemrogramannya bagus untuk rekursi
• kompleksitas waktu itu penting
• kompleksitas ruang itu penting