Các Thuật Toán Sắp Xếp C, C++ Phổ Biến Thường Gặp

Đóng góp bởi Đinh Nhật Tân 12/07/2021

Tải Dev-C++: Công cụ lập trình C++ cơ bản cho máy tính Windows Miễn phí Công cụ Nhà phát hành: Bloodshed Software5153 lượt xem

Trong ngôn ngữ lập trình, các thuật toán sắp xếp đóng một vai trò khá quan trọng trong việc tìm ra lời giải của bài toán sắp xếp. Vậy có bao nhiêu thuật toán sắp xếp cơ bản và phổ biến trong ngôn ngữ lập trình C và C++, hãy cùng theo dõi bài viết dưới đây nhé.

ngôn ngữ lập trình

I. Thuật toán sắp xếp là gì ?

Sắp xếp là khái niệm cơ bản trong tin học nói chung và trong chuyên ngành lập trình nói riêng. Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn. Điển hình như việc sắp xếp họ và tên của học sinh theo bảng chữ cái trong học tập, sắp xếp điểm số từ thấp tới cao trong các cuộc thi, ... Như vậy có rất nhiều mục đích cần phải sắp xếp các phần tử theo một trình tự.

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm). Và để dễ dàng cho việc nghiên cứu và học tập thì người ta thường gán các phần tử được sắp xếp là các chữ số.

II. Các thuật toán sắp xếp trong C, C++ cơ bản

1. Bubble Sort (Sắp xếp nổi bọt)

Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính.

Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa.

Sắp xếp nổi bọt

2. Insertion Sort (Sắp xếp Chèn)

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài.

Ý tưởng của thuật toán này như sau: ta có mảng ban đầu gồm phần tử A[0] xem như đã sắp xếp, ta sẽ duyệt từ phần tử 1 đến n – 1, tìm cách chèn những phần tử đó vào vị trí thích hợp trong mảng ban đầu đã được sắp xếp.

Sắp xếp chèn

3. Selection Sort (Sắp xếp chọn)

Sắp xếp chọn là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh tại chỗ

Ý tưởng của thuật toán như sau: Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn một phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy

Sắp xếp chọn

4. Merge Sort (Sắp xếp trộn)

Sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó.

Thuật toán này là ví dụ điển hình của thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945. Ý tưởng của thuật toán này như sau: chia đôi mảng thành hai mảng con, sắp xếp hai mảng con đó và trộn lại theo đúng thứ tự, mảng con được sắp xếp bằng cách tương tự.

Sắp xếp trộn

5. Quick Sort (Thuật toán sắp xếp nhanh)

Cũng là một thuật toán sắp xếp dựa trên ý tưởng của chia để trị. Giải thuật dựa trên ý tưởng: chọn một điểm làm mốc (gọi tắt là pivot), sắp xếp mọi phần tử bên trái mốc đều nhỏ hơn mốc và mọi phần tử bên phải đều lớn hơn mốc, sau khi xong ta được 2 dãy con bên trái và bên phải, áp dụng tương tự cách sắp xếp này cho 2 dãy con vừa tìm được cho đến khi dãy con chỉ còn 1 phần tử.

Thuật toán sắp xếp nhanh

III. Các thuật toán sắp xếp nâng cao

1. Shell Sort

Shell sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp sếp chèn.

Giải thuật này tránh được các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp sếp chọn. (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn ở vị trí bên trái)

Trong Shell Sort, các phần tử tại một khoảng cụ thể sẽ được sắp xếp. Khoảng cách giữa các phần tử được giảm dần dựa trên trình tự được sử dụng. Hiệu suất của kiểu sắp xếp Shell phụ thuộc vào kiểu trình tự được sử dụng cho một mảng đầu vào nhất định.

Shell Sort

2. Shaker Sort (Cocktail sort)

Là một cải tiến của bubble sort. ShakerSort sau khi đưa phần tử nhỏ/lớn nhất lên đầu dãy, sau đó lại đưa phần tử lớn/nhỏ nhất về cuối dãy. Như vậy, trong một lần duyệt, ShakerSort sẽ đưa ít nhất hai số về đúng với vị trí của nó. Trong trường hợp mảng có các phần tử là [2, 3, 4, 5, 1] đối với Shaker Sort chỉ cần 1 lần duyệt là đưa các phần tử của mảng về đúng vị trí, còn với Bubble Sort cần tới 4 lần duyệt để đưa các phần tử về đúng vị trí.

Tuy nhiên, trong trường hợp mảng có ngẫu nhiên phần tử với thứ tự đảo lộn thì Bubble Sort và Shaker Sort cho thời gian sắp xếp gần tương đương nhau. Vì vậy, có thể nói rằng Shaker Sort ưu thế hơn Bubble Sort trong trường hợp các phần tử trong mảng gần có thứ tự như trong ví dụ trên là mảng [2, 3, 4, 5, 1].

Shaker Sort

3. Heap Sort

Heap sort là kỹ thuật sắp xếp dựa trên so sánh dựa trên cấu trúc dữ liệu Binary Heap. Nó tương tự như sắp xếp lựa chọn, nơi đầu tiên chúng ta tìm phần tử lớn nhất và đặt phần tử lớn nhất ở cuối. Chúng ta lặp lại quá trình tương tự cho các phần tử còn lại.

Một Binary Heap là một cây nhị phân hoàn chỉnh trong đó các mục được lưu trữ theo một thứ tự đặc biệt sao cho giá trị trong nút cha lớn hơn (hoặc nhỏ hơn) so với giá trị trong hai nút con của nó

Ý tưởng của thuật toán này là: Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n²). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).

Heap Sort

4. Radix Sort (Sắp xếp cơ số)

Khác với các thuật toán sắp xếp so sánh, thuật toán sắp xếp theo cơ số (Radix Sort) là một thuật toán sắp xếp không so sánh. Cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện.

Thuật toán này được thực hiện dựa trên ý tưởng nếu một danh sách đã được sắp xếp hoàn chỉnh thì từng phần tử cũng sẽ được sắp xếp hoàn chỉnh dựa trên giá trị của các phần tử đó. Thuật toán này yêu cầu danh sách cần được sắp xếp để có thể so sánh thứ tự các vị trí vì thế sắp xếp theo cơ số không giới hạn ở tập số nguyên

RaDix sort

Xem thêm

Các kiểu dữ liệu trong C/C++ thường gặp

Cách tải và cài đặt IDE Dev-C++ mới nhất | Compiler C++

Tổng hợp các phím tắt trong Visual Studio Code giúp lập trình nhanh chóng

Bài viết trên đã giới thiệu đến bạn các thuật toán cơ bản và nâng cao trong C/C++ thường gặp. Nếu bạn thấy hữu ích thì hãy chia sẻ với bạn bè và đừng quên để lại bình luận phía bên dưới nhé!