Review Quick sort là gì? Thuật toán sắp xếp nhanh Quick sort

Quick sort là thuật toàn được sử dụng khá phổ biến trong ngôn ngữ lập trình C++. Bài viết này sẽ giúp bạn làm chủ Quick sort một cách đơn giản và dễ hiểu nhất nhé

Quick sort

I. Khái niệm Quick sort

1. Quick sort

Quick sort là thuật toán sắp xếp, hoạt động theo cách sau: Chọn một phần tử trong mảng làm điểm đánh dấu và sau đó chia mảng thành hai mảng con bằng cách so sánh các phần tử trong mảng với điểm đánh dấu. Mảng 1 sẽ chứ các phần tử nhỏ hơn hoặc bằng điểm đánh dấu và mảng 2 sẽ gồm các phần tử lớn hơn điểm đánh dấu.

Quick sort là một thuật toán áp dụng cách thức chia để trị (Divide and Conquer). Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn điểm đánh dấu, tùy từng trường hợp sẽ có một số 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.

2. Giải thuật Quick sort

Giải thích:

• • Chọn điểm đánh dấu cho mảng, ở đây mình sẽ chọn điểm đánh sấu là số cuối cùng của mảng.

• • Tạo hai biến là trái và phải để 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 điểm đánh dấu. Nếu phần tử nhỏ hơn điểm đánh dấu 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.

II. Thuật toán sắp xếp nhanh Quick sort

1. Thiết kế thuật toán Quick sort

Quick sort

Để sử dụng Quick sort ta cần dùng thêm những hàm sau:

Hàm Partition:

Hàm Partition

Hàm swap():

2. Ví dụ code minh họa

Đề: Để 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.

Code: Xem tại đây

link code: Thuật toán sắp xếp nhanh (Quick Sort) – Freetuts

Input và Output:

Input và Output

Hy vọng bài viết này sẽ giúp bạn làm chủ được Quick sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công!