Đổi chỗ trực tiếp (Interchange sọt):

Xuất phát từ đầu dãy, lần lượt tìm những phần tử còn lại ko thoả thứ tự với phần tử đang xét. Với mỗi phần tử tìm được mà ko thoả thứ tự. Thực hiện hoán vị để thoả thứ tự. Lặp lại tương tự với các phần tử tiếp theo.

[codes=c]void InterchangeSort(int a[], int N)
{
    for (int i = 0; i < N – 1; i++)
        for (int j = i + 1; j < N; j++)
            if (a[j] < a[i])
                Swap(a[j],a[i]);
}[/codes]

Sắp xếp chọn (Selection sọt):

Chọn phần tử có khóa nhỏ nhất trong N phần tử ban đầu. Đổi chỗ phần tử vừa chọn với phần tử đầu dãy. Xem dãy hiện hành chỉ còn N-1 phần tử (không xét phần tử đầu). Bắt đầu từ vị trí thứ hai và lặp quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn một phần tử.

[codes=c]void SelectionSort(int a[], int n)
{
  int min;  // lưu chỉ số phần tử nhỏ nhất
  for(int i = 0; i < n-1; i++)  // duyệt qua n-1 phần tử
  {  
    min = i;
    for(int j = i+1; j < n; j++)
      if (a[j] < a[min])
        min = j;
    Swap(a[min], a[i]);  //hoán vị a[i] và phần tử nhỏ nhất
  }
}[/codes]

Sắp xếp nổi bọt (Bubble sọt):

Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn về đầu. Sau đó ở bước tiếp theo không xét phần tử đó nữa.  Do vậy lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào được xét.
[codes=c]
void BubbleSort(int a[], int n)
{
  int i, j;
  for(i =0; i < n-1; i++)
    for(j=n-1; j >i; j–) //đổi chỗ cặp phân tử đứng sai
      if (a[j] < a[j-1])
        Swap(a[j], a[j-1]);
}[/codes]

Sắp xếp nhanh (Quick sọt):

Thuật toán do Hoare đề xuất và tốc độ trung bình nhanh hơn thuật toán khác.

[codes=c]void QuickSort(int a[], int left, int right) {
  int  i, j, x;
  x = a[(left+right)/2];    // chọn phần tử giữa làm mốc
  i = left,  j = right;
  do {
    while (a[i] < x) i++;  // lặp đến khi a[i] >= x
    while (a[j] > x) j–;  // lặp đến khi a[j] <= x
    if ( i <= j) {  
            Swap(a[i], a[j]);
            i++;    // qua phần tử kế tiếp
            j–;    // qua phần tử đứng trước
    }
  } while (i<j);
         if (left < j)      // ph đoạn bên trái
    QuickSort(a, left, j);
         if (right > i)      // ph đoạn bên phải
    QuickSort(a, i, right);
}[/codes]

Sắp xếp chèn (Insertion sọt):

[codes=c]void InsertionSort(int a[], int n){
  int pos, x;      //x lưu phần tử a[i]
  for(int i=1; i < n; i++)
    {
     x = a[i];  pos = i-1;  //xét từ vị trí i trở về trước
     while ((pos ≥ 0) && (a[pos] > x))  //kết hợp dời chỗ các p. tử đứng sau x trong dãy mới
       {
              a[pos+1] = a[pos];
              pos–;  
       }
       a[pos+1] = x;  //chèn x vào dãy mới  
    }
}[/codes]

Shell sọt:

Thuật toán Insertion sort có hạn chế là luôn chèn 1 phần tử vào đầu dãy!
Shell Sort cải tiến bằng cách chia làm nhiều dãy con và thực hiện pp chèn trên từng dãy con

[codes=c]void ShellSort(int a[], int n, int h[], int k)
{
  int step, i, pos, x, len;
  for(step = 0; step < k; step++) {   // duyệt qua từng bước nhảy
    len = h[step];      // chiều dài của bước nhảy
    for(i = len; i < n; i++) {  // duyệt các dãy con
      x = a[i];  // llưu phần tử cuối để tìm vị trí thích hợp trong dãy con
      pos = i – len;  // a[j] đứng trước a[i] trong cùng dãy con
      while ((x < a[pos]) && (pos = 0))
      {
        a[pos+len] = a[pos];    // dời về sau theo dãy con
        pos = pos – len;    // qua phần tử trước trong dãy con
      }
    a[pos+len] = x;  // đưa x vào vị trí thích hợp trong dãy con
    }// end for i
}// end for step
[/codes]

Radix sọt:

Không quan tâm đến việc so sánh giá trị các phần tử. Bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử. Còn gọi là phương pháp phân lô.

GT RadixSort thực hiện như sau:
Xem mỗi phần tử a[i] trong dãy a[1]…a[n] là một số nguyên có tối đa m chữ số
Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm…
Tại mỗi bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0  9.
Sau khi phân loại xong ở hàng thứ m cao nhất, ta sẽ thu được danh sách các phần tử được sắp.

[codes=c]void RadixSort(long a[], int n){
  int i, j, d, digit, num;
  int h = 10;    // biến để lấy các con số, bắt đầu từ hàng đơn vị
  long B[10][MAX];  //mảng hai chiều chứa các phần tử phân lô
  int  Len[10];    // kích thước của từng mảng B[i]

  for(d = 0; d < MAXDIGIT; d++)  // xét lần lượt hàng
  {
    for( i = 0; i < 10; i++) // khởi tạo kích thước các dãy B[i] là 0
      Len[i] = 0;

    for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng
    {
      digit = (a[i] % h) / (h / 10);// lấy chữ số theo hàng h
      B[digit][Len[digit]++] = a[i];  
    }

    num = 0;  // chỉ số bắt đầu cho mảng a[]  
    for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9]
           for(j =0; j < Len[i]; j++)
            a[num++] = B[i][j];
    h *= 10;  // qua hàng kế tiếp.

        }  
} //end RadixSort[/codes]

Hàm Swap:

[codes=c]void Swap(int &a, int &b)        
{  
    int temp;  
    temp =a;  
    a=b;  
    b=temp;  
}  [/codes]

Last modified on March 31st, 2021 at 12:57 am

10cth1 C