Quick Sort là gì? Tìm hiểu chi tiết về Quick Sort

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Các thuật toán sắp xếp dữ liệu là một yếu tố quan trọng khá quan trọng trong lập trình, điển hình trong số đó là Quick Sort. Vậy Quick Sort là gì? Trong bài viết hôm nay, bạn hãy cùng Tino Group tìm hiểu về Quick Sort để xem cách thuật toán này triển khai và hoạt động như thế nào nhé!

Quick Sort là gì?

Khái niệm Quick Sort

Thuật toán Quick Sort ( Sắp xếp nhanh ) là một quy trình tiến độ có mạng lưới hệ thống để sắp xếp những thành phần của một mảng. Giống như Merge Sort, QuickSort là một thuật toán sử dụng phương pháp chia để trị ( Divide and Conquer algorithm ) .
Tên gọi “ Quick Sort ” ám chỉ thuật toán này có năng lực sắp xếp tài liệu nhanh hơn nhiều so với bất kể thuật toán sắp xếp truyền thống cuội nguồn nào khác. Tuy nhiên, Quick Sort không được không thay đổi vì thứ tự tương đối của những thành phần bằng nhau không được bảo vệ .
Quick-sort-la-gi

Cách thức hoạt động của Quick Sort

Thuật toán sẽ chọn ra một phần tử trong mảng để làm điểm đánh dấu gọi là pivot. Sau khi chọn được điểm đánh dấu, nó sẽ chia mảng đó thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng sẽ bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại luôn lớn hơn hoặc bằng pivot.

Sau đó, quy trình này được tái diễn đủ số lần cho đến khi những mảng nhỏ hoàn toàn có thể được sắp xếp một cách thuận tiện để tạo ra một tập tài liệu được sắp xếp vừa đủ .
Các nhiều phiên bản Quick Sort khác nhau chọn pivot theo những cách khác nhau. Tốc độ sắp xếp của thuật toán phải phụ thuộc vào vào việc lựa chọn pivot, có một số ít cách để chọn như sau :

  • Luôn chọn phần tử đầu tiên làm pivot.
  • Luôn chọn phần tử cuối cùng làm pivot
  • Chọn một phần tử ngẫu nhiên làm pivot.
  • Chọn vị trí ở giữa làm pivot.

Quick-sort-la-gi

Ứng dụng của thuật toán Quick Sort

Quick Sort phân phối một cách tiếp cận nhanh gọn và có chiêu thức để sắp xếp bất kể thứ gì. Sau đây là một số ít ứng dụng của Quick Sort

  • Máy tính thương mại: Được sử dụng trong các tổ chức chính phủ và tư nhân với mục đích phân loại dữ liệu khác nhau như sắp xếp tài khoản/hồ sơ theo tên hoặc theo ID, phân loại giao dịch theo thời gian hoặc địa điểm, phân loại file theo tên hoặc ngày tạo, v.v.
  • Tính toán số: Hầu hết các thuật toán được phát triển hiệu quả sử dụng hàng đợi ưu tiên và sắp xếp inturn để đạt được độ chính xác trong tất cả các phép tính.
  • Tìm kiếm thông tin: Thuật toán sắp xếp hỗ trợ tìm kiếm thông tin nhanh hơn và hiệu quả hơn

Độ phức tạp của Quick Short

Khi chọn một thuật toán sắp xếp, hiệu suất cao là một trong những yếu tố quan trọng nhất. Dưới đây là một số ít điểm hiệu suất cao của thuật toán Quicksort .

Độ phức tạp về thời gian của Quick Short

Trong những trường hợp tốt nhất, trung bình và xấu nhất, thuật toán Quick Sort thực thi với độ phức tạp O ( n ), O ( n log n ) và O ( n ^ 2 ) tương ứng. Đây là một trong những thuật toán sắp xếp hiệu suất cao nhất khi nói đến độ phức tạp về thời hạn .

Độ phức tạp về không gian của Quick Short

