[DSA] Sắp xếp (phần 1)

1. Giới thiệu về BigO

"Big O" là một khái niệm trong lý thuyết độ phức tạp tính toán. Nó được sử dụng để mô tả độ phức tạp thời gian của một thuật toán hoặc một chương trình máy tính. Big O đo lường tốc độ tăng của số lượng thao tác (hoặc thời gian) khi kích thước đầu vào của bài toán tăng lên.

Trong lý thuyết độ phức tạp tính toán, Big O được sử dụng để xác định giới hạn trên cho số lượng thao tác cần thực hiện bởi một thuật toán. Ví dụ, nếu một thuật toán có độ phức tạp thời gian O(n), điều đó có nghĩa là số lần thao tác cần thực hiện tăng lên tối đa là một hằng số lần số lượng đầu vào n.

Một số ví dụ về Big O:

• O(1) đại diện cho độ phức tạp thời gian cố định, không phụ thuộc vào kích thước đầu vào.
• O(n) đại diện cho độ phức tạp tuyến tính, thời gian tăng theo số lượng đầu vào.
• O(log n) đại diện cho độ phức tạp theo logarit, thời gian tăng chậm hơn so với số lượng đầu vào.
• O(n^2) đại diện cho độ phức tạp bậc hai, thời gian tăng nhanh hơn so với số lượng đầu vào.

Vì vậy, Big O là một công cụ quan trọng để đánh giá độ phức tạp của các thuật toán và giúp chúng ta lựa chọn thuật toán phù hợp cho bài toán cần giải quyết.

2. Giới thiệu về thuật toán sắp xếp

Các thuật toán sắp xếp là các thuật toán được thiết kế để sắp xếp một danh sách các phần tử theo một trật tự nhất định, ví dụ như sắp xếp các số theo thứ tự tăng dần hoặc giảm dần.

Các thuật toán sắp xếp là rất quan trọng trong các ứng dụng thực tế, vì việc sắp xếp dữ liệu là một phần không thể thiếu trong các thuật toán xử lý dữ liệu phức tạp, chẳng hạn như tìm kiếm, tra cứu hoặc tính toán.

3. Phân loại

Các thuật toán sắp xếp được chia thành hai loại chính:

• Thuật toán sắp xếp nội bộ (Internal sorting algorithm): là các thuật toán sắp xếp thực hiện việc sắp xếp trực tiếp trên một mảng hoặc một danh sách các phần tử trong bộ nhớ trong của máy tính.
• Thuật toán sắp xếp ngoại bộ (External sorting algorithm): là các thuật toán sắp xếp được thiết kế để sắp xếp các tập tin hoặc các dữ liệu lớn không thể lưu trữ trong bộ nhớ trong của máy tính.

Một số thuật toán sắp xếp nổi tiếng như:

• Bubble sort: đổi chỗ các phần tử liền kề nếu chúng không theo thứ tự, cho đến khi không còn phần tử nào đổi chỗ nữa.
• Selection sort: tìm phần tử nhỏ nhất trong danh sách và đưa nó vào vị trí đầu tiên, sau đó tìm phần tử nhỏ nhất trong danh sách còn lại và đưa nó vào vị trí thứ hai, và tiếp tục cho đến khi danh sách được sắp xếp hoàn chỉnh.
• Insertion sort: chèn mỗi phần tử vào đúng vị trí của nó trong danh sách đã sắp xếp trước đó.
• Merge sort: chia danh sách thành hai nửa đều nhau, sắp xếp từng nửa, sau đó trộn hai nửa đã sắp xếp với nhau để tạo ra danh sách đã sắp xếp hoàn chỉnh.
• Quick sort: chọn một phần tử pivot từ danh sách, chia danh sách thành hai phần dựa trên giá trị của pivot, sau đó sắp xếp hai phần này độc lập với nhau bằng cách sử dụng đệ quy.

4. Hiện thực các thuật toán

4.1. Sắp xếp nổi bọt - Bubble sort

Bubble sort là một thuật toán sắp xếp đơn giản và hiệu quả, hoạt động bằng cách so sánh các phần tử liên tiếp trong một danh sách và hoán đổi chúng nếu chúng không ở đúng thứ tự. Thuật toán được gọi là "Bubble" sort bởi vì các phần tử nhỏ hơn sẽ "nổi" lên trên như bong bóng nổi lên trên mặt nước.

