[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp chọn.

Share:
Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước tiến hành như sau:

Bước 1: i=1

Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]

Bước 3: Hoán vị a[min] và a[i]

Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2

Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.


Thuật toán sắp xếp chọn - tinhoccoban.net
Ví dụ 1 thuật toán sắp xếp chọn 


Ví dụ 2: Cho dãy a = (12,2,8,5,1,6,4,15)

12 2 8 5 1 6 4 15

Bước 1: 1 2 8 5 12 6 4 15

Bước 2: 1 2 8 5 12 6 4 15

Bước 3: 1 2 4 5 12 6 8 15

Bước 4: 1 2 4 5 12 6 8 15

Bước 5: 1 2 4 5 6 12 8 15

Bước 6: 1 2 4 5 6 8 12 15

Bước 7: 1 2 4 5 6 8 12 15


C++ Code:
  1. #include <iostream.h>
  2. void selectionSort(int *array,int length)//selection sort function
  3. {
  4.     int i,j,min,minat;
  5.     for(i=0;i<(length-1);i++)
  6.     {
  7.         minat=i;
  8.         min=array[i];
  9.             for(j=i+1;j<(length);j++) //select the min of the rest of array
  10.         {
  11.           if(min>array[j])   //ascending order for descending reverse
  12.           {
  13.               minat=j;  //the position of the min element
  14.               min=array[j];
  15.           }
  16.         }
  17.         int temp=array[i] ;
  18.         array[i]=array[minat];  //swap
  19.         array[minat]=temp; 
  20.     }
  21. }
  22. void printElements(int *array,int length) //print array elements
  23. {
  24.     int i=0;
  25.     for(i=0;i<10;i++)
  26.        cout<<array[i]<<endl;
  27. }
  28. void main()
  29. {
  30.     int a[]={9,6,5,23,2,6,2,7,1,8};   // array to sort
  31.         selectionSort(a,10);                 //call to selection sort  
  32.     printElements(a,10);               // print elements
  33. }


5.Heap sort. (Sắp xếp vun đống)
6.Simple insertion sort.(Sắp xếp chèn)
7. Shell sort.
8.Merge sort. (Sắp xếp hòa nhập)