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

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

Giới thiệu

Thuật toán sắp xếp nhanh (Quick Sort) là thuật toán sắp xếp dựa trên nguyên tắc của Thuật toán chia để trị. Trong đó, mảng được chia thành các mảng con và các mảng con này được gọi đệ quy để sắp xếp các phần tử.

Không phải tự nhiên mà nó được gọi là thuật toán sắp xếp nhanh. So với các thuật toán sắp xếp phổ biến khác thì có lẽ hiệu năng của Quick Sort sẽ vượt trội hơn rất nhiều so với Bubble Sort, Selection Sort, Insertion Sort,…

Ý tưởng thuật toán sắp xếp nhanh

Bước 1

Một phần tử chốt được chọn từ mảng. Bạn có thể chọn bất kỳ phần tử nào từ mảng làm phần tử chốt.

Ở đây, chúng ta chọn phần tử nằm ở vị trí ngoài cùng bên phải (tức là phần tử nằm ở cuối mảng) của mảng làm phần tử chốt.

Thuật toán sắp xếp nhanh - Quick Sort
Chọn phần tử chốt

Bước 2

Các phần tử nhỏ hơn phần tử chốt được đặt ở bên trái và các phần tử lớn hơn phần tử chốt được đặt ở bên phải.

Thuật toán sắp xếp nhanh - Quick Sort
Đặt tất cả các phần tử nhỏ hơn ở bên trái và lớn hơn ở bên phải của phần tử chốt
  • Một con trỏ được cố định tại phần tử chốt. Phần tử chốt được so sánh với các phần tử bắt đầu từ chỉ mục đầu tiên. Nếu phần tử đó lớn hơn phần tử chốt thì đánh dấu nó, con trỏ thứ hai được đặt cho phần tử đó.
  • Bây giờ, phần tử chốt được so sánh với các phần tử khác (con trỏ thứ ba). Nếu phần tử đó nhỏ hơn phần tử chốt sẽ được hoán đổi với phần tử lớn hơn được tìm thấy trước đó.
Thuật toán sắp xếp nhanh - Quick Sort
So sánh phần tử chốt với các phần tử khác

Cuối cùng, phần tử chốt được hoán đổi với con trỏ thứ hai.

Thuật toán sắp xếp nhanh - Quick Sort
Hoán đổi phần tử chốt với con trỏ thứ hai

Bây giờ các phần con bên trái và bên phải của phần tử chốt này được thực hiện để xử lý thêm trong các bước bên dưới.

Bước 3

Các phần tử chốt lại được chọn cho các phần tử con bên trái và bên phải. Trong các phần tử con này, phần tử chốt được đặt vào đúng vị trí của chúng. Sau đó, bước 2 được lặp lại.

Thuật toán sắp xếp nhanh - Quick Sort
Chọn phần tử chốt của mỗi nửa và đặt vào đúng vị trí bằng cách sử dụng đệ quy

Bước 4

Các phần con lại được chia thành các phần con nhỏ hơn cho đến khi mỗi phần con được tạo thành từ một phần tử duy nhất.

Bước 5

Tại thời điểm này, mảng đã được sắp xếp.

Sắp xếp nhanh sử dụng đệ quy để sắp xếp các mảng con

Dựa trên nguyên tắc của thuật toán Thuật toán chia để trị, thuật toán sắp xếp nhanh có thể được giải thích như sau:

Chia

Mảng được chia thành các mảng con và lấy phần tử chốt làm điểm phân đoạn. Các phần tử nhỏ hơn phần tử chốt được đặt ở bên trái và các phần tử lớn hơn phần tử chốt được đặt ở bên phải.

Trị

Các phần con bên trái và bên phải lại được phân đoạn bằng cách chọn các phần tử chốt. Đệ quy cho đến khi không thể phân đoạn được nữa.

Kết hợp

Bước này không đóng vai trò quan trọng trong sắp xếp nhanh. Mảng đã được sắp xếp ở cuối bước trị.

Thuật toán sắp xếp nhanh - Quick Sort
Sắp xếp các phần tử ở bên trái của phần tử chốt bằng cách sử dụng đệ quy
Thuật toán sắp xếp nhanh - Quick Sort
Sắp xếp các phần tử ở bên phải của phần tử chốt bằng cách sử dụng đệ quy

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

quickSort(array, leftmostIndex, rightmostIndex) if (leftmostIndex < rightmostIndex) pivotIndex <- partition(array,leftmostIndex, rightmostIndex) quickSort(array, leftmostIndex, pivotIndex) quickSort(array, pivotIndex + 1, rightmostIndex) partition(array, leftmostIndex, rightmostIndex) set rightmostIndex as pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element[i] < pivotElement swap element[i] and element[storeIndex] storeIndex++ swap pivotElement and element[storeIndex+1] return storeIndex + 1
Code language: PHP (php)

Cài đặt thuật toán sắp xếp nhanh

function partition(array, low, high) { var pivot = array[high]; var i = low - 1; for (var j = low; j < high; j++) { if (array[j] <= pivot) { i++; var temp = array[i]; array[i] = array[j]; array[j] = temp; } } temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; } function quickSort(array, low, high) { if (low < high) { var pi = partition(array, low, high); quickSort(array, low, pi - 1); quickSort(array, pi + 1, high); } } var arr = [3, 5, -2, 14, -9, 30]; quickSort(arr, 0, arr.length - 1); console.log(arr);
Code language: PHP (php)

Kết quả

[-9, -2, 3, 5, 14, 30]
Code language: JSON / JSON with Comments (json)

Đánh giá thuật toán sắp xếp nhanh

Độ phức tạp thời gian:

  • Trường hợp xấu nhất: O(n2)
    Nó xảy ra khi phần tử chốt được chọn là phần tử lớn nhất hoặc nhỏ nhất. Điều kiện này dẫn đến trường hợp phần tử pivot nằm ở cuối cùng của mảng đã được sắp xếp. Một mảng con luôn trống và một mảng con khác chứa n – 1 phần tử. Do đó, Quick Sort chỉ được gọi trên mảng con này.
  • Trường hợp tốt nhất: O(n*log n)
    Nó xảy ra khi phần tử chốt luôn là phần tử giữa hoặc gần phần tử giữa.
  • Trường hợp trung bình: O(n*log n)
    Nó xảy ra khi các điều kiện trên không xảy ra.

Độ phức tạp không gian:

Độ phức tạp không gian của thuật toán sắp xếp nhanh là O(log n).

Ứng dụng của thuật toán sắp xếp nhanh

Thuật toán sắp xếp nhanh được sử dụng trong các trường hợp:

  • Được sử dụng ở mọi nơi mà không cần đến sự ổn định
  • Độ phức tạp thời gian quan trọng
  • Độ phức tạp không gian quan trọng

Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.


Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

Leave a Reply

Your email address will not be published. Required fields are marked *