Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Comb Sort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Comb Sort thông qua các phần sau.
Nội dung chính
1. Giới thiệu
Comb Sort chủ yếu là một cải tiến so với Bubble Sort. Sắp xếp bong bóng luôn so sánh các giá trị liền kề. Vì vậy, tất cả các nghịch đảo lần lượt bị loại bỏ. Comb Sort cải thiện trên Bubble Sort bằng cách sử dụng khoảng cách có kích thước lớn hơn 1. Khoảng trống bắt đầu với một giá trị lớn và thu hẹp theo hệ số 1,3 trong mỗi lần lặp cho đến khi nó đạt đến giá trị 1. Do đó, Comb Sort loại bỏ nhiều hơn một số lần đảo ngược bằng một hoán đổi và hoạt động tốt hơn Bubble Sort.
Hệ số thu nhỏ đã được thực nghiệm tìm thấy là 1,3 (bằng cách thử nghiệm Combsort trên hơn 200.000 danh sách ngẫu nhiên) [Nguồn: Wiki]
Mặc dù, nó hoạt động tốt hơn Bubble Sort ở mức trung bình, trường hợp xấu nhất vẫn là O (n2).
2. Code ví dụ với nhiều ngôn ngữ khác nhau
C++
// C++ implementation of Comb Sort
#include<bits/stdc++.h>
using namespace std;
// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
// Initialize gap
int gap = n;
// Initialize swapped as true to make sure that
// loop runs
bool swapped = true;
// Keep running while gap is more than 1 and last
// iteration caused a swap
while (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = false;
// Compare all elements with current gap
for (int i=0; i<n-gap; i++)
{
if (a[i] > a[i+gap])
{
swap(a[i], a[i+gap]);
swapped = true;
}
}
}
}
// Driver program
int main()
{
int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
int n = sizeof(a)/sizeof(a[0]);
combSort(a, n);
printf("Sorted array: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}
Java
// Java program for implementation of Comb Sort
class CombSort
{
// To find gap between elements
int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort arr[] using Comb Sort
void sort(int arr[])
{
int n = arr.length;
// initialize gap
int gap = n;
// Initialize swapped as true to make sure that
// loop runs
boolean swapped = true;
// Keep running while gap is more than 1 and last
// iteration caused a swap
while (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = false;
// Compare all elements with current gap
for (int i=0; i<n-gap; i++)
{
if (arr[i] > arr[i+gap])
{
// Swap arr[i] and arr[i+gap]
int temp = arr[i];
arr[i] = arr[i+gap];
arr[i+gap] = temp;
// Set swapped
swapped = true;
}
}
}
}
// Driver method
public static void main(String args[])
{
CombSort ob = new CombSort();
int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
ob.sort(arr);
System.out.println("sorted array");
for (int i=0; i<arr.length; ++i)
System.out.print(arr[i] + " ");
}
} Python
# Python program for implementation of CombSort
# To find next gap from current
def getNextGap(gap):
# Shrink gap by Shrink factor
gap = (gap * 10)/13
if gap < 1:
return 1
return gap
# Function to sort arr[] using Comb Sort
def combSort(arr):
n = len(arr)
# Initialize gap
gap = n
# Initialize swapped as true to make sure that
# loop runs
swapped = True
# Keep running while gap is more than 1 and last
# iteration caused a swap
while gap !=1 or swapped == 1:
# Find next gap
gap = getNextGap(gap)
# Initialize swapped as false so that we can
# check if swap happened or not
swapped = False
# Compare all elements with current gap
for i in range(0, n-gap):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap]=arr[i + gap], arr[i]
swapped = True
# Driver code to test above
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
combSort(arr)
print ("Sorted array:")
for i in range(len(arr)):
print (arr[i]),
C#
// C# program for implementation of Comb Sort
using System;
class GFG
{
// To find gap between elements
static int getNextGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort arr[] using Comb Sort
static void sort(int []arr)
{
int n = arr.Length;
// initialize gap
int gap = n;
// Initialize swapped as true to
// make sure that loop runs
bool swapped = true;
// Keep running while gap is more than
// 1 and last iteration caused a swap
while (gap != 1 || swapped == true)
{
// Find next gap
gap = getNextGap(gap);
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = false;
// Compare all elements with current gap
for (int i=0; i<n-gap; i++)
{
if (arr[i] > arr[i+gap])
{
// Swap arr[i] and arr[i+gap]
int temp = arr[i];
arr[i] = arr[i+gap];
arr[i+gap] = temp;
// Set swapped
swapped = true;
}
}
}
}
// Driver method
public static void Main()
{
int []arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
sort(arr);
Console.WriteLine("sorted array");
for (int i=0; i<arr.Length; ++i)
Console.Write(arr[i] + " ");
}
} Kết quả:
Sorted array:
-44 -6 0 1 3 4 8 23 28 56 Minh hoạ
Ta có các phần tử của mảng là
8, 4, 1, 56, 3, -44, 23, -6, 28, 0
Giá trị khoảng cách ban đầu = 10
Sau khi thu hẹp giá trị khe hở => 10 / 1,3 = 7;
8 4 1 56 3 -44 23 -6 28 0
-6 4 1 56 3 -44 23 8 28 0
-6 4 0 56 3 -44 23 8 28 1
Giá trị khoảng cách mới => 7 / 1,3 = 5;
-44 4 0 56 3 -6 23 8 28 1
-44 4 0 28 3 -6 23 8 56 1
-44 4 0 28 1-6 23 8 56 3
Giá trị khoảng cách mới => 5 / 1,3 = 3;
-44 1 0 28 4 -6 23 8 56 3
-44 1-6 28 4 0 23 8 56 3
-44 1-6 23 4 0 28 8 56 3
-44 1-6 23 4 0 3 8 56 28
Giá trị khoảng cách mới => 3 / 1,3 = 2;
-44 1-6 0 4 23 3 8 56 28
-44 1-6 0 3 23 4 8 56 28
-44 1-6 0 3 8 4 23 56 28
Giá trị khoảng cách mới => 2 / 1,3 = 1;
-44-6 1 0 3 8 4 23 56 28
-44-6 0 1 3 8 4 23 56 28
-44-6 0 1 3 4 8 23 56 28
-44-6 0 1 3 4 8 23 28 56
không cần hoán đổi nữa (Đã sắp xếp mảng)
3. Độ phức tạp
Độ phức tạp theo thời gian: Độ phức tạp của trường hợp xấu nhất của thuật toán này là O (n2) và độ phức tạp của trường hợp tốt nhất là O (n).
Không gian phụ trợ: O (1).
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
