Ninja IT

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

Sắp xếp nổi bọt (bubble sort)

So sánh các phần tử liên tiếp nhau để đưa phần tử nhỏ nhất về đầu dãy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

/**
 * @param arr là array
 * @param length là số lượng phần tử trong array
 */
void bubbleSort(int* arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = n - 1; j > i; j--) {
      if (arr[j] < arr[j - 1]) {
        // swap
        int temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
      }
    }
  }
}

Độ phức tạp của thuật toán là O(n2).

Sắp xếp đổi chỗ

Xuất phát từ đầu dãy, lần lượt so sánh phần tử đầu dãy với các phần tử còn lại, nếu thấy lớn hơn thì đổi chỗ cho nhau, mục đích là để sau khi quét một lượt, phần tử bé nhất sẽ về đầu dãy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void interchangeSort(int* arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      if (arr[i] > arr[j]) {
        // swap
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
      }
    }
  }
}
Độ phức tạp của thuật toán cũng là O(n2).

Sắp xếp chọn (selection sort)

Cũng là tìm phần tử bé nhất vào vị trí đầu tiên giống như hai thuật toán trên. Nhưng chúng ta không tráo đổi vị trí ngay mà tìm phần tử bé nhất xong rồi mới tráo đổi.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * @param arr là array
 * @param length là số lượng phần tử trong array
 */
void selectionSort(int* arr, int length) {
  for (int i = 0; i < length - 1; i++) {
    int jMin = i;
    for (int j = i; j < length; j++) {
      if (arr[j] < arr[jMin]) {
        jMin = j;
      }
    }
    swap(arr, i, jMin);
  }
}
Độ phức tạp của thuật toán cũng là là O(n2), tuy nhiên số lần đổi chỗ thì ít hơn.

Sử dụng thuật toán

Ba thuật toán ở trên đều có số lần so sánh là (n-1)*n/2. Các thuật toán này hiệu quả nếu số lượng của mảng là nhỏ (từ 10 trở xuống). Nếu số lượng mảng lớn thì có thể dùng thuật toán sắp xếp trộn hoặc sắp xếp nhanh có độ phức tạp là O(n * log(n)).