Thuật toán sắp xếp
Khái niệm về thuật toán sắp xếp
Sắp xếp là một chuỗi các hành động bao gồm so sánh và đổi chỗ các phần tử của một cơ sở dữ liệu, sao cho số thứ tự của các phần tử trong cơ sở thu tuân theo một quy luật nhất định.
Tương tự chúng ta có được định nghĩa của thuật toán sắp xếp:
Thuật toán sắp xếp là một kế hoạch sắp xếp lại các phần tử trong một cơ sở dữ liệu, khiến chúng tuân theo một quy luật nhất định.
Một kế hoạch càng tốt, diễn biến của việc sắp xếp diễn ra càng nhanh.
Tại sao lại cần một kế hoạch? Quy ước rằng chúng ta cần sắp xếp một cơ sở dữ liệu theo sự tăng dần giá trị, xét các thuật toán sau đây.
Bogo sort
Với một tập dữ liệu cho trước, xáo trộn ngẫu nhiên vị trí của các phần tử, sau đó tập dữ liệu mới nhận được. Lặp lại quy trình tới khi tập dữ liệu đã cho được sắp xếp.
Kế hoạch của thuật toán này hoàn toàn là nhờ sự may mắn, độ phức tạp trung bình của nó là $O((N-1) \times (N!))$. Trong trường hợp tệ nhất nó có thể chạy tới vô hạn.
Implement của Bogo sort:
bool sorted(int a[], int n)
{
for(int i = 0; i < n - 1; i++)
{
if (a[i] > a[i + 1]) return false;
}
return true;
}
void bogo_sort(int *a, int n)
{
while (!sorted(a, n))
{
std::shuffle(a, a + n, std::default_random_engine(0));
}
}
Bubble sort
Duyệt tất cả các phần tử, đẩy phần từ nhỏ hơn lên trên, sau đó làm điều tương tự với tất cả các phần tử còn lại.
Sau mỗi lần chọn ra phần tử tiếp theo, chúng ta giảm đi một bước ở chu kì kế tiếp. Độ phức tạp của thuật toán: $O(N + (N - 1) + (N - 2) + ... 3 + 2 + 1) = O( \frac{N \times (N - 1)}{2}) = O(N^2)$. Thuật toán này vừa ổn định vừa chạy nhanh hơn Bogo sort rất nhiều, tuy nhiên nó vẫn là một thuật toán chậm.
Implement của Bubble sort:
void bubble_sort(int *a, int n)
{
for (int i = 0; i < n; i++)
{
int j = i;
while (j > 0)
{
if (a[j] >= a[j - 1]) break;
std::swap(a[j], a[j - 1]);
j--;
}
}
}Insertion sort
Duyệt tất cả các vị trí, với mỗi vị trí tìm phần tử duy nhất tương ứng với vị trí đó.
Độ phức tạp của thuật toán là $O(N^2)$.
Implement của Selection sort:
void selection_sort(int *a, int n){
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i] > a[j]) std::swap(a[i], a[j]);
}
}
}Merge sort
- Phân rã mảng đã cho thành 2 mảng con, nếu mảng con chứa nhiều hơn 1 phần tử, tiếp tục phân rã nó thành 2 mảng nhỏ hơn, lặp lại quy trình.
- Tại mức độ mảng con chỉ có 1 phần tử, so sánh 2 phần tử đó, sặp xếp lại chúng vào mảng cha.
- Với mỗi mảng có các mảng con nhiều hơn 2 phần tử, chúng ta sẽ thu được 2 mảng con đã được sắp xếp tăng dần. So sánh và sắp xếp lại vào mảng gốc bằng cách sử dụng hai con trỏ, chúng ta sẽ có mảng cha đã sắp xếp với độ phức tạp là $(O(length))$
- Từ 2 mảng con đã sắp xếp, tiếp tục ghép vào cho tới khi thu được 1 mảng hoàn chỉnh. Bạn có thể xem ví dụ để hiểu rõ hơn.
void merge_sort(int *a, int l, int r)
{
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
int b[r - l + 1];
int curr = 0, pointer_1 = l, pointer_2 = mid + 1;
while (pointer_1 <= mid && pointer_2 <= r)
{
if (a[pointer_1] < a[pointer_2])
{
b[curr] = a[pointer_1];
pointer_1++;
curr++;
}
else
{
b[curr] = a[pointer_2];
pointer_2++;
curr++;
}
}
while (pointer_1 <= mid)
{
b[curr] = a[pointer_1];
curr++;
pointer_1++;
}
while (pointer_2 <= mid)
{
b[curr] = a[pointer_2];
curr++;
pointer_2++;
}
for (int i = 0; i < r - l + 1; i++)
{
a[l + i] = b[i];
}
}
int main()
{
int a[5] = {5, 4, 2, 3, 1};
merge_sort(a, 0, 4);
for (int i = 0; i < 5; i++)
{
std::cout << a[i] << ' ';
}
std::cout << '\n';
}
Nhận xét
Đăng nhận xét