Sorting

3 minutes read

Sorting Algorithm

02/11/2019

This post is going to give you some interesting algorithm ralating sorting elements.

Problem Sorting an array $a$ consists of $n$ elements in increasing order.

I. $O(n^2)$ Algorithm

1. Interchange Sort

1for(int i=0; i<n; i++){
2    for(int j=i+1; j<n; j++){
3        if (a[j] < a[i]) swap(a[j], a[i]);
4    }
5}

2. Bubble Sort

Từng phần tử nổi lên như bong bóng vậy đó.

1for(int i=n-1; i>0; i--){
2	    for(int j=1; j<=i; j++){
3	        if (a[j] < a[j-1]) swap(a[j], a[j-1]);
4	    }
5	}

Ngoài ra còn có Insertion Sort, Selection Sort, Shaker Sort.

II. $O(n\ log(n))$ Algorithm

1. Quick Sort

Ý tưởng

  • Chọn 1 phần tử cần sort (pivot)
  • Sort phần tử đó: partition
  • Quick sort cho 2 bên pivot

Cài đặt
Tham khảo GFG, chọn phần tử cuối làm pivot cho dễ cài đặt.

 1int partition(int l, int r);
 2void quick_sort(int l, int r){
 3    if (l >= r) return;
 4    pi = partition(l, r);  //correct pos of pivot
 5    quick_sort(l, pi-1);
 6    quick_sort(pi+1, r);
 7}
 8int partition(int l, int r){
 9    int pivot = a[r];
10    int pivot_index = l;
11    for(int i=l; i<=r-1; i++){
12        if (a[i] < pivot){
13            swap(a[i], a[pivot_index]);
14            pivot_index++;
15        }
16    }
17    swap(a[pivot_index], a[r]);
18    return i;
19}

Lưu ý
Quick Sort có độ phức tạp trung bình là $O(n\ log(n))$ và worst case là $O(n^2)$ khi mảng đã được sort (kể cả tăng hay giảm).

2. Merge Sort

Ý tưởng

  • Chia mảng thành 2 phần left, right
  • Sort bên trái, Sort bên phải
  • Merge 2 bên lại.

Ý tưởng divide and conquer (DP), thao tác chính là thao tác merge đó mới chính là lúc sort thực sự.

Cài đặt Tham khảo GFG

 1//a[] là biến toàn cục rồi
 2void merge(int l, int m, int r);
 3void merge_sort(int l, int r){
 4    if (l >= r) return; //= is maximal roi
 5    int m = (l+r)/2;
 6    merge_sort(l, m);
 7    merge_sort(m+1, r);
 8    merge(l, m, r);
 9}
10void merge(int l, int m, int r){
11    int n1 = m-l+1;
12    int n2 = r-m;
13    int L[n1], R[n2]; //temp
14    for(int i=0; i<n1; i++){
15        L[i] = a[l+i];
16    }
17    for(int i=0; i<n2; i++){
18        R[i] = a[m+1+i];
19    }
20    int i = 0, j = 0, k = l;
21    while(i<n1 && j<n2){
22        if (L[i] <= R[j]) a[k++] = L[i++];
23        else a[k++] = R[j++];
24    }
25    while(i<n1)
26        a[k++] = L[i++];
27    while(j<n2) 
28        a[k++] = R[j++];
29}

$\rightarrow$ Merge Sort luôn có độ phức tạp $O(n\ log(n))$.

III. O(n) Algorithm

1. Counting Sort

Khi mà mảng chỉ gồm các small elements thì ta có thể dùng Counting Sort.
Ý tưởng
Nếu phần tử $x$ trước nó có $y$ phần tử nhỏ hơn thì nó phải nằm ở vị trí $y$ (based 0).
Cài đặt

 1int cnt[M]; //M = *max_element(a, a+n)
 2memset(cnt, 0, sizeof cnt);
 3for(int i=0; i<n; i++){
 4    cnt[a[i]]++;
 5}
 6for(int i=1; i<M; i++){
 7    cnt[i] += cnt[i-1];
 8}
 9int ans[n];
10for(int i=0; i<n; i++){
11    ans[--cnt[a[i]]] = a[i];  //base 0
12}
13for(int i=0; i<n; i++) a[i] = ans[i]; //copy answer

Còn 1 số thuật toán fast khác như Radix Sort, Flash Sort.