Thuật toán Quick Sort là gì?


Thuật toán Quick Sort là gì?

Thuật toán Quick Sort là một thuật toán sắp xếp, còn được gọi là sắp xếp kiểu phân chia (Part Sort). Đây là một thuật toán hiệu quả dựa trên việc phân chia mảng dữ liệu thành các nhóm phần tử nhỏ hơn.

Phân loại: Giải thuật sắp xếp
Thời gian phức tạp: Trung bình O(n log n), Xấu nhất: O(n^2)
Phức tạp dữ liệu: Khác nhau tùy vào cách hiện thực
Phương pháp tối ưu: Thỉnh thoảng

Thuật toán Quick Sort 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 gọi là phần tử chốt. Kết quả sẽ là 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ột mảng bao gồm các phần tử lớn hơn phần tử chốt.

Có Thể Bạn Quan Tâm :   Thuế trước bạ ô tô là gì? Cách tính lệ phí trước bạ và lệ phí sang tên ô tô

Quá trình chia này được tiếp tục cho đến khi các mảng con có độ dài bằng 1. Hiện thực bằng đệ quy, sau khi sắp xếp các mảng con, ta sẽ có một mảng đã được sắp xếp hoàn chỉnh.

Kỹ thuật chọn phần tử chốt

Kỹ thuật chọn phần tử chốt có ảnh hưởng đến khả năng rơi vào vòng lặp vô hạn trong những trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt ở vị trí trung vị của danh sách. Khi đó, sau log2(n) lần chia, ta sẽ có các mảng con có độ dài bằng 1.

Dưới đây là một số cách chọn phần tử chốt:

  • Chọn phần tử đầu tiên hoặc phần tử cuối cùng làm phần tử chốt.
  • Chọn phần tử ở giữa danh sách làm phần tử chốt.
  • Chọn phần tử trung vị trong ba phần tử đầu tiên, ở giữa và cuối cùng làm phần tử chốt.
  • Chọn phần tử ngẫu nhiên làm phần tử chốt. Tuy nhiên, cách này có khả năng rơi vào trường hợp đặc biệt.
Có Thể Bạn Quan Tâm :   Ngoại lực là gì? Các nguồn năng lượng sinh ra ngoại lực là gì?

Ý tưởng của thuật toán Quick Sort

Khái niệm của thuật toán Quick Sort là gì
Khái niệm của thuật toán Quick Sort là gì
  1. Chọn phần tử chốt.
  2. Đặt hai biến con trỏ để duyệt từ hai phía của phần tử chốt.
  3. Biến bên trái trỏ đến từng phần tử trong mảng con bên trái của phần tử chốt.
  4. Biến bên phải trỏ đến từng phần tử trong mảng con bên phải của phần tử chốt.
  5. Khi biến bên trái nhỏ hơn phần tử chốt, di chuyển sang phải.
  6. Khi biến bên phải nhỏ hơn phần tử chốt, di chuyển sang trái.
  7. Nếu không có trường hợp 5 và 6 xảy ra, hoán đổi giá trị của hai biến trái và phải.
  8. Nếu trái lớn hơn phải, giá trị của trái là giá trị chốt mới.

Khái niệm của thuật toán Quick Sort là gì

Giải thuật

Dưới đây là chương trình mô phỏng thuật toán đệ quy viết bằng ngôn ngữ lập trình Java:

public class QuickSort {
  public static void main(String[] args) {
    int[] x = {6, 2, 3, 4, 5, 9, 1};
    printArray(x);
    int left = 0;
    int right = x.length - 1;
    quickSort(x, left, right);
    printArray(x);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (arr == null || arr.length == 0)
      return;
    if (left >= right)
      return;
      
    int middle = left + (right - left) / 2;
    int pivot = arr[middle];
    int i = left, j = right;
    
    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }
      while (arr[j] > pivot) {
        j--;
      }
      if (i <= j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
      }
    }
    
    if (left < j)
      quickSort(arr, left, j);
    if (right > i)
      quickSort(arr, i, right);
  }
  
  public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
}

Thông tin tham khảo:

  • https://en.wikipedia.org/wiki/Quicksort
  • http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html
Có Thể Bạn Quan Tâm :   Cơm Thố Là Gì? Món Cơm Thố Truyền Thống Thơm Ngon Hấp Dẫn

Bạn có thể quan tâm:

  • Các thuật toán sắp xếp mà lập trình viên cần biết
  • Thuật toán trong lập trình - Một số suy nghĩ
  • Tầm quan trọng của giải thuật trong xử lý các vấn đề

Điểm nổi bật về các nhà phát triển phần mềm hàng đầu trên TopDev

TopDev qua viblo

Back to top button