Trong các thuật toán sắp xếp, Bubble Sort và Shaker Sort là hai thuật toán sắp xếp có nhiều nét tương đồng, do đó 2 thuật toán thường được đề cập và đem so sánh để nhìn toàn vẹn hơn về 2 thuật toán này.
Tóm Tắt
Bubble Sort
Ý tưởng
Giả sử mảng ban đầu cần sắp xếp có N phần tử a1, a2, a3, …, aN.
Xét lần lượt 2 phần tử liền kề nhau bắt đầu từ cuối mảng.
- Nếu 2 phần tử này là nghịch thế của nhau
a[i] > a[i – 1], tiến hành hoán vị đổi chỗ hai phần tử này. - Lặp lại điều trên sẽ đem được phần tử nhỏ nhất lên đầu mảng và loại phần tử này ra khỏi mảng đang xét.
- Tiếp tục thực hiện lại các bước trên đối với mảng mới để đưa dần các phần tử nhỏ nhất về đầu mảng.
- Thực hiện lại các thao tác cho đến khi mảng đang xét chỉ còn 1 phần tử duy nhất.
Bubble Sort
Hiện thực
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á
Độ phức tạp trong trường hợp:
- Tốt nhất là
O(n). - Trung bình là
O(n
2
)
- Xấu nhất độ phức tạp là
O(n
2
)
Thuật toán không nhận diện được mảng đã sắp xếp.
Shaker Sort
Ý tưởng
Shaker Sort là một cải tiến của Bubble Sort.
Sau khi đưa phần tử nhỏ nhất về đầu mảng sẽ đưa phần tử lớn nhất về cuối dãy. Do đưa các phần tử về đúng vị trí ở cả hai đầu nên Shaker Sort sẽ giúp cải thiện thời gian sắp xếp dãy số do giảm được độ lớn của mảng đang xét ở lần so sánh kế tiếp.
Shaker Sort
Hiện thực
void shakerSort(int a[], int n)
{
int Left = 0;
int Right = n - 1;
int k = 0;
while (Left < Right)
{
for (int i = Left; i < Right; i++)
{
if (a[i] > a[i + 1])
{
swap(a[i], a[i + 1]);
k = i;
}
}
Right = k;
for (i = Right; i > Left; i--)
{
if (a[i] < a[i - 1])
{
swap(a[i], a[i - 1]);
k = i;
}
}
Left = k;
}
}
Đánh giá
Shaker Sort là một dạng nâng cao của Bubble Sort, độ phức tạp cho trường hợp:
- Tốt nhất là
O(n). - Xấu nhất là
O(n2). - Trung bình là
O(n
2
)
Thuật toán nhận diện được mảng đã sắp xếp.
Kết luận
Trong trường hợp mảng có các phần tử là [2, 3, 4, 5, 1] đối với Shaker Sort chỉ cần 1 lần duyệt là đưa các phần tử của mảng về đúng vị trí, còn với Bubble Sort cần tới 4 lần duyệt để đưa các phần tử về đúng vị trí.
Tuy nhiên, trong trường hợp mảng có ngẫu nhiên phần tử với thứ tự đảo lộn thì Bubble Sort và Shaker Sort cho thời gian sắp xếp gần tương đương nhau.
Vì vậy, có thể nói rằng Shaker Sort ưu thế hơn Bubble Sort trong trường hợp các phần tử trong mảng gần có thứ tự như trong ví dụ trên là mảng [2, 3, 4, 5, 1].
