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

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 từ 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à quy trình sắp xếp lại những thành phần trong một tập hợp theo một trình tự nào đó nhằm mục đích mục tiêu giúp quản trị và tìm kiếm những thành phần thuận tiện và nhanh gọn hơn. Điển hình như việc sắp xếp họ và tên của học viên theo bảng vần âm trong học tập, sắp xếp điểm số từ thấp tới cao trong những cuộc thi, … Như vậy có rất nhiều mục tiêu cần phải sắp xếp những thành phần 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à chiêu thức sắp xếp đơn thuần, dễ hiểu thường được dạy trong khoa học máy tính .
Giải thuật khởi đầu từ đầu của tập dữ liệu. Nó so sánh hai thành phần đầu, nếu thành phần đứng trước lớn hơn thành phần đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp thành phần tiếp theo cho đến cuối tập hợp tài liệu. Sau đó nó quay lại với hai thành phần đầ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 con cờ 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 khởi đầu gồm thành phần A [ 0 ] xem như đã sắp xếp, ta sẽ duyệt từ thành phần 1 đến n – 1, tìm cách chèn những thành phần đó vào vị trí thích hợp trong mảng bắt đầ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 thuầ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 thành phần nhỏ nhất trong n thành phần khởi đầu, đưa thành phần này về vị trí đúng là tiên phong của dãy hiện hành. Sau đó không chăm sóc đến nó nữa, xem dãy hiện hành chỉ còn n-1 thành phần của dãy bắt đầu, khởi đầu từ vị trí thứ 2. Lặp lại quy trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn một thành phần. Dãy bắt đầu có n thành phần, vậy tóm tắt sáng tạo độc đáo thuật toán là thực thi n-1 lượt việc đưa thành phần 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 những list ( hoặc bất kể cấu trúc tài liệu nào hoàn toàn có thể truy vấn 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ụ nổi bật 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ựa như .

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 sáng tạo độc đáo của chia để trị. Giải thuật dựa trên sáng tạo độc đáo : chọn một điểm làm mốc ( gọi tắt là pivot ), sắp xếp mọi thành phần bên trái mốc đều nhỏ hơn mốc và mọi thành phần 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, vận dụng tương tự như 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 thành phần .

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 những trường hợp phải tráo đổi vị trí của hai thành phần xa nhau trong giải thuật sắp sếp chọn. ( nếu như thành phần nhỏ hơn ở vị trí bên phải khá xa so với thành phần lớn hơn ở vị trí bên trái )
Trong Shell Sort, những thành phần tại một khoảng chừng đơn cử sẽ được sắp xếp. Khoảng cách giữa những thành phần đượ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 vào kiểu trình tự được sử dụng cho một mảng nguồn 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 hảo trong đó những mục được tàng trữ theo một thứ tự đặc biệt quan trọng 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(n2). 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
Bài viết trên đã trình làng đến bạn những 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 dụng thì hãy san sẻ với bè bạn và đừng quên để lại phản hồi phía bên dưới nhé !

Source: https://final-blade.com
Category : Kiến thức Internet