Thuật toán sắp xếp quick sort – Code thuật toán quick sort C/C++

2
233

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++.

Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp quick sort. Một thuật toán ngay từ cái tên đã cho thấy rằng nó có khả năng sắp xếp với tốc độ cao hơn hẳn so với các thuật toán Insertion sort, selection sort hay bubble sort.

Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu

Ý tưởng của thuật toán sắp xếp quick sort

Mô phỏng thuật toán sắp xếp quick sort
Mô phỏng thuật toán sắp xếp quick sort

Giống như Merge sort, thuật toán sắp xếp quick sort là một thuật toán chia để trị( Divide and Conquer algorithm). Nó chọn một phần tử trong mảng làm điểm đánh dấu(pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot đã chọn. Việc lựa chọn pivot ảnh hưởng rất nhiều tới tốc độ sắp xếp. Nhưng máy tính lại không thể biết khi nào thì nên chọn theo cách nào. Dưới đây là một số cách để chọn pivot thường được sử dụng:

  1. Luôn chọn phần tử đầu tiên của mảng.
  2. Luôn chọn phần tử cuối cùng của mảng. (Được sử dụng trong bài viết này)
  3. Chọn một phần tử random.
  4. Chọn một phần tử có giá trị nằm giữa mảng(median element).

Tầm quan trọng của phân đoạn trong thuật toán quick sort

Mấu chốt chính của thuật toán sắp xếp quick sort là việc phân đoạn dãy số (Xem hàm partition()). Mục tiêu của công việc này là: Cho một mảng và một phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. Di chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang bên trái vị trí của x, và di chuyển tất cả các phần tử của mảng mà lớn hơn x sang bên phải vị trí của x.

Khi đó ta sẽ có 2 mảng con: mảng bên trai của x và mảng bên phải của x. Tiếp tục công việc với mỗi mảng con(chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.

Thuật toán phân đoạn

Đặt pivot là phần tử cuối cùng của dãy số arr. Chúng ta bắt đầu từ phần tử trái nhất của dãy số có chỉ số là left, và phần tử phải nhất của dãy số có chỉ số là right -1(bỏ qua phần tử pivot). Chừng nào left < right mà arr[left] > pivot và arr[right] < pivot thì đổi chỗ hai phần tử left và right. Sau cùng, ta đổi chỗ hai phần tử left và pivot cho nhau. Xem hình minh họa phía dưới. Khi đó, phần tử left đã đứng đúng vị trí và chia dãy số làm đôi(bên trái và bên phải)

Minh họa quá trình phân đoạn trong thuật toán quick sort
Minh họa quá trình phân đoạn trong thuật toán quick sort

Code minh họa thuật toán phân đoạn

Ví dụ cho quá trình phân đoạn

Quy trình của thuật toán sắp xếp quick sort

Code minh họa hàm quickSort

Minh họa thuật toán sắp xếp quick sort sử dụng ngôn ngữ C++

Kết quả chạy thử:

Đánh giá thuật toán sắp xếp quick sort

Độ  phức tạp thuật toán

  • Trường hợp tốt: O(nlog(n))
  • Trung bình: O(nlog(n))
  • Trường hợp xấu: O(n^2)

Không gian bộ nhớ sử dụng: O(log(n))

2 BÌNH LUẬN

    • Nếu bạn dùng để học và mới học thì nên sử dụng Codeblock hoặc DevC. Hoặc muốn sử dụng nhiều tính năng thì dùng Visual Studio của MS nhưng bản cài nặng.
      Ngoài ra, Visual Studio Code cũng là một lựa chọn tốt nhưng cần am hiểu chút.
      Mình chỉ dùng code viết cho blog và đang dùng devC.

ĐỂ LẠI BÌNH LUẬN

Vui lòng nhập nội dung bình luận
Vui lòng nhập tên