[Thuật toán] Các thuật toán sắp xếp (Phần 1)

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). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số.

Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.

Mức độ hiệu quả của từng giải thuật phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến.

Có nhiều giải thuật sắp xếp: Selection sort, Insertion sort, Interchange sort, Bubble sort, Shaker sort, Binary Insertion sort, Shell sort, Heap sort, Quick sort, Merge sort, Radix sort…

I./ Thuât toán sắp xếp nổi bọt (Bubble Sort):

  • Ý tưởng

Ý tưởng chính của thuật toán là xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

  • Giải thuật

Bước 1: i=1; //Phần tử đầu tiên

Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ Array[n] đến Array[i]

Bước 3: i=i+1

Bước 4

* Nếu i < n, quay lại Bước 2.

* Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.

  • Cài đặt code C/C++

  • Đánh giá giải thuật: 

Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất n*(n-1)/2 0
Xấu nhất n*(n-1)/2 n*(n-1)/2

 Độ phức tạp = O(n2)

  • Giảm bớt vòng duyệt

Nếu trong một lần duyệt nào đó với một i cố định khi vòng lặp j kết thúc mà không cần phải đổi chỗ cặp phần tử nào, nghĩa là mọi cặp phần tử kề nhau đã đứng đúng thứ tự thì dãy đã được sắp xếp và không cần tiến hành vòng lặp tiếp theo. Do đó có thể dùng một cờ để kiểm soát việc này. Ta có một đoạn mã giả của thuật toán nổi bọt như sau:

  •  Video Demo

 II./ Thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort)

  • Ý tưởng:

Như đã biết, để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và triệt tiêu dần chúng đi.
Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chổ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử kế tiếp theo trong dãy.
  • Giải thuật:

Bước 1: i=1;/ Bắt đầu từ đầu dãy

Bước 2: j = i+1; // Tìm tất cả các phần tử Array[j]<Array[i],j>i

Bước 3:

Trong khi j<=N thực hiện

Nếu Array[j]<Array[i]: Array[i] <->Array[j]; 

j=j+1;

Bước 4:

i = i+1;

Nếu i<n: Lặp lại Bước 2

Ngược lại: Dừng.

  • Cài đặt code C/C++

  • Đánh giá thuật toán

Trường hợp Số lần so sánh Số lần hoán vị
Tốt nhất n*(n-1) / 2 0
Xấu nhất n*(n-1) / 2 n*(n-1) / 2

 Độ phức tạp = O(n2)

III./ Thuật toán sắp xếp chọn (Selection Sort)

  • Ý tưởng

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 1 phần tử.
Do 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.
  • Giải thuật

Bước 1: i = 0 ;

Bước 2: Tìm phần tử Array[min] nhỏ nhất trong dãy hiện hành từ Array[i] đến Array[n]

Bước 3: Đổi chỗ Array[i] và Array[min]

Bước 4

Nếu i < n – 1 thì 

i = i + 1;

Lặp lại bước 2;

Ngược lại: Dừng

  • Cài đặt code C/C++

  •   

    Đánh giá thuật toán

Trường hợp Số lần so sánh Số phép gán
Tốt nhất n*(n-1)/2 0
Xấu nhất n*(n-1)/2 3n*(n-1)/2

Độ phức tạp = O(n2)

  • Video Demo

(Còn tiếp….)

Share
  • nguyen ngoc minh

    trong vong lap if,ham hoan vi ban bi sai vi tri,tem=a[j] moi dung

Share