Algoritma QuickSort

Dalam tutorial ini, anda akan mengetahui cara kerja pintasan. Anda juga akan dapati contoh cepat yang berfungsi di C, C ++ Python dan Java.

Quicksort adalah algoritma berdasarkan pendekatan divide and winer di mana array dibahagikan kepada subarrays dan sub-array ini dipanggil secara berulang untuk menyusun elemen.

Bagaimana QuickSort Berfungsi?

  1. Unsur pangsi dipilih daripada tatasusunan. Anda boleh memilih unsur apa pun daripada tatasusunan sebagai elemen pangsi.
    Di sini, kami telah mengambil bahagian paling kanan (iaitu elemen terakhir) array sebagai elemen pangsi. Pilih elemen pangsi
  2. Unsur-unsur yang lebih kecil daripada elemen pangsi diletakkan di sebelah kiri dan unsur-unsur yang lebih besar daripada elemen pangsi diletakkan di sebelah kanan. Letakkan semua elemen yang lebih kecil di sebelah kiri dan lebih besar di sebelah kanan unsur pangsi
    Susunan di atas dicapai dengan langkah-langkah berikut.
    1. Penunjuk terpaku pada elemen pangsi. Unsur pangsi dibandingkan dengan elemen yang bermula dari indeks pertama. Sekiranya elemen lebih besar daripada elemen pangsi dicapai, penunjuk kedua ditetapkan untuk elemen tersebut.
    2. Sekarang, elemen pangsi dibandingkan dengan elemen lain (penunjuk ketiga). Sekiranya elemen yang lebih kecil daripada elemen pangsi dicapai, elemen yang lebih kecil ditukar dengan elemen yang lebih besar yang dijumpai sebelumnya. Perbandingan elemen pangsi dengan unsur lain
    3. Prosesnya berterusan sehingga elemen terakhir kedua tercapai.
      Akhirnya, elemen pangsi ditukar dengan penunjuk kedua. Tukar elemen pangsi dengan penunjuk kedua
    4. Sekarang bahagian kiri dan kanan elemen pangsi ini diambil untuk proses selanjutnya dalam langkah-langkah di bawah.
  3. Unsur pangsi sekali lagi dipilih untuk bahagian kiri dan kanan secara berasingan. Dalam sub-bahagian ini, elemen pangsi diletakkan di kedudukan kanannya. Kemudian, langkah 2 diulang. Pilih elemen pangsi pada setiap separuh dan letakkan di tempat yang betul menggunakan rekursi
  4. Sub-bahagian dibahagikan lagi kepada sub-bahagian yang lebih kecil sehingga setiap bahagian dibentuk daripada satu elemen.
  5. Pada ketika ini, susunan sudah disusun.

Quicksort menggunakan rekursi untuk menyusun sub-bahagian.

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

  • Bahagikan
    lokasi ini dibahagikan kepada subparts mengambil pivot sebagai titik pembahagian. Unsur-unsur yang lebih kecil daripada pangsi diletakkan di sebelah kiri pangsi dan unsur-unsur yang lebih besar daripada pangsi diletakkan di sebelah kanan.
  • Menaklukkan bahagian
    kiri dan kanan sekali lagi dipartisi menggunakan dengan memilih elemen pangsi untuknya. Ini dapat dicapai dengan memasukkan bahagian-bahagian ke dalam algoritma secara berulang.
  • Gabungkan
    Langkah ini tidak memainkan peranan penting dalam pintasan. Susunan tersebut sudah disusun pada akhir langkah penaklukan.

Anda boleh memahami cara kerja pintas dengan bantuan ilustrasi di bawah.

Menyusun elemen di sebelah kiri pangsi menggunakan rekursi Menyusun unsur di sebelah kanan pangsi menggunakan rekursi

Algoritma Susun Pantas

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmostIndex, bagian kanan ,Index ) tetapkan rightmostIndex sebagai pivotIndex storeIndex <- leftmostIndex - 1 untuk i <- leftmostIndex + 1 ke rightmostIndex if element (i) <elemen pivotElement swap (i) dan elemen (storeIndex) storeIndex ++ swiv pivotElement dan elemen (storeIndex + 1) returnIndex 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); )

Kerumitan Quicksort

Kerumitan Masa

  • Kerumitan Kes Terburuk (Big-O) : Ia berlaku apabila elemen pangsi yang dipilih sama ada unsur terbesar atau terkecil. Keadaan ini membawa kepada kes di mana unsur pangsi terletak pada hujung larik yang disusun. Satu sub-array sentiasa kosong dan satu sub-array mengandungi unsur - unsur. Oleh itu, quicksort dipanggil hanya pada sub-array ini. Walau bagaimanapun, algoritma jenis cepat mempunyai prestasi yang lebih baik untuk pivot yang tersebar.O(n2)
    n - 1

  • Kerumitan Kes Terbaik (Omega Besar) : O(n*log n)
    Ia berlaku apabila elemen pangsi selalu merupakan elemen tengah atau dekat dengan elemen tengah.
  • Kerumitan Kes Purata (Big-theta) : O(n*log n)
    Ia berlaku apabila keadaan di atas tidak berlaku.

Kerumitan Ruang

Kerumitan ruang untuk quicksort adalah O(log n).

Aplikasi Quicksort

Quicksort dilaksanakan apabila

  • bahasa pengaturcaraan baik untuk berulang
  • kerumitan masa penting
  • kerumitan ruang penting

Artikel menarik...