Selection sort

Tư tưởng :

Chọn vị trí nhỏ nhất trong dãy chưa sắp,ghi nhớ vị trí của nó trong dãy và sau

đó đổi chỗ nó với vị trí đầu dãy.Tiếp đó thu ngắn dãy đi 1 phần tử<trừ đi phần

tử đầu> và lặp lại qua trình trên cho đến khi dãy còn 1 phần tử.

Thủ tục :

void SelectionSort(int X[20],int n)

{

int i,j,k,tg;

for(i=1;i<n;i++)

{

j=i; //giả sử vị trí cần xếp có giá trị min

for(k=j+1;k<=n;k++)

if(X[k]<X[j]) j=k; // j là vị trí có giá trị min từ iàn

tg=X[i];

X[i]=X[j];

X[j]=tg;

}

}

//Độ phức tạp của thuật toán

Tổng số lần so sánh :

C(n)=(n-1)+...+(n-i-1)+...+1=n(n-1)/2-n=n(n-1)/2

Bậc của C(n) là O(n2)

+ Tổng số lần đổi chỗ : M(n)=n-1

Bậc của M(n) là O(n2)

 Vậy thời gian thực hiện giải thuật Selection Sort có độ phức tạp là O(n2)