Sắp xếp nhanh

Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.

Tiến trình chia này diễn ra tiếp tục cho tới khi độ dài của các mảng con đều bằng 1. Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp trường hợp trung bình và trường hợp xấu nhất là O(nlogn) với n là số phần tử.

Minh họa cách chia trong giải thuật sắp xếp nhanh (Quick Sort)

Hình minh họa dưới đây minh họa cách tìm phần tử chốt trong mảng. Ở đây, chúng ta chọn phần tử chốt đứng ở cuối danh sách.

Phần tử chốt chia danh sách thành hai phần. Và sử dụng đệ qui, chúng ta tìm phần tử chốt cho các mảng con cho tới khi danh sách chỉ còn một phần tử.

Giải thuật phần tử chốt trong sắp xếp nhanh (Quick Sort)

Dựa vào cách chia danh sách trong giải thuật sắp xếp nhanh ở trên, chúng ta có thể viết một giải thuật như dưới đây.

Output:

Bước 1: Chọn phần tử chốt là phần tử có chỉ mục cao nhất (phần tử ở cuối danh sách)

Bước 2: Khai báo hai biến để trỏ tới bên trái và bên phải của danh sách, ngoại trừ phần tử chốt

Bước 3: Biến bên trái trỏ tới mảng con bên trái

Bước 4: Biến bên phải trỏ tới mảng con bên phải

Bước 5: Khi giá trị tại biến bên trái là nhỏ hơn phần tử chốt thì di chuyển sang phải

Bước 6: Khi giá trị tại biến bên phải là lớn hơn phần tử chốt thì di chuyển sang trái

Bước 7: Nếu không trong trường hợp cả bước 5 và bước 6 thì tráo đổi giá trị biến trái và phải

Bước 8: Nếu left ≥ right, thì đây chính là giá trị chốt mới

Giải thuật phần tử chốt mẫu trong sắp xếp nhanh (Quick Sort)

Từ các bước trên, chúng ta có thể suy ra code mẫu cho giải thuật sắp xếp nhanh (Quick Sort) như sau:

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 giải thuật phần tử chốt một cách đệ qui, chúng ta có thể kết thúc với các mảng con nhỏ hơn. Sau đó mỗi mảng con này có thể được xử lý với sắp xếp nhanh. Dưới đây, mình sử dụng giải thuật đệ qui cho sắp xếp nhanh:

Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách

Bước 2: Chia mảng bởi sử dụng phần tử chốt

Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái

Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải

Giải thuật mẫu cho Sắp xếp nhanh (Quick Sort)

Từ phần giải thuật trên, chúng ta có thể suy ra code mẫu cho giải thuật sử dụng đệ qui cho sắp xếp nhanh như sau:

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

- Hiếu Kiều -