Game App
  • Game App
  • Sản phẩm
  • Tin tức
Đăng nhập
Giỏ hàng
Đã thêm vào giỏ hàng Xem giỏ hàng
Chọn vị trí để xem giá, thời gian giao:
Bạn đang ở tại Hồ Chí Minh?

Sửa

Giá và khuyến mãi đang lấy theo khu vực này.
X
Chọn địa chỉ nhận hàng

Khu vực đã chọn Thiết lập lại

Chọn Tỉnh/Thành
Vui lòng chọn Tỉnh/Thành bên dưới
Chọn Phường/Xã
Vui lòng chọn Phường/Xã bên dưới
Thay đổi địa chỉ khác    
not found

Không tìm thấy kết quả phù hợp

Hãy thử lại với từ khoá khác
Số nhà, tên đường Vui lòng cho Thế Giới Di Động biết số nhà, tên đường để thuận tiện giao hàng cho quý khách.
Đặt làm địa chỉ mặc định
Xác nhận địa chỉ
Thông tin giao hàng Thêm thông tin địa chỉ giao hàng mới Xác nhận
Xóa địa chỉ Bạn có chắc chắn muốn xóa địa chỉ này không? Hủy Xóa

Hãy chọn địa chỉ cụ thể để chúng tôi cung cấp chính xác giá và khuyến mãi

Chọn địa chỉ Đóng

Quick sort là gì? Thuật toán sắp xếp nhanh Quick sort trong C/C++

Đóng góp bởi Phạm Nguyễn Huy Cường Xét duyệt & biên tập: Nhóm nội dung Thế Giới Di Động. 19/03/2021

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

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.

Săn ngay Ốp lưng xịn cho dế xinh cực đẹp chỉ từ 10k

Săn ngay ốp lưng xịn cho dế xinh cực đẹp chỉ từ 10k

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

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

hàm 1

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 Partition

Hàm swap():

Hàm Swap

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

Input và Output

Xem thêm:

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!

Xem tất cả bình luận của bạn Tại đây

Tin tức liên quan

↑

Bạn vui lòng chờ trong giây lát...