Trong bài này bản thân sẽ giới thiệu thuật toán Quick Sort (sắp xếp nhanh), đấy là thuật toán thu xếp được xem như là nhành nhất trong số thuật toán mình đã reviews trước đây.

Bạn đang xem: Thuật toán quicksort c++

*


*

Chúng ta sẽ thuộc nhau mày mò về sắp xếp nhanh là gì? Cũng như phương pháp nó vận động và thực thi trong C++ như thế nào.

Ở cuối nội dung bài viết mình sẽ sở hữu được một ví dụ bố trí trong mảng. Để chúng ta áp dụng được thuật toán trong những bài tập thực 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 hệt như Merge Sort. Đây là 1 trong thuật toán áp dụng cách thức chia nhằm trị (Divide and Conquer).

Bài viết này được đăng tại


Thuật toán sẽ lựa chọn mốt thành phần trong mảng làm cho điểm khắc ghi (pivot). Lúc chọn ăn điểm đánh dấu, nó sẽ phân chia mảng thành hai mảng con bằng phương pháp so sánh cùng với pivot đang chọn. Một mảng bao hàm các phần tử bé dại hơn hoặc bởi pivot và mảng còn sót lại sẽ to hơn hoặc bởi pivot.

Tốc độ thu xếp của thuật toán tùy ở trong vào việc lựa chọn pivot, có một số trong những cách lựa chọn như sau:

Chọn bộ phận đầu tiên của mảng.Chọn thành phần cuối thuộc của mảng.Chọn phần tử có giá chỉ trị nằm trong lòng mảng.Chọn Random một trong những phần tử của mảng.

Trên đây là một số bí quyết chọn thông dụng, được thực hiện nhiều nhất. Tùy trực thuộc vào vấn đề mà ta lựa chọn pivot mang đến phù hợp.

Các chúng ta cũng có thể xem hình minh họa dưới đây để rất có thể hiểu hơn.

Khi chúng ta chọn số 3 làm cho pivot, thì mảng được chia thành hai phần. Phần hông trái bé dại hơn hoặc bằng 3, phần bên phải to hơn hoặc bằng 3, cả hai phần phần lớn được thu xếp tằng dần.

Tiếp tục lựa chọn pivot cho từng phần. Phần hông trái có pivot là tiên phong hàng đầu và phần bên phải tất cả pivot là số 6.

Cứ như vậy bọn họ sẽ phân chia phần ra cho tới khi không phân chia được nữa và thu xếp theo đúng vật dụng tự.

2. Thuật toán Quick Sort trong C++

Giải ưng ý thuật toán

Trong phần này họ có nhì giai đoạn. Tiến trình một là quy trình phân đoạn mảng (partition()) và quy trình hai là tiến độ sắp xếp (quickSort()).

lựa chọn pivot cho mảng, tại chỗ này mình sẽ lựa chọn pivot là số cuối cùng của mảng.Tạo hai vươn lên là là left và right nhằm trỏ tới bên trái và bên buộc phải của danh sách.Thực hiện so sánh các bộ phận với pivot. Nếu phần tử nhỏ dại hơn pivot thì dịch chuyển hẳn sang bên trái và ngược lại.Sau khi dịch chuyển thực hiện các bước sắp xếp các thành phần trong mảng con mới, trước khi thường xuyên 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

Thuật toán Quick Sort trong C++

Ở phần trên tôi đã nêu ra công việc viết thuật toán. Để cụ thể hơn tôi đã có ghi chú rõ ràng, ví dụ trong từng mẫu code trong thuật toán bên dưới đây. Chúng ta hãy đọc thật kỹ càng nhé:

Hàm partition()


int partition (int arr<>, int low, int high) int pivot = arr; // khai báo bộ phận đánh dâu pivot int left = low; //khai báo biến phía trái int right = high - 1; //khai báo phát triển thành bên bắt buộc while(true) while(left = bộ phận 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); // trường hợp chưa xong xuôi thì thực hiện hàm swap() để tráo đổi. Left++; // do left lúc này đã xét, nên cần tăng right--; // vì right hiện tại đã xét, nên buộc phải giảm swap(arr, arr); return left; // Trả về chỉ số sẽ dùng để làm chia song 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ụ bố trí Quick Sort vào mảng

Để minh họa đến hình hình ảnh ở trên, mình sẽ có tác dụng ví dụ áp dụng thuật toán sắp xếp nhanh (Quick Sort). Bố trí các thành phần trong mảng arr<> = 9, -3, 5, 2, 6, 8, -6, 1, 3 theo lắp thêm tự tăng dần.

Code mẫu:


#include#includeusing namespace std;//tạo hàm swap nhằm tráo đổi những vị trívoid swap(int &a, int &b) int t = a; a = b; b = t; // phân đoạn vào 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 phía bên trái int right = high - 1; //khai báo trở nên bên cần while(true) while(left = phần tử pivot trong mảng while(right >= left && arr > pivot) right--; // tìm thành phần = right) break; // sau khi duyệt xong thì thoát ra khỏi vòng lặp swap(arr, arr); // nếu như chưa kết thúc thì áp dụng hàm swap() nhằm tráo đổi. Left++; // bởi vì left bây giờ đã xét, nên phải tăng right--; // bởi right lúc này đã xét, nên yêu cầu giảm swap(arr, arr); return left; // Trả về chỉ số sẽ dùng để chia đôi mảng /* Hàm tiến hành giải thuật quick sort */void quickSort(int arr<>, int low, int high){ if (low
Kết quả:

Như vậy là chúng ta đã thực hiện chấm dứt chương trình sắp xếp mảng bằng phương thức Quick Sort. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nhanh (Quick Sort) vào C++. Chúc các bạn thực hiện thành công!!!