# Selection Sort

## Contents

# 14.2. Selection Sort#

Selection sort is a simple sorting algorithm that finds the minimum or maximum element from the unsorted part of the list and swap it with the last element of the unsorted part. It is much less efficient on large lists than more advanced algorithms such as quicksort.

## 14.2.1. Algorithm#

For sorting in ascending order, the general idea of selection sort is to iterate through the array, and find the maximum element from the unsorted part of the list, which is initially the entire array, then swap it with the last element of the unsorted array. This makes the last element of the array sorted, and the remaining elements of the array unsorted. The process repeats till the entire array gets sorted.

For example, if only the last 3 elements of the array are sorted holding the maximum 3 numbers of the array, we will look at the maximum number in the remaining of the array excluding the last 3 elements. This element will be swapped with the last element from the unsorted array, excluding the last 3 elements. This makes the last 4 elements of the array sorted, and holding the maximum 4 numbers of the entire array.

Given the following example array named `int A[] = {9, 5, 18, 8, 5, 2};`

Selection sort works as follows:

Find the maximum element from the unsorted part of the array, which is initially the entire array. Then swap it with the last element.

After the first iteration, the last element of the array — as a sub-array — is sorted, and is holding the maximum element of the array.

Find the maximum element from the unsorted part of the array, which is the remaining of the array excluding the last element. Then swap it with the last element of the unsorted array.

`top`

is holding the index of the last element of the unsorted array.After the second iteration, the last two elements of the array — as a sub-array — are sorted, holding the maximum two elements of the array.

If the largest element is also the last element in the unsorted sub-array, we swap the element with itself. After that, the last three elements of the array — as a sub-array — are sorted, holding the maximum three elements of the array.

The process repeats till the entire array gets sorted.

## 14.2.2. Pseudocode#

We write pseudocode for selection sort as follows:

Set

`top`

to`n - 1`

, where`n`

is the length of the array.Iterate elements from index

`0`

to`top`

to find the largest element and place its index in`indexOfLargest`

Swap element at index

`top`

with element at index`indexOfLargest`

. This places the largest element at the end of the unsorted sub-array.Decrement

`top`

by`1`

.Repeat steps 2 to 4 till

`top`

is`0`

.

## 14.2.3. Implementation#

We implement selection sort as follows. In lines \(8\) to \(12\), we implement the swap function that swaps two `int`

values. We implemented the swap function before in Section 6.3. Download `selection-sort.c`

if you want to play with the code.

**Code**

```
1void printArray(int list[], int listLength) {
2 for (int i = 0; i < listLength; i++) {
3 printf("%d ", list[i]);
4 }
5 printf("\n");
6}
7
8void swap(int *x, int *y) {
9 int temp = *x;
10 *x = *y;
11 *y = temp;
12}
13
14void selectionSort(int list[], int n) {
15 for (int top = n - 1; top > 0; top--) {
16 // find largest from 0 to top
17 int indexOfLargest = 0;
18 for (int i = 1; i <= top; i++) {
19 if (list[i] > list[indexOfLargest]) {
20 indexOfLargest = i;
21 }
22 }
23 // put largest at top
24 swap(&list[indexOfLargest], &list[top]);
25 printf("After iteration %d: ", n - top);
26 printArray(list, 6);
27 }
28}
29
30int main(void) {
31 int list[] = {9, 5, 18, 8, 5, 2};
32 selectionSort(list, 6);
33 printArray(list, 6);
34}
```

**Output**

After iteration 1: 9 5 2 8 5 18 After iteration 2: 5 5 2 8 9 18 After iteration 3: 5 5 2 8 9 18 After iteration 4: 2 5 5 8 9 18 After iteration 5: 2 5 5 8 9 18 2 5 5 8 9 18