Quick sort - Giải thuật sắp xếp nhanh trong C/C++

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

Giải thuật Quick sort

I. Ý nghĩa và công đoạn của Quick sort

1. Quick sort

Quick sort là một giải thuật sắp xếp mạnh mẽ. Nó hoạt động bằng cách chọn một phần tử làm điểm chốt, sau đó chia mảng thành hai phần, một phần nhỏ hơn hoặc bằng và một phần lớn hơn điểm chốt. Điều này tạo ra một quy trình lặp, giúp sắp xếp mảng một cách hiệu quả.

Quick sort - Thuật toán phân đoạn và chinh phục

• 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ử ở giữa mảng.
• Chọn ngẫu nhiên một phần tử của mảng.

2. Quick sort - Sắp xếp nhanh chóng

Mô tả:

• Chọn điểm đánh dấu cho mảng, ở đây mình sẽ chọn số cuối cùng của mảng.
• Tạo hai biến trái và phải để trỏ tới bên trái và bên phải của danh sách.
• So sánh các phần tử với điểm đánh dấu. Nếu nhỏ hơn thì dịch chuyển sang bên trái và ngược lại.
• Sau khi dịch chuyển, 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.

Chớ bỏ lỡ cơ hội sở hữu ốp lưng siêu xịn cho điện thoại với giá chỉ từ 10k.

II. Quick sort - Bí quyết sắp xếp nhanh chóng

1. Phác thảo thuật toán Quick sort

Sắp xếp nhanh Quick sort

Để kích hoạt Quick sort, ta cần tích hợp thêm những hàm sau:

Hàm Phân đoạn:

Hàm Phân đoạn

Hàm hoán đổi():

2. Đoạn mã minh họa

Đề: Để làm ví dụ cho hình ảnh trên, chúng ta sẽ á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.

Mã: Xem tại đây

liên kết mã nguồn: Thuật toán sắp xếp nhanh (Quick Sort) - Freetuts

Nhập và Xuất:

Nhập và Xuất

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