Độ phức tạp khoảng trống trung bình của Quick Sort là O ( log n ) và độ phức tạp khoảng trống trong trường hợp xấu nhất là O ( n ). Điều này ngang bằng với hầu hết những thuật toán sắp xếp phổ cập, nhưng thực chất của thuật toán đệ quy là chúng không tối ưu hóa việc sử dụng bộ nhớ .

Tối ưu hóa

Với bất kể thuật toán nào, thường có 1 số ít tối ưu hóa hoàn toàn có thể được vận dụng cho những trường hợp khác. Để bảo vệ rằng khoảng trống đã sử dụng được số lượng giới hạn ở O ( log n ), thuật toán hoàn toàn có thể được triển khai để đệ quy vào phía nhỏ hơn của phân vùng và cũng sử dụng đệ quy đuôi. Người ta cũng hoàn toàn có thể tiến hành một thuật toán sắp xếp tích hợp chuyển sang một thuật toán sắp xếp lặp đi tái diễn hoàn toàn có thể hiệu suất cao hơn về thời hạn cho những mảng nhỏ hơn .
Quick-sort-la-gi

Thuật toán Quick Sort trong ngôn ngữ lập trình C++

Mô tả thuật toán

Thuật toán sẽ có hai quy trình tiến độ. Giai đoạn đầu là phân đoạn mảng ( partition ( ) ) và quá trình sau là sắp xếp ( quickSort ( ) ) .

  • Chọn pivot cho mảng.
  • Tạo hai biến là left và right để trỏ đến bên trái và bên phải của danh sách.
  • Tiến hành so sánh các phần tử với pivot. Trong trường hợp phần tử nhỏ hơn pivot thì dịch chuyển qua bên trái và ngược lại.
  • Sau khi đã dịch chuyển thì tiến hành công việc sắp xếp các phần tử trong mảng con mới, trước khi tiếp tục phân đoạn tiếp theo.

Code thuật toán Quick Sort trong C++

Ở phần trên đã trình bài những bước viết thuật toán. Để chi tiết cụ thể hơn, bạn hãy tìm hiểu thêm những dòng code trong thuật toán dưới đây .

Hàm partition()

Quick-sort-la-gi

Hàm quicksort()

Quick-sort-la-gi

Hàm swap()

Quick-sort-la-gi

Ví dụ về Quick Sort trong mảng

Để minh họa cho hình ảnh ở trên, tất cả chúng ta hãy cùng làm một ví dụ vận dụng thuật toán sắp xếp nhanh ( Quick Sort ). Sắp xếp những thành phần trong mảng arr [ ] = { 9, – 3, 5, 2, 6, 8, – 6, 1, 3 } theo thứ tự tăng dần .

#include

#include

using namespace std;

void swap(int &a, int &b)

{

int t = a;

a = b;

b = t;

}

int partition (int arr[], int low, int high)

{

int pivot = arr[high];

int left = low;

int right = high - 1;

while(true){

while(left <= right && arr[left] < pivot) left++;

while(right >= left && arr[right] > pivot) right--;

if (left >= right) break;

swap(arr[left], arr[right]);

left++;

right--;

}

swap(arr[left], arr[high]);

return left;

}

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int index = partition(arr, low, high);

quickSort(arr, low, index - 1);

quickSort(arr, index + 1, high);

}

}

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++){

cout << arr[i];

cout<<"\t";

}

}

int main()

{

int arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3};

int n = sizeof(arr)/sizeof(arr[0]);

quickSort(arr, 0, n-1);

cout<<"Mảng sau khi được sắp xếp: \n";

printArray(arr, n);

cout<<"\n---------------------------------------\n";

cout<<"Chương trình này được đăng tại Freetuts.net";

}

Kết quả ta được :
Quick-sort-la-gi

Tại sao Quick Sort lại hiệu quả hơn Merge Sort?

