### Selection Sort

##############################
####    selection sort    ####
##############################

similar to bubble sort, only slightly more inefficient in its best case time complexity.

(logic flow)
- iterate thru the whole input (N data), then find the smallest (or the biggest), then bring it to the top (or to the end).
- then do the same iteration again for the rest of the input (N-1).
- then repeat.

- an unstable sort.

######################################
####    computation complexity    ####
######################################

worst case:    O(N^2)
best case:     O(N^2)
average case:  O(N^2)

###
###  worst case
###

this is the number of loop versus iteration count in each loop.

the number of loop is N
iteration in each loop is N, N-1, N-2, N-3,,, 2,1       // last one is not needed obviously cos 1 item is already sorted

N + (N-1) + (N-2) + (N-3) + ... + 2 + 1 = N(N+1)/2      // quardratic, thus O(N^2) as we ignore constants

###
###  best case
###

unlike other sort algo, like bubble sort, regardless of how sorted already the input data is, we just have to follow the above logic to find the smallest(biggest) element. thus the best case (and subsequently the average case) is the same as the worst case in complexity:  O(N^2)

##################################
####     space complexity     ####
##################################

total:      O(N)
auxiliary:  O(1)    // 1 for a tmp var to retain the smallest(biggest) val

############################################
####    implementation example (C++)    ####
############################################

just using a simple sample array input.

---------------------------------------------  // select.cpp

#include <iostream>
using namespace std;

void selectSort(int*arr, int arrSize);
void printArr(int*arr, int arrSize);

int main()

int arr[] = {12,78,56,34,8,34,4,91,-17,66};
int arrSize = sizeof(arr)/sizeof(arr[0]);

printArr(arr,arrSize);      // 12 78 56 34 8 34 4 91 -17 66
selectSort(arr,arrSize);
printArr(arr,arrSize);      // -17 4 8 12 34 34 56 66 78 91

return 0;

void selectSort(int*arr, int arrSize)

int smallest;
for(int i = 0; i < arrSize ; i++)
{
smallest = i;
for(int j = i; j < arrSize ; j++)
{
if( arr[j] < arr[smallest] )
smallest = j;
}
if( arr[i] != arr[smallest] )  // skip swap if arr[i] == arr[smallest]
{                              // meaning the smallest one is already at the top of that iteration loop
arr[i] = arr[i] + arr[smallest];
arr[smallest] = arr[i] - arr[smallest];
arr[i] = arr[i] - arr[smallest];
}
}

void printArr(int* arr, int arrSize)

for(int i = 0; i < arrSize ; i++)
cout << arr[i] << " ";
cout << endl;

-------------------------------------------------

1. 2014-06-06 21:20:15 |
2. Category : algo
3. Page View: