Struktur Data dan Algoritma - Quick Sort

Pengurutan cepat adalah algoritma pengurutan yang sangat efisien dan didasarkan pada partisi array data menjadi array yang lebih kecil. Sebuah array besar dipartisi menjadi dua array yang salah satunya menyimpan nilai yang lebih kecil dari nilai yang ditentukan, katakanlah pivot, berdasarkan partisi tersebut dibuat dan array lainnya menyimpan nilai yang lebih besar dari nilai pivot.

Quicksort mempartisi larik dan kemudian memanggil dirinya sendiri secara rekursif dua kali untuk mengurutkan dua sub larik yang dihasilkan. Algoritme ini cukup efisien untuk kumpulan data berukuran besar karena rata-rata dan kompleksitas kasus terburuknya masing-masing adalah O (n 2 ).

Partisi di Quick Sort

Representasi animasi berikut menjelaskan cara menemukan nilai pivot dalam array.

Nilai pivot membagi daftar menjadi dua bagian. Dan secara rekursif, kami menemukan pivot untuk setiap sub-daftar hingga semua daftar hanya berisi satu elemen.

Algoritma Pivot Sortir Cepat

Berdasarkan pemahaman kita tentang partisi dalam quick sort, sekarang kita akan mencoba menulis algoritma untuk itu, yaitu sebagai berikut.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Pseudocode Pivot Sortir Cepat

Pseudocode untuk algoritma di atas dapat diturunkan sebagai -

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Algoritma Pengurutan Cepat

Menggunakan algoritma pivot secara rekursif, kami berakhir dengan kemungkinan partisi yang lebih kecil. Setiap partisi kemudian diproses untuk penyortiran cepat. Kami mendefinisikan algoritma rekursif untuk quicksort sebagai berikut -

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Pseudocode Sortir Cepat

Untuk memahami lebih lanjut, lihat pseudocode untuk algoritma pengurutan cepat -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

Untuk mengetahui tentang implementasi quick sort dalam bahasa pemrograman C, silakan klik di sini .