Cách hoạt động của Bubble sort như sau:

• Bắt đầu từ phần tử đầu tiên, so sánh nó với phần tử kế tiếp. Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, hoán đổi chúng.
• Tiếp tục so sánh và hoán đổi các phần tử liên tiếp cho đến khi đến phần tử cuối cùng của danh sách.
• Lặp lại các bước 1 và 2 cho đến khi danh sách được sắp xếp hoàn toàn.

Bubble sort có độ phức tạp là O(n^2), tức là với một danh sách có n phần tử, Bubble sort sẽ thực hiện n(n-1)/2 lần so sánh. Do đó, Bubble sort thường được sử dụng cho các danh sách có kích thước nhỏ hoặc khi cần sắp xếp các danh sách có thứ tự ngẫu nhiên và không cần sắp xếp nhanh chóng. Tuy nhiên, với các danh sách đã được sắp xếp hoặc gần sắp xếp, Bubble sort có thể có hiệu quả cao hơn.

#include <stdio.h>

void bubble_sort(int arr[], int n) {

int i, j, temp;

for (i = 0; i < n - 1; i++) {

for (j = 0; j < n - i - 1; j++) {

if (arr[j] > arr[j + 1]) {

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

}

int main() {

int arr[] = {5, 2, 6, 1, 3};

int n = sizeof(arr) / sizeof(arr[0]);

printf("1. Original array: ");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf("\n");

bubble_sort(arr, n);

printf("==== After using Bubble Sort ==== \n2. Sorted array: ");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf("\n");

return 0;

}

Trong đó, hàm bubble_sort sử dụng hai vòng lặp for để duyệt qua danh sách và hoán đổi các phần tử khi cần thiết, tương tự như ví dụ Python ở trên. Hàm main khởi tạo một mảng số nguyên arr, sử dụng hàm bubble_sort để sắp xếp các phần tử của mảng đó, và sau đó in ra mảng chưa sắp xếp và mảng đã sắp xếp để kiểm tra kết quả.

4.2. Sắp xếp chọn (Selection sort)

Thuật toán sắp xếp chọn (Selection sort) là một thuật toán sắp xếp đơn giản và hiệu quả. Ý tưởng của thuật toán là chọn phần tử nhỏ nhất trong danh sách và đặt nó vào đầu danh sách. Sau đó, chọn phần tử nhỏ nhất tiếp theo và đặt nó vào vị trí thứ hai, và tiếp tục cho đến khi danh sách được sắp xếp hoàn toàn.

Cụ thể, thuật toán sắp xếp chọn hoạt động như sau:

• Duyệt qua từng phần tử của danh sách, bắt đầu từ phần tử đầu tiên.
• Tìm phần tử nhỏ nhất trong danh sách, bắt đầu từ vị trí hiện tại đến cuối danh sách.
• Hoán đổi phần tử nhỏ nhất vừa tìm được với phần tử ở vị trí hiện tại.
• Tăng vị trí hiện tại lên 1 và lặp lại các bước trên cho đến khi duyệt qua hết danh sách.

Độ phức tạp của thuật toán sắp xếp chọn là O(n^2), vì cần phải duyệt qua toàn bộ danh sách trong mỗi lần tìm kiếm phần tử nhỏ nhất.

#include <stdio.h>

void selectionSort(int arr[], int n);

int main()

{

int arr[] = { 38, 27, 43, 3, 9, 82, 10 };

int n = sizeof(arr) / sizeof(arr[0]);

printf("1. Unsorted array:");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf("\n");

selectionSort(arr, n);

printf("==== After using Selection Sort ==== \n2. Sorted array:");

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf("\n");

return 0;

}

void selectionSort(int arr[], int n)

{

int i, j, min_idx;

for (i = 0; i < n - 1; i++) {

min_idx = i;

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[min_idx]) {

min_idx = j;

}

}

int temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

}

}

Giải thích:

• Hàm selectionSort sẽ tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp và đổi chỗ nó với phần tử đầu tiên của mảng chưa được sắp xếp. Sau đó, thuật toán sẽ tiếp tục tìm phần tử nhỏ nhất trong các phần tử còn lại của mảng chưa được sắp xếp và đổi chỗ nó với phần tử thứ hai của mảng chưa được sắp xếp, và tiếp tục như vậy cho đến khi tất cả các phần tử của mảng được sắp xếp.