# Selection Sort

## Overview of Selection sort

Selection sort is a very simple sorting algorithm. It is similar to insertion sort and is inefficient for sorting large arrays.

In this chapter, we’ll review the selection sort algorithm and analyze its performance.

## Selection Sort Algorithm

Selection sort works by finding the smallest element in the array and swapping it with the first element of the array. Then find the smallest element in the remaining part of the array, and swap it with the second element of the array

```
for i in (0 to a.end)
min = index of smallest element of a[i to a.end]
swap(a[i], a[min])
```

Selection sort proceeds in stages. At the start of each stage, the array will be partitioned into a two disjoint regions. The upper region will contain those elements already in sorted order. The lower region will contain those elements that are not necessarily sorted. (They might be by chance.) The upper region will also have the property that every element in it is greater than or equal to any element in the unsorted region.

The action performed during each stage is therefore to and the largest key in the unsorted region and put it into the lowest position of the sorted region. Since it was in the unsorted region, it is less than or equal to every key in the sorted region. By placing it in the lowest position in the sorted region it preserves the ordering of that region. In addition, the size of the unsorted region is reduced by one. This implies that after n steps, where n is the number of elements, the unsorted region will be size zero, or that the array has been sorted.

The following function defines selection sort of an array `A`

of size `n`

. T is the underlying element type. The
`index_of_maximum_key()`

function performs a linear search of its array argument from index 0 to index
`last`

for the key with maximum value and returns its index. The `swap()`

function swaps its arguments.

```
void SelectionSort(T A[], int n) {
// Precondition: A[0..n-1] contains the data to be sorted
// Postcondition: A[0..n-1] is sorted in ascending order.
int largest; // index of largest item in unsorted part of array
int last; // index of last item in unsorted part of array
for (int last = n - 1; last >= 1; last--) {
// Invariant: A[last+1...n-1] is already sorted and
// if j <= last and k > last, A[j] <= A[k]
largest = index_of_maximum_key(A, last);
swap(A[largest], A[last]);
}
}
```

## Analysis of Selection sort (Time and Space Complexity)

In short,

- Worst-case performance:
**\(O\left(N^{2}\right)\)** - Worst-case space complexity:
**O(1)**(in-place)

Let’s review the C++ function from the previous section. During each iteration of the loop, `index_of_maximum_key()`

is called once with an array of size `last+1`

. To find the maximum element in an array of size *n*, *n-1* comparisons must be performed. (Why not *n*?) Therefore, the function performs `last`

comparisons when its second argument is `last`

. Since `last`

runs from *n-1* down to *1*, the total number of key comparisons is the sum of the numbers *1, 2, 3,…, n-1*, which is *n(n − 1)/2*. Notice that the total number of key comparisons performed by selection sort is the same in all cases - it does not depend on the data.

The `swap()`

function performs a constant number of data exchanges. To swap two elements requires three
assignments. It is called once in each iteration of the loop. Since there are *(n − 1)* iterations, there are
*3(n − 1)* data exchanges caused by `swap()`

. As there is no other data movement in the algorithm, the total
number of data exchanges is *3(n − 1)*. This too is independent of the original state of the data.

Expressing these results in order notation, we can see that selection sort has a worst case, average case, and best case running time that is \(O\left(N^{2}\right)\).

## Common Selection Sort Questions

##### 1. Is selection sort in-place sorting algorithm?

Yes, selection sort is an in-place sorting algorithm. It doesn’t use extra space and sorts the array in place.

##### 2. Is selection sort adaptive?

No. In adaptive algorithms, the complexity (running time, performance) changes based on whether or not the input array is sorted. They perform better when the input is sorted. Selection sort is **not** adaptive because the initial order of the array has no impact on the number of comparisons.

##### 3. Is selection sort stable?

No. Stable means that if two elements have the same value, they remain in the same position. Selection sort is **not** stable.

##### 4. Is selection sort divide and conquer?

No. A divide and conquer algorithm continuously breaks down a bigger problem into sub-problems, until they become simple enough to be solved directly. Selection sort doesn’t do that and hence it is not a divide and conquer algorithm.

## Code Examples

### Selection sort in Java

```
private static void selectionSort(int a[]) {
for (int i = 0; i < a.length-1; i++) {
/* assume the min is the first element */
int jMin = i;
/* test against elements after i to find the smallest */
for (int j = i+1; j < a.length; j++) {
/* if this element is less, then it is the new minimum */
if (a[j] < a[jMin]) {
jMin = j;
}
}
if (jMin != i) {
swap(a[i], a[jMin]);
}
}
}
```

See this for a complete example and explanation of **Selection Sort using Recursion**.