Bài viết được dịch từ http://qiita.com/hiso/items/5c36f50c7de61fe870a2

Khảo sát tổng thể các thuật toán sort

Trong số các thuật toán sort điển hình thì ổn nhất là O(nlogn)O(nlogn), dở nhất là O(n2)O(n2). Lý tưởng là O(n)O(n). Trong Sort so sánh thì cần có so sánh của O(nlogn)O(nlogn). Được phân loại theo công dụng, như insert, exchange, select, merge,...

Sau đây, tôi sẽ tổng hợp những tuật toán sort cơ bản đã được học.

Các thuật toán sort

• Bubble sort • Sellection sort • Counting Sort • Merge sort • Quick sort • Odd-even transposition sort

1. Bubble sort

Bubble sort là 1 thuật toán sort. Đây là phương pháp sort bằng cách vừa so sánh kích cỡ của các yếu tố có phù hợp với phần tử bên cạnh không vừa sắp xếp chúng lại. Xét về thời gian tính toán thì O(n2)O(n2) khá là chậm, nhưng do đây là thuật toán đơn giản, cách làm dễ, hơn nữa nó gần với xử lý song song nên thường được sử dụng. Nó được gọi là Sort nội bộ ổn định, hay có các cách gọi khác như Phương pháp exchange cơ bản, Phương pháp trao đổi liền kề.

◆Pseudo code

bubblesort(N)
  for i = 0 to N.length-1
    for j = N.length-1 downto i+1
      if N[j] < N[j-1]
        swap N[j] and N[j-1]

◆Ví dụ trong C

int* bubbleSort(int* N, int len){
  int i,j;

  for(i=0; i<len; i++){
    for(j=len-1; j>i; j--){
      if(N[j] < N[j-1]){
        temp = N[j];
        N[j] = N[j-1];
        N[j-1] = temp;
      }
    }
  }

  return N;
}

2. Sellection sort

Selection sort là 1 thuật toán tìm giá trị lớn nhất hoặc nhỏ nhất từ các phần tử và thay thế với phần tử cuối cùng của dãy. Xét về thời gian tính toán thì O(n2)O(n2) khá là chậm, nhưng do thuật toán đơn giản, cách làm dễ nên thường được sử dụng. Đây không phải là sort ổn định. Đây là thuật toán chọn phần tử nhỏ nhất trong chuỗi, di chuyển nó đến phía bên trái (Cụ thể là vị trí key). Rất dễ hiểu đúng không?

◆Pseudo code

SelectionSort(A)
for i = 0 to A.length-1
  mini = i
  for j = i to A.length-1
    if A[j] < A[mini]
        mini = j
  swap A[i] and A[mini]

◆Ví dụ trong C

int selectionSort(int len, int *a){

int i, j, mini, tmp, count=0;

for(i=0; i<len; i++){
mini = i;

for(j=i+1; j<len; j++){
if(a[j] < a[mini]){
mini = j;
}
}

if(mini != i){
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
count++;
}

}
return count;
}

3. Counting sort

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently. Wikipedia https://en.wikipedia.org/?title=Counting_sort worst case: O(n)O(n) Là phương pháp sort bằng cách đếm số lần xuất hiện của data, sau đó sắp xếp từ nhỏ cho đến lớn. Định nghĩa thì chắc là dễ hiểu, tuy nhiên, đoạn code hơi khó hiểu một chút.

◆Pseudo code

Counting-Sort(A, B, k)
  for i = 0 to k
    do C[i] = 0
  for j = 1 to length[A]
    do C[A[j]] = C[A[j]]+1
  /* C[i] now contains the number of elements equal to i */
  for i = 1 to k
  do C[i] = C[i] + C[i-1]
  /* C[i] now contains the number of elements less than or equal to i */
  for j = length[A] downto 1
   do B[C[A[j]]] = A[j]
   C[A[j]] = C[A[j]]-1

◆Ví dụ trong C

#include <stdio.h>

#define N 2000001

int B[N], C[N];

void countingSort(int A[], int B[], int k, int n){
  int i, j;

  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }   
  for(i = 1; i <= k; i++){
    C[i] = C[i] + C[i - 1];
  } 
  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  for(i = 1; i <= n; i++){
    printf("%d", B[i]);
    if(i != n) printf(" ");
  }
  printf("\n");

}

