In the following article we will discuss the sorting of arrays and elaborate the operations of selection sort with complete examples.
Sorting of Arrays:-
Sorting is the process or technique in which the elements stored in an array are properly arranged in a particular order. Sorting is a very widely used technique, it is essential for binary search.
The elements of an array could be stored in two types of order, which are described below:
1. Ascending order.
2. Descending order.
Ascending order:-
In this order the smallest element is assigned to the smallest index of array, the second smallest element is assigned to second smallest index of an array and so on. At the end the greatest element is assigned to the greatest index of an array.
Descending order:-
In this order the biggest element is assigned to the last index of array, the second biggest element is assigned to second last index of an array and so on. At the end the smallest element is assigned to the smallest index of an array.
Usually, two types of sorting techniques are used in C++ programming.
1. Selection sort.
2. Bubble sort.
3. QuickSort.
4. Merge Sort.
5. Insertion Sort.
Selection Sort:-
Selection sort is one of the widely uses technique to sort an arrays in C++ programming. Its principle is to find a value and put it to its proper place. Its method works in such a way to find the minimum value in an array and put it to the minimum index, then it find the other values in an ascending order and puts them in their proper positions excluding the previous values. But here we will only discuss selection sort with example, therefore if you wanted to read Bubble sort then visit my article Bubble sort in C++ with Examples.
Example of Selection Sort:-
#include<iostream.h>
#include<conio.h>
main()
{
int arr[5];
int mini,temp;
cout<<"Enter 5 numbers: "<<endl;
for(int i=0; i<5; i++)
{
cin>>arr[i];
}
cout<<"Orignal entered numbers: "<<endl;
for(int j=0; j<5; j++)
{
cout<<arr[j];
cout<<endl;
}
for(int r1=0;r1<4;r1++)
{
mini=r1;
for(int r2=r1+1; r2<5; r2++)
if(arr[r2]<arr[mini])
mini=r2;
if(mini !=r1)
{
temp=arr[r1];
arr[r1]=arr[mini];
arr[mini]=temp;
}
}
cout<<"Array sorted by selection sort is: "<<endl;
for(int q=0; q<5; q++)
{
cout<<arr[q];
cout<<endl;
}
getch();
}
Explanation:-
Now, I will describe this program with complete explanations and proper examples. Just consider the array entered by the user is:
Now nested loop will be used to perform sorting operation. The outer loop iterations will represent the number of passes and the inner loop will represents the number of iterations.
At start when the loop started, value of r1=0, which indicates the beginning of first pass.
In the first pass r1=0 and the inner loop came into action, in first pass inner loop will perform 4 iterations and check the following collection of statements.
for(int r1=0;r1<4;r1++)
{
mini=r1;
for(int r2=r1+1; r2<5; r2++)
if(arr[r2]<arr[mini])
mini=r2;
if(mini !=r1)
{
temp=arr[r1];
arr[r1]=arr[mini];
arr[mini]=temp;
}
}
First pass:
Iteration no. 1:
When first iteration starts the value of r1=0, which was assigned to a variable mini, the value of r2=1, Therefore values of mini and r2 will be compared which means 0s index and the 1st index of an array will be compared. As the above array show that the value of 1st index is greater than 0s index, due to which array will remains unchanged.
Iteration no.2:
When second iteration starts the value mini=0 and the value of r2=2, Therefore values of mini and r2 will be compared which means 0s index and the 2nd index of an array will be compared. As the above array show that the value of 2nd index is lesser than 0s index, due to which value of r2 will be assigned to variable mini.
Iteration no.3:
When 3rd iteration starts the value mini=2 and the value of r2=3, Therefore values of mini and r2 will be compared which means 2nd index and the 3rd index of an array will be compared. As the above array shows that the value of 3rd index is greater than 2nd index, due to which array remains unchanged.
Iteration no.4:
When 4th iteration starts the value mini=2 and the value of r2=4, Therefore values of mini and r2 will be compared which means 2nd index and the 4th index of an array will be compared. As the above array shows that the value of 4th index is lesser than 2nd index, due to value of r2 will be assigned to variable mini.
At the end of the pass the last condition is checked. That is, if the value of variable mini is not equal to variable r1 then interchange the values of index [mini] and index [r1]. Therefore the new array will looks like.
Second Pass:
Iteration no. 1:
When first iteration starts the value of r1=1, which was assigned to a variable mini, the value of r2=2, Therefore values of mini and r2 will be compared which means 1st index and the 2nd index of an array will be compared. As the above array shows that the value of 2nd index is smaller than 1st index, due to which value of r2 will be assigned to variable mini.
Iteration no.2:
When second iteration starts the value mini=2 and the value of r2=3, Therefore values of mini and r2 will be compared which means 2nd index and the 3rd index of an array will be compared. As the above array show that the value of 3rd index is greater than 2nd index, due to which array will remains unchanged.
Iteration no.3:
When third iteration starts the value mini=2 and the value of r2=4, Therefore values of mini and r2 will be compared which means 2nd index and the 4th index of an array will be compared. As the above array shows that the value of 4th index is greater than 2nd index, due to array remains unchanged.
At the end of the pass the last condition is checked. That is, if the value of variable mini is not equal to variable r1 then interchange the values of index [mini] and index [r1]. Therefore the new array will looks like.
Third Pass:
Iteration no. 1:
When first iteration starts the value of r1=2, which was assigned to a variable mini, the value of r2=3, Therefore values of mini and r2 will be compared which means 2nd index and the 3rd index of an array will be compared. As the above array shows that the value of 3rd index is greater than 2nd index, due to array remains unchanged.
Iteration 2:
When second iteration starts the value of mini=2 and the value of r2=4, Therefore values of mini and r2 will be compared which means 2nd index and the 4th index of an array will be compared. As the above array shows that the value of 4th index is smaller than 2nd index, due to which value of r2 will be assigned to variable mini.
At the end of the pass the last condition is checked. That is, if the value of variable mini is not equal to variable r1 then interchange the values of index [mini] and index [r1]. Therefore the new array will looks like.
Fourth Pass:
Iteration no. 1:
When first iteration starts the value of r1=3, which was assigned to a variable mini, the value of r2=4, Therefore values of mini and r2 will be compared which means 3rd index and the 4th index of an array will be compared. As the above array shows that the value of 4th index is smaller than 3rd index, due to value of r2 will be assigned to variable mini.
At the end of the pass the last condition is checked. That is, if the value of variable mini is not equal to variable r1 then interchange the values of index [mini] and index [r1]. Therefore the new array will looks like.
[yop_poll id=”7″] At last at this point the outer loop has been completed and we obtained the sorted array in ascending order with the help of Selection Sort.
If you like my work and wanted to read my other articles then visit my homepage.
@ 2014 HellGeeks.com
