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

NỘI DUNG BÀI VIẾT

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.

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 đó.

Cuối cùng, phần tử chốt được hoán đổi 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.

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ị.

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 + 1Code 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(n²)
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.

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