int main(){
  int A[N];
  int i, j, n, k = 0;

  //input
  scanf("%d", &n); 
  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }

  //sort and out
  countingSort(A, B, k, n);

  return 0;
}

4. Merge sort

Merde sort là 1 thuật toán sort bằng cách, nếu khi merge nhiều phần tử đã được sắp xếp sẵn vào 1 dãy mà sắp xếp theo thứ tự từ nhỏ đến lớn, thì dãy mới cũng được sắp xếp lại. Khi sort các array có chứa data nn phần tử, thì lượng tính toán tệ nhất là O(nlogn)O(nlogn). Thực tế cũng tùy thuộc vào cách làm phân chia hay tích hợp, nhưng thông thường thì có thể sort ổn định. In-place sort cũng được đưa ra, nhưng thường thì cần có lưu trữ bên ngoài O(n)O(n).

Khi merge sort, đầu tiên cần chia ra, sau đó kết hợp lại. Array sẽ được sort trong quá trình kết hợp.

◆Pseudo code

Merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  create array L[0...n1], R[0...n2]
  for i = 0 to n1-1
    do L[i] = A[left + i]
  for i = 0 to n2-1
    do R[i] = A[mid + i]
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

MergeSort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

◆Ví dụ trong C

#include<stdio.h>
#include<stdlib.h>

#define SENTINEL 1000000000

int count=0;

void mergeSort(int A[],int left,int right){
  int i,mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



void merge(int A[],int left,int mid,int right){
  int n1,n2,i,j,k;
  int *L,*R;
  n1=mid-left;
  n2=right-mid;
  L=(int *)malloc(sizeof(int)*(n1+1));
  R=(int *)malloc(sizeof(int)*(n2+1));
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[mid+j];
  }
  L[n1]=SENTINEL;
  R[n2]=SENTINEL;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
   if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
    else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
  free(L);
  free(R);
}


main(){
  int A[500000];
  int n,i;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A,0,n);
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i<n-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}

5. Quick Sort

Quick sort là thuật toán được phát triển bởi nhà khoa học máy tính Charles Antony Richard Hoare vào năm 1960. Lượng tính toán tốt nhất và tính toán trung bình là O(nlogn)O(nlogn). So với các phương pháp sort khác thì đây được coi là phương pháp nhanh nhất, tuy nhiên không phải do số data hay cách sắp xếp các đối tượng thì sẽ nhanh, lượng tính toán tệ nhất là O(n2)O(n2). Đây không phải là kiểu sort ổn định.

◆Pseudo code

Partition(A, p, r)
  x = A[r]
  i = p-1
  for j = p to r-1
    do if A[j] <= x
      then i = i+1
        exchange A[i] and A[j] 
  exchange A[i+1] and A[r]
  return i+1


Quicksort(A, p, r)
  if p < r
    then q = Partition(A, p, r)
      run Quicksort(A, p, q-1)
      run Quicksort(A, q+1, r)

◆Ví dụ trong C (Lấy từ Wikipedia)

typedef int value_type; 

value_type med3(value_type x, value_type y, value_type z)
/* Trả về giá trị trung gian của x, y, z  */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}

void quicksort(value_type a[], int left, int right)
/* Quick sort
 * a     : Array sort
 * left  : Vị trí bắt đầu của data sort
 * right : Ví trí kết thúc của data sort
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            i++; j--;
        }
        quicksort(a, left, i - 1);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right); /* 分割した右を再帰的にソート */
    }
}

6. Odd-even sort

Odd-even Sort là thuật toán cải thiện từ Bubble sort. Đây là phương pháp sort chuyển vị trí sau từng cặp, trái lại với việc tiến hành tuần tự 1 hướng với việc tiến hành tuần tự theo 1 hướng ở Bubble sort.
Giống với Bubble, Odd-even sort cũng là dạng sort nội bộ ổn định, lượng tính toán thời gian trong trường hợp tệ nhất là O(n2)O(n2). Việc so sánh từng cặp diễn ra động lập nên không giống với Bubble sort, Odd-even sort có thể tiến hành song song.

