Các thuật toán chúng ta sẽ đề cập đến:
- Interchange Sort
- Selection Sort
- Insertion Sort
- Binary Insertion Sort
- Bubble Sort
- Shaker Sort
- Shell Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Radix Sort
1. Interchange Sort:
Đây là thuật toán rất quen thuộc khi chúng ta mới làm quen với lập trình.
Ý tưởng: Lấy một phần tử làm mốc, duyệt tất cả các phần tử đứng sau nó, phần tử nào có giá trị nhỏ hơn giá trị mốc thì đổi chỗ
void InterchageSort(int *a, int n)
{
int i, j, t;
for(i = 0; i < n - 1; i++)
{
for(j = i + 1; j < n; j++)
{
if(a[i] > a[j])
{
t = a[i]; a[i] = a[j]; a[j] = t;
}
}
}
}
2. Selection Sort:
Ý tưởng: Lấy một phần tử làm mốc, tìm phần tử có giá trị nhỏ nhất (nhỏ hơn giá trị mốc) đứng sau nó, rồi đổi chỗ.
void SelectionSort(int *a, int n)
{
int i, j, min, t;
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
if(a[j] < a[min])
min = j;
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
3. Insertion Sort:
Ý tưởng: Duyệt các phần tử từ vị trí thứ 1 đến n - 1, nếu giá trị tại phần tử i nhỏ hơn giá trị phần tử i - 1 thì tiến hành chèn (giá trị của i lấy giá trị của i - 1).
void InsertionSort(int *a, int n)
{
int i, j, x;
for(i = 1; i < n; i++)
{
x = a[i];
for(j = i - 1; j >= 0 && a[j] > x; j--)
a[j + 1] = a[j];
a[j + 1] = x;
}
}
4. Binary Insertion Sort:
Ý tưởng: Giống như Insertion Sort nhưng việc chèn không còn tuyến tính nữa mà là nhị phân (thời gian sắp xếp sẽ nhanh hơn).
void BinaryInsertionSort(int *a, int n)
{
int i, j, x, left, right, mid;
for(i = 1; i < n; i++)
{
x = a[i];
left = 0;
right = i - 1;
while(left <= right)
{
mid = (left + right) / 2;
if(x > a[mid])
left = mid + 1;
else
right = mid - 1;
}
for(j = i - 1; j > left; j--)
a[j + 1] = a[j];
a[j + 1] = x;
}
}
5. Bubble Sort:
Ý tưởng: Đẩy phần tử lớn nhất của mảng hiện hành về vị trí cuối.
void BubbleSort(int *a, int n)
{
bool check = true;
int i, j, t;
for(i = 0; i < n - 1 && check == true; i++)
{
check = false;
for(j = 0; j < n - 1 - i; j++)
if(a[j] > a[j + 1])
{
t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
check = true;
}
}
}
6. Shaker Sort:
Ý tưởng: Giống như Bubble Sort nhưng thay vì chỉ duyệt từ một đầu, nay ta duyệt từ cả hai đầu.
void ShakerSort(int *a, int n)
{
bool check = true;
int i, j, k, t;
for(k = 0; k < n / 2 && check == true; k++)
{
i = k;
j = n - 1 - k;
check = false;
while(j > k)
{
if(a[i] > a[i + 1])
{
t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
check = true;
}
if(a[j] < a[j - 1])
{
t = a[j]; a[j] = a[j - 1]; a[j - 1] = t;
check = true;
}
i++;
j--;
}
}
}
7. Shell Sort:
Ý tưởng: Giống như Insertion Sort nhưng thay vì chèn tuyến tính từng phần tử một, ta chọn phần tử chèn theo số bước (step).
Hiệu quả của thuật toán này phụ thuộc nhiều vào việc chọn step, đó có thể là dãy số nguyên tố, fibonaxi,...
void ShellSort(int *a, int n)
{
int i, j, x, step;
step = n / 2;
while(step > 0)
{
for(i = step; i < n; i++)
{
x = a[i];
for(j = i - step;j >= 0 && a[j] > x; j = j - step)
a[j + step] = a[j];
a[j + step] = x;
}
step = step / 2;
}
}
8. Quick Sort:
Ý tưởng: Lấy một phần tử làm trục, sắp xếp sao cho các phần tử đứng trước trục đều có giá trị nhỏ hơn giá trị trục, các phần tử đứng sau trục đều có giá trị lớn hơn giá trị trục.
Sắp xếp sẽ có hiệu quả hơn nếu chọn phần tử ở chính giữa làm trục.
void QuickSort(int *a, int left, int right)
{
int i, j, pivot, t;
pivot = a[(left + right) / 2];
i = left;
j = right;
while(i <= j)
{
while(a[i] < pivot)
i++;
while(a[j] > pivot)
j--;
if(i <= j)
{
t = a[i]; a[i] = a[j]; a[j] = t;
i++;
j--;
}
}
if(left < j)
QuickSort(a, left, j);
if(i < right)
QuickSort(a, i, right);
}
9. Merge Sort:
Ý tưởng: Từ hai mảng bị phân đôi đã có thứ tự, ta tiến hành trộn hai mảng đó thành một mảng duy nhất có thứ tự.
void Merge(int *a, int start1, int end1, int end2)
{
int *b, i, j, k;
b = new int [end2 - start1 + 1];
if(b == NULL)
return;
i = start1;
j = end1 + 1;
k = 0;
while(i <= end1 && j <= end2)
{
if(a[i] > a[j])
b[k++] = a[j++];
else
b[k++] = a[i++];
}
while(i <= end1)
b[k++] = a[i++];
while(j <= end2)
b[k++] = a[j++];
for(i = end2; i >= start1; i--)
a[i] = b[--k];
}
void MergeSort(int *a, int left, int right)
{
int mid = (left + right) / 2;
if(left < mid)
MergeSort(a, left, mid);
if(mid + 1 < right)
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right);
}
10. Heap Sort:
Ý tưởng: Tổ chức mảng như cây nhị phân gần đầy, mỗi nút có nhiều nhất là hai nút con sao cho giá trị nút cha lớn hơn giá trị của hai nút con. Xóa nút gốc, đưa nút cuối cùng lên làm gốc rồi tạo lại cây.
void ShiftDown(int *a, int left, int right)
{
int k, t;
while(left * 2 + 1 <= right)
{
k = left * 2 + 1;
if(k + 1 <= right && a[k] < a[k + 1])
k = k + 1;
if(a[k] < a[left])
return;
else
{
t = a[k]; a[k] = a[left]; a[left] = t;
left = k;
}
}
}
void HeapSort(int *a, int n)
{
int i, t;
for(i = (n - 2) / 2; i >= 0; i--)
ShiftDown(a, i, n - 1);
i = n - 1;
while(i > 0)
{
t = a[0]; a[0] = a[i]; a[i] = t;
í--;
ShiftDown(a, 0, i);
}
}
11. Radix Sort:
Ý tưởng: Sắp xếp các số lần lượt theo chữ số ở hàng đơn vị, chục, trăm,...
void RadixSort(int *a, int n)
{
int i, max, k;
int *b = new int [n];
if(b == NULL)
return;
max = a[0];
k = 1;
for(i = 1; i < n; i++)
{
if(a[i] > max)
max = a[i];
}
while(max / k > 0)
{
int c[10] = {0};
for(i = 0; i < n; i++)
c[a[i] / k % 10]++;
c[i] += c[i - 1];
for(i = n - 1; i >= 0; i--)
b[--c[a[i] / k % 10]] = a[i];
for(i = 0; i < n; i++)
a[i] = b[i];
k = k * 10;
}
}
- Từ những điều trên, ta có thể tính thời gian sắp xếp của mỗi thuật toán để tìm ra cách hiệu quả và phù hợp nhất. Hãy xây dựng hàm phát sinh mảng ngẫu nhiên và tính thời gian.
- Gợi ý:
int main()
{
int *a, n;
//Tạo mảng ngẫu nhiên
clock_ t start, end;
start = clock();
//Gọi thuật toán
end = clock();
cout<<"Time = "<< (float)(end - start) / CLOCKS_PER_SEC<<" s"<<endl;
}
0 nhận xét:
Đăng nhận xét