COMP1927 - Selection Sort

Selection Sort has a very simple algorithm; find the smallest and swap it with the first unsorted element. Rinse and repeat.

## Type

Stable (although really it can be unstable, if you set it to smallest if it's less than or equal to
In-Place

## Complexity

Selection sort has a best, worst and average complexity of O(n2), as it has no early entry and always traverses the list (of n elements) n times.

However it only performs n swaps, one for each element.

## Code

```void selectionSort (int array[], int length) {

// While the list isn't sorted
int i;
int unsortedStart;
int smallest;
int smallestCell;
int temp;

for (unsortedStart = 0; unsortedStart < length; unsortedStart++) {

// Traverse the list to find the smallest item
smallest = array[unsortedStart];
smallestCell = unsortedStart;
for (i = unsortedStart; i < length; i++) {
if (array[i] < smallest) {
smallest = array[i];
smallestCell = i;
}
}

// Swap the smallest with the first item of the unsorted list
temp = array[smallestCell];
array[smallestCell] = array[unsortedStart];
array[unsortedStart] = temp;

}

}
```
page revision: 7, last edited: 20 Aug 2011 11:20