Tổng hợp thuật toán sort cơ bản & Ví dụ trong ngôn ngữ C

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

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.

• 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("
");

}

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("
");
  printf("%d
",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;
      }
    }
  }

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ỉ.