Selection Sort Algorithm
Step-by-Step Algorithm
1. Step 1:
• Start with the first element in the array (i = 0).
• Find the smallest element in the array from index i to n − 1.
• Swap the smallest element with the element at index i.
2. Step 2:
• Move to the next element (i = 1).
• Find the smallest element in the remaining unsorted part (from index
i to n − 1).
• Swap the smallest element with the element at index i.
3. Step 3:
• Continue to the next position (i = 2).
• Find the smallest element in the remaining unsorted part.
• Swap it with the element at index i.
4. Step 4:
• Repeat this process for each position in the array until only one
element remains in the unsorted part.
• No further swaps are needed when the last element is reached because
the array is now sorted.
5. Step 5:
• The array is completely sorted.
• End the algorithm.
1
C Code for Selection Sort
1 // C program to implement Selection Sort
2 # include < stdio .h >
3
4 void selectionSort ( int arr [] , int n ) {
5 int i , j , minIndex , temp ;
6
7 // Move through each element in the array
8 for ( i = 0; i < n -1; i ++) {
9 // Find the smallest element in the remaining
unsorted array
10 minIndex = i ;
11 for ( j = i +1; j < n ; j ++) {
12 if ( arr [ j ] < arr [ minIndex ]) {
13 minIndex = j ;
14 }
15 }
16
17 // Swap the smallest element with the first element
of the unsorted part
18 temp = arr [ minIndex ];
19 arr [ minIndex ] = arr [ i ];
20 arr [ i ] = temp ;
21 }
22 }
23
24 void printArray ( int arr [] , int n ) {
25 for ( int i = 0; i < n ; i ++) {
26 printf ( " % d " , arr [ i ]) ;
27 }
28 printf ( " \ n " ) ;
29 }
30
31 int main () {
32 int arr [] = {64 , 25 , 12 , 22 , 11};
33 int n = sizeof ( arr ) / sizeof ( arr [0]) ;
34
35 printf ( " Original array :\ n " ) ;
36 printArray ( arr , n ) ;
37
38 selectionSort ( arr , n ) ;
39
40 printf ( " Sorted array :\ n " ) ;
41 printArray ( arr , n ) ;
42
43 return 0;
44 }
2
Explanation of Code
1. The program defines the selectionSort function, which takes an array
and its size as input.
2. A nested loop is used:
• The outer loop iterates over each element in the array.
• The inner loop finds the index of the smallest element in the unsorted
part of the array.
3. After finding the smallest element, it is swapped with the current element
being processed.
4. The printArray function is used to display the array before and after
sorting.
3
Real-World Example: Organizing Books on a Shelf
Imagine you have a pile of books with different heights and you want to arrange
them on a shelf in increasing order of height:
1. Start by finding the shortest book in the pile and place it at the first
position.
2. Look at the remaining pile and find the next shortest book. Place it in
the second position.
3. Repeat this process for the entire pile of books until all books are arranged
from shortest to tallest.
This is similar to how the Selection Sort algorithm works, where you repeat-
edly find the smallest element in the unsorted part and place it in its correct
position.
4
Diagrammatic Representation of Selection Sort
• Initial Array: [64, 25, 12, 22, 11]
• Pass 1 (i = 0):
– Find the smallest element in the entire array: 11.
– Swap 11 with the first element (64).
– Result: [11, 25, 12, 22, 64]
• Pass 2 (i = 1):
– Find the smallest element in the unsorted part: 12 (from [25, 12, 22, 64]).
– Swap 12 with the second element (25).
– Result: [11, 12, 25, 22, 64]
• Pass 3 (i = 2):
– Find the smallest element in the unsorted part: 22 (from [25, 22, 64]).
– Swap 22 with the third element (25).
– Result: [11, 12, 22, 25, 64]
• Pass 4 (i = 3):
– No swap needed, as the remaining elements are already in order.
– Result: [11, 12, 22, 25, 64]
• Final Sorted Array: [11, 12, 22, 25, 64]
5
Why i < n-1 and Not i ≤ n − 1?
• The loop runs from i = 0 to i < n-1 because the last element of the
array will already be sorted by the time the loop reaches it.
• In the selectionSort algorithm, we only need to process n − 1 elements
since the largest element will naturally occupy the last position after the
previous iterations.