Trong bài này mình sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đây là thuật toán sắp xếp được xem là nhành nhất trong các thuật toán mình đã giới thiệu trước đây.
Bạn đang xem: Thuật toán quicksort c++
Chúng ta sẽ cùng nhau tìm hiểu về sắp xếp nhanh là gì? Cũng như cách thức nó hoạt động và triển khai trong C++ như thế nào.
Ở cuối bài viết mình sẽ có một ví dụ sắp xếp trong mảng. Để những bạn vận dụng được thuật toán trong những bài tập trong thực tiễn .
Tóm Tắt
1. Sắp xếp nhanh (Quick Sort) là gì?
Về cơ bản thuật toán sắp xếp Quick Sort khá giống như Merge Sort. Đây là một thuật toán áp dụng cách thức chia để trị (Divide and Conquer).
Bài viết này được đăng tại
Thuật toán sẽ chọn mốt phần tử trong mảng làm điểm đánh dấu (pivot). 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 bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại sẽ lớn hơn hoặc bằng pivot.
Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn pivot, có một số ít cách chọn như sau :Chọn phần tử đầu tiên của mảng.Chọn phần tử cuối cùng của mảng.Chọn phần tử có giá trị nằm giữa mảng.Chọn Random một phần tử của mảng.Chọn thành phần tiên phong của mảng. Chọn thành phần ở đầu cuối của mảng. Chọn thành phần có giá trị nằm giữa mảng. Chọn Random một thành phần của mảng .Trên đây là 1 số ít cách chọn thông dụng, được sử dụng nhiều nhất. Tùy thuộc vào bài toán mà ta chọn pivot cho tương thích .Các bạn hoàn toàn có thể xem hình minh họa dưới đây để hoàn toàn có thể hiểu hơn .Khi tất cả chúng ta chọn số 3 làm pivot, thì mảng được chia làm hai phần. Phần bên trái nhỏ hơn hoặc bằng 3, phần bên phải lớn hơn hoặc bằng 3, cả hai phần đều được sắp xếp tằng dần .
Tiếp tục chọn pivot cho mỗi phần. Phần bên trái có pivot là số 1 và phần bên phải có pivot là số 6.
Cứ như vậy tất cả chúng ta sẽ chia phần ra cho đến khi không chia được nữa và sắp xếp theo đúng thứ tự .
2. Thuật toán Quick Sort trong C++
Giải thích thuật toán
Trong phần này tất cả chúng ta có hai quá trình. Giai đoạn một là quá trình phân đoạn mảng ( partition ( ) ) và quá trình hai là quá trình sắp xếp ( quickSort ( ) ). Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số cuối cùng của mảng.Tạo hai biến là left và right để trỏ tới bên trái và bên phải của danh sách.Thực hiện so sánh các phần tử với pivot. Nếu 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ực hiện 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.
Xem thêm:
Thuật toán Quick Sort trong C++
Chọn pivot cho mảng, ở đây mình sẽ chọn pivot là số ở đầu cuối của mảng. Tạo hai biến là left và right để trỏ tới bên trái và bên phải của list. Thực hiện so sánh những thành phần với pivot. Nếu thành phần nhỏ hơn pivot thì di dời qua bên trái và ngược lại. Sau khi di dời triển khai việc làm sắp xếp những thành phần trong mảng con mới, trước khi liên tục phân đoạn tiếp theo. Xem thêm : Phương Trình Hoành Độ Giao Điểm Của 2 Đường Thẳng Y = 2X + 3 + M Và Y = X + 6Ở phần trên mình đã nêu ra những bước viết thuật toán. Để cụ thể hơn mình đã có chú thích rõ ràng, đơn cử trong từng dòng code trong thuật toán dưới đây. Các bạn hãy đọc thật kỹ nhé :
Hàm partition()
int partition (int arr<>, int low, int high){ int pivot = arr; // khai báo phần tử đánh dâu pivot int left = low; //khai báo biến bên trái int right = high – 1; //khai báo biến bên phải while(true){ while(left = phần tử pivot trong mảng while(right >= left && arr > pivot) right–; // tìm phần tử = right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp swap(arr, arr); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi. left++; // Vì left hiện tại đã xét, nên cần tăng right–; // Vì right hiện tại đã xét, nên cần giảm } swap(arr, arr); return left; // Trả về chỉ số sẽ dùng để chia đôi mảng}
Hàm quicksort()
void quickSort(int arr<>, int low, int high){ if (low
Hàm swap()
void swap(int &a, int &b){ int t = a; a = b; b = t;}
3. Ví dụ sắp xếp Quick Sort trong mảng
Để minh họa cho hình ảnh ở trên, mình sẽ làm ví dụ áp dụng thuật toán sắp xếp nhanh (Quick Sort). Sắp xếp các phần tử trong mảng arr<> = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần.Để minh họa cho hình ảnh ở trên, mình sẽ làm 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 .
Code mẫu:
#include#includeusing namespace std;//tạo hàm swap để tráo đổi các vị trívoid swap(int &a, int &b){ int t = a; a = b; b = t;} // phân đoạn trong mảngint partition (int arr<>, int low, int high){ int pivot = arr; // khai báo phần tử đánh dâu pivot int left = low; //khai báo biến bên trái int right = high – 1; //khai báo biến bên phải while(true){ while(left = phần tử pivot trong mảng while(right >= left && arr > pivot) right–; // tìm phần tử = right) break; // sau khi duyệt xong thì thoát khỏi vòng lặp swap(arr, arr); // nếu chưa xong thì sử dụng hàm swap() để tráo đổi. left++; // Vì left hiện tại đã xét, nên cần tăng right–; // Vì right hiện tại đã xét, nên cần giảm } swap(arr, arr); return left; // Trả về chỉ số sẽ dùng để chia đôi mảng} /* Hàm thực hiện giải thuật quick sort */void quickSort(int arr<>, int low, int high){ if (low
Kết quả:
Như vậy là tất cả chúng ta đã thực thi xong chương trình sắp xếp mảng bằng giải pháp Quick Sort. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nhanh ( Quick Sort ) trong C + +. Chúc những bạn triển khai thành công xuất sắc ! ! !
Source: https://final-blade.com
Category : Kiến thức Internet