Cấu trúc dữ liệu và thuật toán - Sắp xếp nhanh

Sắp xếp nhanh là một thuật toán sắp xếp hiệu quả cao và dựa trên việc phân chia mảng dữ liệu thành các mảng nhỏ hơn. Một mảng lớn được phân vùng thành hai mảng, một mảng chứa các giá trị nhỏ hơn giá trị đã chỉ định, chẳng hạn như pivot, dựa vào đó phân vùng được tạo và một mảng khác giữ các giá trị lớn hơn giá trị pivot.

Quicksort phân vùng một mảng và sau đó gọi chính nó đệ quy hai lần để sắp xếp hai mảng con kết quả. Thuật toán này khá hiệu quả đối với các tập dữ liệu có kích thước lớn vì độ phức tạp trung bình và trường hợp xấu nhất của nó lần lượt là O (n 2 ).

Phân vùng trong Sắp xếp nhanh

Sau đây biểu diễn động giải thích cách tìm giá trị tổng hợp trong một mảng.

Giá trị pivot chia danh sách thành hai phần. Và đệ quy, chúng tôi tìm tổng hợp cho mỗi danh sách con cho đến khi tất cả các danh sách chỉ chứa một phần tử.

Thuật toán Pivot Sắp xếp Nhanh

Dựa trên hiểu biết của chúng tôi về phân vùng theo kiểu sắp xếp nhanh, bây giờ chúng tôi sẽ cố gắng viết một thuật toán cho nó, như sau.

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

Phân loại nhanh Pivot Pseudocode

Mã giả cho thuật toán trên có thể được suy ra là:

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

Thuật toán sắp xếp nhanh

Sử dụng thuật toán pivot đệ quy, chúng tôi kết thúc với các phân vùng nhỏ hơn có thể. Mỗi phân vùng sau đó được xử lý để sắp xếp nhanh chóng. Chúng tôi định nghĩa thuật toán đệ quy cho quicksort như sau:

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

Mã giả sắp xếp nhanh

Để hiểu thêm về nó, hãy xem mã giả cho thuật toán sắp xếp nhanh -

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

Để biết về cách thực hiện sắp xếp nhanh trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .