Code:
void SelectionSort(int A[],int n) {
int min;
for(int i=0; i<n-1; i++) {
min = i;
for(int j=i+1; j<n; j++)
if(A[min]>A[j])
min = j;
if(min != i)
Swap(A[i],A[min]);
}
}
Trong hàm Selection Sort, có gọi thủ tục Swap ta dễ thấy rằng hàm Swap có 3lệnh gán nên thời gian thực hiện là O(1).
Trong Selection Sort lệnh gọi Swap nên chỉ tốn O(1), dòng for thứ 2 thực hiện n-i lần, mỗi lần thực hiện tốn O(1) nên tốn O (n-i) và đây cũng là độ phức tạp của hàm:
T(n) =∑_(i=1)^(n-1)▒(n-i) = (n(n-1))/2 = O(n^2)