Odd-even sort là thuật toán ghép số lẻ và số lẻ sau nó thành 1 cặp (Pair1), sau khi so sánh/hoán đổi thì lặp lại việc so sánh/hoán đổi với cặp số chẵn và số chẵn sau số đó. Sau Pair1:（So sánh số thứ 1 và số thứ 2, So sánh số thứ 3 và số thứ 4, So sánh số thứ 5 và số thứ 6,....） thì tiến hành

Pair2:（So sánh số thứ 2 và số thứ 3, So sánh số thứ 4 và số thứ 5, So sánh số thứ 6 và số thứ 7,...) Và lặp lại chu trình này.

◆Pseudo code

◆Ví dụ trong C（Lấy từ Wikipedia）

int data[N] = { /* ... */ };
  int flag = 1;
  int i;

  while(flag) {
    flag = 0;
    for (i = 0; i < N-1; i += 2) { /* Pair1 */
      if (data[i] > data[i+1]) {
        swap(&data[i], &data[i+1]);
        flag = 1;
      }
    }
    for (i = 1;i < N-1;i += 2) { /* Pair2 */
      if (data[i] > data[i+1]) {
        swap(&data[i], &data[i+1]);
        flag = 1;
      }
    }
  }

Tóm tắt, khảo sát

Chắc hẳn tất cả các bạn đã biết được ưu điểm, nhược điểm của từng loại thuật toán rồi nhỉ.

△ Độ dễ đọc

Bubble sort > Sellection Sort > Odd-even sort > Quick sort > Merge sort > Counting Sort 　Đây chỉ là đánh giá chủ quan của tôi thôi.

△Lượng tính toán

• So sánh WorstCase 　Counting Sort > Quick sort >= Merge sort > Sellection sort >= Odd-even sort >= Bubble sort 　Bubble sort：O(n2)O(n2) 　Odd-even sort：O(n2)O(n2) 　Sellection sort：O(n2)O(n2) 　CountingSort：O(n)O(n) 　Merge sort：O(nlogn)O(nlogn) 　Quick sort：O(n2)O(n2) 　Nếu sử dụng giá trị trung tâm để so sánh Quick sort thì WorstCase sẽ là O(nlogn)O(nlogn). • Xem xét lượng tính toán đối với sắp xếp data 　Counting Sort > Merge sort >= Quick sort > Sellection sort >= Odd-even sort >= Bubble sort 　Bubble sort：Tệ nhất, cũng là tốt nhấtO(n2)O(n2) 　Odd-even sort：最悪、最良共にO(n2)O(n2) 　Sellection sort：最悪、最良共にO(n2)O(n2) 　CountingSort：最悪、最良共にO(n)O(n)の為最速 　Merge sort：最悪、最良共にO(nlogn)O(nlogn)の為極めて高速 　Quick sort：平均計算時間がO(nlogn)O(nlogn)の為極めて高速

△Lượng Memory cần thiết

Counting Sort > Merge sort > Quick sort > Sellection sort = Odd-even sort = Bubble sort 　 　Bubble sort：O(1)O(1) 　Odd-even sort；O(1)O(1) 　Sellection sort：O(1)O(1) 　CountingSort：O(k)O(k) kk là phạm vi của data 　Merge sort：O(n)O(n) 　Quick sort：O(logn)O(logn) 　CountingSort thì phạm vi data thay đổi so với ban đầu, nên cần có 1 lượng Memory có thể chứa được phạm vi đó.

△Tốc độ

Về tốc độ thì cũng phụ thuộc nhiều vào Machine spec. 　Ví dụ, CountingSort thì nhanh nhất 1 cách áp đảo 　nhưng lại cần có 1 lượng memory không phải "dạng tầm thường" tùy vào phạm vi giá trị. Ngoài ra, đối với Merge sort và Quick sort 　Thì merge sort nhanh với data nhỏ 　Quick sort được đánh giá nhanh nhất với data lớn.

Tóm lại, cái gì là mạnh nhất?

Nhiều người nói rằng Quick sort là nhanh nhất. Trường hợp có giới hạn sẵn phạm vi giá trị 1 cách đơn giản như Hiragana: CountingSort Đối với thứ có lượng data lớn đáng kể ：QuickSort Đối với những thứ dung lượng không lớn lắm：MargeSort