Về không gian phụ trợ: Quick Sort là một thuật toán sắp xếp tại chỗ trong khi Merge Sort phải sử dụng thêm không gian. Sắp xếp tại chỗ có nghĩa là không có dung lượng lưu trữ bổ sung nào được sử dụng để thực hiện sắp xếp (ngoại trừ ngăn xếp đệ quy). Merge Sort yêu cầu một mảng tạm thời để hợp nhất các mảng đã sắp xếp, vì vậy Quick Sort trở thành tùy chọn tốt hơn.

Trường hợp xấu nhất: Trường hợp xấu nhất của Quick Sort là O (n2) có thể tránh được bằng cách sử dụng Quick Sort ngẫu nhiên. Lúc này sẽ có được trường hợp trung bình bằng cách chọn phần tử xoay ngẫu nhiên và cải thiện hiệu suất như Merge Sort

Thân thiện với bộ nhớ cache: Quick Sort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ cache vì thuật toán này có vị trí tham chiếu tốt khi được sử dụng cho các mảng.

Tóm lại, Quick Sort là một thuật toán sắp xếp rất hữu ích trong nhiều trường hợp và được sử dụng phổ biến hiện nay. Bài viết trên đã cung cấp cho bạn một số thông tin liên quan đến Quick Sort, hy vọng bạn sẽ áp dụng thuật toán này hiệu quả để sắp xếp dữ liệu nhé!

FAQs về Quick Sort

Có bao nhiêu loại thuật toán sắp xếp?

Quick Sort là một loại thuật toán sắp xếp trong rất nhiều loại khác nhau, mỗi loại sẽ có những ưu điểm riêng. Các thuật toán sắp xếp phổ cập trong JavaScript gồm :

  • Bubble Sort.
  • Selection Sort.
  • Insertion Sort.
  • Merge Sort.
  • Quick sort.
  • Bucket Sort.

Quick Sort có phải là một thuật toán ổn định không?

Quick Sort không phải là một thuật toán không thay đổi vì việc hoán đổi những thành phần được triển khai theo vị trí của pivot ( mà không xem xét vị trí bắt đầu của chúng ). Thuật toán sắp xếp được cho là không thay đổi nếu nó duy trì thứ tự tương đối của những bản ghi trong trường hợp những khóa bằng nhau .

Quick Sort có phải là một thuật toán tại chỗ không?

Quick Sort là một thuật toán tại chỗ, nghĩa là toàn bộ những số đều được sắp xếp trong chính mảng khởi đầu .

Tại sao nên sử dụng Quick Sort ngẫu nhiên?

Đôi khi, việc chọn thành phần ngoài cùng bên phải hoàn toàn có thể dẫn đến trường hợp xấu nhất. Trong những trường hợp như vậy, việc chọn một thành phần ngẫu nhiên làm trục xoay của bạn ở mỗi bước sẽ giảm Tỷ Lệ dẫn đến hành vi trong trường hợp xấu nhất .
Chúng ta sẽ có nhiều năng lực chọn những trục gần tâm của mảng hơn và khi điều này xảy ra, những nhánh đệ quy đồng đều hơn và do đó thuật toán kết thúc nhanh hơn rất nhiều .
Độ phức tạp thời hạn chạy dự kiến ​ ​ là O ( n log n ) vì những trục ngẫu nhiên đã chọn được cho là để tránh hành vi trong trường hợp xấu nhất .

CÔNG TY CỔ PHẦN TẬP ĐOÀN TINO

  • Trụ sở chính: L17-11, Tầng 17, Tòa nhà Vincom Center, Số 72 Lê Thánh Tôn, Phường Bến Nghé, Quận 1, Thành phố Hồ Chí Minh
    Văn phòng đại diện: 42 Trần Phú, Phường 4, Quận 5, Thành phố Hồ Chí Minh
  • Điện thoại: 0364 333 333
    Tổng đài miễn phí: 1800 6734
  • Email: [email protected]
  • Website: www.tino.org

5/5 – ( 1 bầu chọn )

admin