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


January 31, 2023, Learn eTutorial
1279

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++

Selection sort is one of the sorting methods in C++ which helps to sort the array elements. It works by comparing the elements and finding the smallest element and swap it with the first position of the array. Now the first element is sorted and in the second pass, it will start from the second position and check each element to find the smallest element and swap that element with the second position element. It go on in many iterations until the array is completely sorted.

We can learn the selection sort easily by an example, 

  • 10, 16, 8, 15
  • In the first pass, the sorting algorithm starts from position one which is 12 and it checks all the elements of the array and finds the smallest element 8, and swaps it with the first element 12.
  • 8, 16,10, 15
  • In the second pass, the algorithm skips the first position and starts from the second position which is 16, and checks all other elements of the array for the smallest element which is now 10, and swaps 10 and 16.
  • 8, 10, 16,15
  • In the third pass, the algorithm checks the third element and checks for the smallest element in the array of remaining elements and swaps it with the third position, here 16 and 15 get swapped.
  • 8, 10, 15, 16
  • Now the array is completely sorted.

C++ program to implement selection sort

The program gives a message for the user to give 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 comparing 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 evaluates 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 the 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