C++ Program to implement selection sort in C++

Here we are going to implement selection sort in C++. This program is to sort an array in ascending order using the selection sort technique.

Selection sort in C++

In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted into its appropriate position in the array. It is also the simplest algorithm. It is an in-place comparison sorting algorithm. In this algorithm, the array is divided into two parts, the first is the sorted part, and another one is the unsorted part. Initially, the sorted part of the array is empty, and the unsorted part is the given array. The sorted part is placed on the left, while the unsorted part is placed on the right.
In selection sort, the first smallest element is selected from the unsorted array and placed at the first position. After that second smallest element is selected and placed in the second position. The process continues until the array is entirely sorted.
Now, let's see the working of the Selection sort Algorithm.
To understand the working of the Selection sort algorithm, let's take an unsorted array. It will be easier to understand the Selection sort via an example.
Let the elements of array are 
12, 29, 25, 8, 32, 17, 40
Now, for the first position in the sorted array, the entire array is to be scanned sequentially.
At present, 12 is stored at the first position, after searching the entire array, it is found that 8 is the smallest value.
12, 29, 25, 8, 32, 17, 40 So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted array.
For the second position, where 29 is stored presently, we again sequentially scan the rest of the items of the unsorted array. After scanning, we find that 12 is the second lowest element in the array that should be appeared at the second position.
8, 29, 25, 12, 32, 17, 40

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the sorted array. So, after two iterations, the two smallest values are placed at the beginning in a sorted way.
8, 12, 25, 29, 32, 17, 40 
The same process is applied to the rest of the array elements. Now, we are showing a pictorial representation of the entire sorting process.
8, 12, 25, 29, 32, 17, 40
8, 12, 25, 29, 32, 17, 40
8, 12, 17, 29, 32, 25, 40
8, 12, 17, 25, 32, 29, 40
8, 12, 17, 25, 29, 32, 40
8, 12, 17, 25, 29, 32, 40
Now, the array is completely sorted.

C++ program to implement selection sort

The program asks the user to enter the size of the array. The entered number will be stored in the variable tot. Then the user is asked to enter the elements. The elements are stored in the array arr[50]. Let us have an explanation with an example. If the user enters 5 as size, then tot=5; And when the user enters the 5 elements, it gets stored in the array in this way
Arr[0] = 10
Arr[1] = 1
Arr[4] = 2
Now the execution of the for loop to perform selection sort get started.


for(i=0; i<(tot-1); i++)

    {

        chk=0;

        small = arr[i];

 

i is initialized to 0; the condition i<(tot-1) evaluates to be true.(ex: i<4), the program flow goes inside the loop.
Inside the loop, initialize the variable chk = 0; The element in the array arr[i] is initialized to small. We are assuming the first element (ex: 10) as the smallest element in the array and compare it with elements at rest indexes.
Every time we've supposed the element at the current index as the smallest element, then compared it with the rest of the element, if it is found greater than any element, then we've initialized a new element as the smallest one.
Now the inner for loop begins, j is initialized to i+1, and the condition jevaluates to be true, and the program flow goes inside the loop.



for(j=(i+1); jarr[j])

            {

                small = arr[j];

                chk++;

                index = j;

            }

        }


Inside this loop, the condition small>arr[j] (if)  evaluates to be true, therefore program flow goes inside the if's body. And arr[j]  gets initialized to small. The value of chk gets incremented. So chk=1. And finally, j gets initialized to index. Now the value of j gets incremented. Again the condition evaluates true and program flow goes inside the loop. This process continues until the condition of this for loop evaluates to be false. After exiting from this loop, the condition chk!=0 (if)  evaluates to be true, therefore arr[i] or arr[0]  gets initialized to temp, small  gets initialized to arr[i] or arr[0], and finally temp  gets initialized to arr[index]. Now the program flow goes to the update part of the outer for loop and increments the value of i. So i=1. And the condition again gets evaluated
That is the condition i<(tot-1)  evaluates to be true again, therefore program flow again goes inside the loop. This process continues until the condition evaluates to be false. In this way, selection sort gets implemented.

Algorithm

Step 1: Call the header file iostream.

Step 2: Use the namespace std.

Step 3: Open the integer type main function; int main().

Step 4: Declare integer type variables tot, arr[50], I, j, small, chk, index;

Step 5: Ask the user to enter the size of the array

Step 6: Get the number into the variable tot;

Step 7: Ask the user to enter the numbers;

Step 8: Get the numbers into the array arr[50];

Step 9: for i =1 to tot-1

Step 10: set chk = 0;

Step 11: set small = arr[i];

Step 12: for j = i+1 to tot-1 repeat:
          If (small>arr[j])
          Set small = arr[j]
          Increment chk;
          Set index = j

Step 13: swap arr[i] with arr[index];

Step 14: print the sorted array;

Step 15: Exit;

 

C++ Source Code

                                          #include<iostream>
using namespace std;
int main()
{
    int tot, arr[50], i, j, temp, small, chk, index;
    cout<<"Enter the Size of Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    for(i=0; i<(tot-1); i++)
    {
        chk=0;
        small = arr[i];
        for(j=(i+1); j<tot; j++)
        {
            if(small>arr[j])
            {
                small = arr[j];
                chk++;
                index = j;
            }
        }
        if(chk!=0)
        {
            temp = arr[i];
            arr[i] = small;
            arr[index] = temp;
        }
    }
    cout<<"\nSorted Array is:\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}
                                      

OUTPUT

Enter the Size of Array: 6
Enter 6 Array Elements: 10
2
36
5
45
36
Sorted Array is:
2 5 10 36 36 45