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 nổi bọt. Nội dung bài viết bao gồm các phần sau:

• Ý tưởng của thuật toán
• Ví dụ minh họa
• Minh họa thuật toán sử dụng ngôn ngữ C++
• Đánh giá thuật toán

Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần theo thuật toán sắp xếp nổi bọt. 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

Bài viết liên quan:

• Sắp xếp dãy số theo thứ tự giảm dần, tăng dần trong C/C++
• Cây tìm kiếm nhị phân – Binary search tree
• Danh sách liên kết đơn – Single linked list

Ý tưởng của sắp xếp nổi bọt

Minh họa thuật toán sắp xếp nổi bọt

Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp.

Ví dụ minh họa

Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần. Lần lặp đầu tiên: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.

Lần lặp thứ 2: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.

Lần lặp thứ 3: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Code sắp xếp nổi bọt trong C/C++

// Code from https://blog.luyencode.net

include

void swap(int &x, int &y) {

int temp = x;  
x = y;  
y = temp;  

} // Hàm sắp xếp bubble sort void bubbleSort(int arr[], int n) {

int i, j;  
bool haveSwap = false;  
for (i = 0; i < n-1; i++){  
// i phần tử cuối cùng đã được sắp xếp  
    haveSwap = false;  
    for (j = 0; j < n-i-1; j++){  
        if (arr[j] > arr[j+1]){  
            swap(arr[j], arr[j+1]);  
            haveSwap = true; // Kiểm tra lần lặp này có swap không  
        }  
    }  
    // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm  
    if(haveSwap == false){  
        break;  
    }  
}  

} / Hàm xuất mảng / void printArray(int arr[], int size) {

int i;  
for (i=0; i < size; i++)  
    printf("%d ", arr[i]);  
printf("n");  

} // Driver program to test above functions int main() {

int arr[] = {64, 34, 25, 12, 22, 11, 90};  
int n = sizeof(arr)/sizeof(arr[0]);  
bubbleSort(arr, n);  
printf("Sorted array: n");  
printArray(arr, n);  
return 0;  

} Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa.

Kiểm tra kết quả:

Sorted array: 11 12 22 25 34 64 90

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

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

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

Nếu bạn đang cần học một ngôn ngữ lập trình, hay tìm tới các khóa học hay mà tôi chia sẻ ở mục khóa học nhé. Bạn hãy để lại các thắc mắc, ý kiến đóng góp nếu có xuống mục bình luận ở cuối bài viết nhé.

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.

Tại sao phải sắp xếp?

• Để có thể sử dụng thuật toán tìm nhị phân
• Để thực hiện thao tác nào đó được nhanh hơn

Các phương pháp sắp xếp thông dụng:

• Phương pháp Đổi chỗ trực tiếp (Interchange sort)
• Phương pháp Nổi bọt (Bubble sort)
• Phương pháp Chèn trực tiếp (Insertion sort)
• Phương pháp Chọn trực tiếp (Selection sort)

Interchange Sort

Khái niệm nghịch thế:

• Xét một mảng các số a[0], a[1], … a[n-1]
• Nếu có i a[j], thì ta gọi đó là một nghịch thế

Mảng chưa sắp xếp sẽ có nghịch thế

Mảng đã có thứ tự sẽ không chứa nghịch thế

a[0] <= a[1] <=… <=[n -1]

Nhận xé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à làm triệt tiêu dần chúng đi

Ý tưởng:

• 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ử tiếp theo trong dãy

void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
void InterchangeSort(int a[], int n){  
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
          if(a[i] > a[j])  //nếu có nghịch thế thì đổi chỗ
            Swap(a[i], a[j]);
}

Đánh giá:

• Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
• Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh

Bubble Sort

Ý tưởng:

• Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo
• Ở lần xử lý thứ i 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

void BubbleSort(int a[], int n){  
  for (int i = 0; i < n - 1; i++)
    for (int j = n - 1; j > i; j--)
       if(a[j] < a[j-1])
           Swap(a[j], a[j-1]);
}

Đánh giá:

• Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu
• Số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh

Khuyết điểm:

• Không nhận diện được tình trạng dãy đã có thứ tự hay có thứ tự từng phần
• Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm

Insertion Sort

Nhận xét:

• Mọi dãy a[0] , a[1] ,..., a[n-1] luôn có i-1 phần tử đầu tiên a[0] , a[1] ,... , a[i-2] đã có thứ tự (i ≥ 2)

Ý tưởng chính:

• Tìm cách chèn phần tử a[i] vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a[0] , a[1] ,... , a[i-1] trở nên có thứ tự
• Vị trí này chính là pos thỏa : a[pos-1] <= a[i ]< a[pos] (1 <= pos <= i)

void InsertionSort(int a[], int n){  
  int pos, x;
  for(int i = 1; i < n; i++){ //đoạn a[0] đã sắp
    x = a[i]; 
    pos = i;
    while(pos > 0 && x < a[pos-1]){
      a[pos] = a[pos-1];  // dời chỗ
      pos--;
    }
    a[pos] = x;
  }
}

Đánh giá:

• Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau:

Selection Sort

Nhận xét:

• Mảng có thứ tự thì a[i] = min(a[i], a[i+1], …, a[n-1])

Ý tưởng: mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế:

• 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 dãy hiện hành
• 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ử

void SelectionSort(int a[], int n)
{
  int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
  for (int  i = 0; i < n - 1; i++){
    min = i; 
    for(int j = i + 1; j < n; j++)
          if (a[j] < a[min])
           min = j; // ghi nhận vị trí phần tử nhỏ nhất
    if (min != i)
          Swap(a[min], a[i]);
  }
}

Đánh giá:

• Ở lượt thứ i, cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành
• Số lượng phép so sánh không phụ thuộc vào tình trạng của dãy số ban đầu
• Trong mọi trường hợp, số lần so sánh là:

Tạm kết

Như vậy là mình đã giới thiệu cho các bạn 4 thuật toán sắp xếp thông dụng. Ở phần tới mình sẽ giới thiệu thêm cho các bạn thêm các thuật toán sắp xếp khác.