1. Sắp xếp nổi bọt
Ý tưởng cơ bản:
Sắp xếp nổi bọt (Bubble Sort) là một thuật toán sắp xếp đơn giản. Thuật toán này lặp đi lặp qua dãy số cần sắp xếp, so sánh hai phần tử liền kề và hoán đổi chúng nếu chúng không theo đúng thứ tự. Quá trình này được tiếp tục cho đến khi không còn cặp phần tử nào cần hoán đổi, nghĩa là dãy đã được sắp xếp hoàn chỉnh.
Tên gọi của thuật toán này dễ hiểu: các bong bóng khí dưới nước ban đầu nhỏ, khi nổi lên mặt nước sẽ dần to ra. Mô hình này tương tự với cách thuật toán hoạt động.
Cách thức hoạt động của sắp xếp nổi bọt:
- So sánh hai phần tử liền kề.
- Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, hoán đổi chúng.
- Lặp lại quá trình này với tất cả các cặp phần tử liền kề, từ đầu đến cuối dãy. Sau bước này, phần tử lớn nhất sẽ nằm ở cuối dãy.
- Lặp lại quá trình trên với các phần tử còn lại, trừ phần tử cuối cùng đã được sắp xếp.
- Tiếp tục quá trình trên với số lượng phần tử giảm dần cho đến khi không còn cặp phần tử nào cần so sánh.
Phiên bản cơ bản của sắp xếp nổi bọt
/**
* Sắp xếp nổi bọt - phiên bản cơ bản
* @param arr Mảng cần sắp xếp
* @param length Số phần tử trong mảng
*/
public static void bubbleSort(Integer[] arr, int length) {
if (length <= 1) {
return;
}
// Thực hiện tối đa length lần duyệt
for (int i = 0; i < length; i++) {
// Duyệt từ đầu đến cuối trừ các phần tử đã được sắp xếp
for (int j = 0; j < length - i - 1; j++) {
// Nếu phần tử hiện tại lớn hơn phần tử tiếp theo, hoán đổi
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Phiên bản cải tiến của sắp xếp nổi bọt
Nếu trong một lần duyệt không có sự hoán đổi nào, điều đó có nghĩa là dãy đã được sắp xếp. Chúng ta có thể dừng thuật toán sớm để tiết kiệm thời gian.
/**
* Sắp xếp nổi bọt - phiên bản cải tiến
* @param arr Mảng cần sắp xếp
* @param length Số phần tử trong mảng
*/
public static void optimizedBubbleSort(Integer[] arr, int length) {
if (length <= 1) {
return;
}
boolean swapped;
// Thực hiện tối đa length lần duyệt
for (int i = 0; i < length; i++) {
swapped = false;
// Duyệt từ đầu đến cuối trừ các phần tử đã được sắp xếp
for (int j = 0; j < length - i - 1; j++) {
// Nếu phần tử hiện tại lớn hơn phần tử tiếp theo, hoán đổi
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Nếu không có sự hoán đổi nào trong lần duyệt này, dừng thuật toán
if (!swapped) {
break;
}
}
}
Giải thích thuật toán sắp xếp nổi bọt
Sắp xếp nổi bọt sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài cùng biến i đại diện cho số lần duyệt cần thực hiện, trong khi vòng lặp trong cùng biến j đại diện cho các chỉ số phần tử được so sánh trong mỗi lần duyệt [0, 1, ..., length-i]. Mỗi lần duyệt sẽ đặt phần tử lớn nhất ở cuối dãy, nên số lượng phần tử cần so sánh giảm dần. Hiểu rõ nguyên lý này sẽ giúp bạn dễ dàng triển khai thuật toán.
Phân tích hiệu suất sắp xếp nổi bọt
Giả sử có N phần tử trong mảng, lần đầu tiên cần N-1 lần so sánh, lần thứ hai cần N-2 lần, và tiếp tục như vậy. Tổng số lần so sánh là:
(N-1) + (N-2) + ... + 1 = N*(N-1)/2
Khi N rất lớn, số lần so sánh khoảng N²/2 (bỏ qua số trừ 1).
Nếu dữ liệu ngẫu nhiên, mỗi lần so sánh có 50% khả năng cần hoán đổi, nên số lần hoán đổi khoảng N²/4. Trong trường hợp xấu nhất (dữ liệu đã được sắp xếp ngược), mỗi lần so sánh đều cần hoán đổi.
Cả số lần so sánh và hoán đổi đều tỷ lệ với N². Theo ký hiệu Big O, ta có độ phức tạp thời gian là O(N²).
Chúng ta có thể nhận biết thuật toán có độ phức tạp O(N²) khi thấy một vòng lặp lồng trong vòng lặp khác. Vòng lặp ngoài thực hiện N lần, và mỗi lần vòng lặp trong thực hiện N lần (hoặc một phần N lần), dẫn đến tổng cộng N² lần thực hiện một thao tác cơ bản.
2. Sắp xếp chọn
Thuật toán sắp xếp chọn hoạt động bằng cách tìm phần tử nhỏ nhất từ các phần tử chưa được sắp xếp và đặt nó vào vị trí đúng. Quá trình này được lặp lại cho đến khi tất cả các phần tử được sắp xếp.
Các bước thực hiện:
- Tìm phần tử có giá trị nhỏ nhất trong dãy chưa được sắp xếp
- Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên của dãy chưa được sắp xếp
- Lặp lại bước 1 và 2 cho dãy còn lại (trừ phần tử đã được sắp xếp)
/**
* Sắp xếp chọn
* @param array Mảng cần sắp xếp
* @return Mảng đã được sắp xếp
*/
public static int[] selectionSort(int[] array) {
// Tổng cộng cần N-1 lần duyệt
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
// Tìm phần tử nhỏ nhất trong dãy chưa được sắp xếp
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j; // Ghi nhớ chỉ số của phần tử nhỏ nhất
}
}
// Đổi chỗ phần tử nhỏ nhất với phần tử ở vị trí i
if (minIndex != i) {
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
return array;
}
Phân tích hiệu suất sắp xếp chọn
Sắp xếp chọn thực hiện cùng số lần so sánh như sắp xếp nổi bọt: N*(N-1)/2, nhưng chỉ thực hiện tối đa N lần hoán đổi.
Khi N rất lớn, số lần so sánh là yếu tố chính, nên độ phức tạp thời gian cũng là O(N²) như sắp xếp nổi bọt. Tuy nhiên, do số lần hoán đổi ít hơn, sắp xếp chọn thường nhanh hơn sắp xếp nổi bọt. Khi N nhỏ, nếu thời gian hoán đổi lớn hơn nhiều so với thời gian so sánh, sắp xếp chọn sẽ rất nhanh.
3. Sắp xếp chèn
Ý tưởng của sắp xếp chèn trực tiếp là lấy từng phần tử chưa được sắp xếp và chèn vào vị trí thích hợp trong dãy đã được sắp xếp. Quá trình này tiếp tục cho đến khi tất cả các phần tử được chèn vào đúng vị trí.
Sắp xếp chèn còn có nhiều biến thể như sắp xếp chèn nhị phân, sắp xếp chèn danh sách liên kết, sắp xếp Shell, v.v. Trong bài này, chúng ta chỉ tập trung vào sắp xếp chèn trực tiếp.
/**
* Sắp xếp chèn trực tiếp
* @param array Mảng cần sắp xếp
* @return Mảng đã được sắp xếp
*/
public static int[] insertionSort(int[] array) {
// Bắt đầu từ phần tử thứ hai, phần tử đầu tiên mặc định đã được sắp xếp
for (int i = 1; i < array.length; i++) {
int key = array[i]; // Phần tử cần chèn
int j = i - 1;
// Dịch chuyển các phần tử lớn hơn key sang phải
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
// Chèn key vào vị trí đúng
array[j + 1] = key;
}
return array;
}
Phân tích hiệu suất sắp xếp chèn
Lần đầu tiên, thuật toán thực hiện tối đa 1 lần so sánh, lần thứ hai tối đa 2 lần, và tiếp tục như vậy, lần thứ N tối đa N-1 lần. Tổng số lần so sánh là 1 + 2 + 3 + ... + N-1 = N*(N-1)/2.
Giả sử trung bình chỉ một nửa số phần tử thực sự được so sánh để tìm điểm chèn, ta có N*(N-1)/4 lần so sánh. Theo ký hiệu Big O, độ phức tạp thời gian là O(N²).
Số lần sao chép xấp xỉ bằng số lần so sánh, nhưng một lần sao chép tốn ít thời gian hơn một lần hoán đổi. Vì vậy, với dữ liệu ngẫu nhiên, sắp xếp chèn nhanh gấp đôi sắp xếp nổi bọt và nhanh hơn sắp xếp chọn một chút.
Tuy nhiên, nếu cần sắp xếp theo thứ tự ngược, mỗi lần so sánh và di chuyển đều được thực hiện, và lúc này sắp xếp chèn không nhanh hơn sắp xếp nổi bọt.
Tổng kết
Cả ba thuật toán sắp xếp trên: nổi bọt, chọn và chèn đều có độ phức tạp thời gian O(N²) theo ký hiệu Big O. Thông thường, sắp xếp nổi bọt ít được lựa chọn hơn mặc dù dễ viết nhất, vì hiệu suất trung bình không tốt bằng sắp xếp chọn và chèn.
Sắp xếp chọn giảm thiểu số lần hoán đổi xuống mức thấp nhất, nhưng số lần so sánh vẫn lớn. Khi lượng dữ liệu nhỏ và việc hoán đổi tốn nhiều thời gian hơn so với so sánh, sắp xếp chọn là lựa chọn tốt.
Trong大多数情况下, khi lượng dữ liệu nhỏ hoặc đã gần như được sắp xếp, sắp xếp chèn là lựa chọn tốt nhất trong ba thuật toán này.
Sau này, chúng ta sẽ tìm hiểu các thuật toán sắp xếp nâng cao có độ phức tạp thời gian nhỏ hơn O(N²).