C++ Program for Selection Sorting Technique
Description
The Selection Sort maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.
In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.
That is: A pass to the array is made to locate the minimum value. Once, minimum value is found, it is placed in the first position of the array (at 0 index).Then another pass is made in the remaining elements to find the next smallest element, which is placed in the second position (at index no. 1) , and so on. Once the next to the last element is compared with the last element , all the elements have been sorted in ascending order.
Suppose an array A of N elements A[1], A[2], ......... , A[N] is to be sorted.
Pass-1 : Find the location of LOC of the smallest element in the list of N elements
A[1], A[2], ......., A[N], then interchange A[LOC] and A[1].
Pass-2 : Find the Location of LOC of the smallest in the sublist of n-1 elements.
A[2], A[3], ........ , A[n], and then interchange A[LOC] and A[2].
Then:
A[1], A[2] are sorted, A[1] < A[2].
Pass-3 : Find the Location of LOC of the smallest in the sublist of n-2 elements.
A[3], A[4], ........ , A[N], and then interchange A[LOC] and A[3].
A[1], A[2], A[3] are sorted
To illustrate selection Sort , consider an unsorted array of 5 elements,
25 15 30 9 99
Pass-1 Find the minimum element in arr[0...4] and place it at beginning (red colour denotes sorted array)
9 15 30 25 99
Pass-2 Find the minimum element in arr[1...4] and place it at beginning of arr[1...4]
9 15 30 25 99
Pass-3 Find the minimum element in arr[2...4] and place it at beginning of arr[2...4]
9 15 25 30 99
Pass-4 Find the minimum element in arr[3...4] and place it at beginning of arr[3...4]
9 15 25 30 99
Hence array is now sorted.
Time complexity of Insertion Sort is: O(N2).
Space complexity of Insertion Sort is: O(1).
Algorithm
Step 1 - Set MIN to location 0
Step 2 - Search the minimum element in the list
Step 3 - Swap with value at location MIN
Step 4 - Increment MIN to point to next element
Step 5 - Repeat until list is sorted
C++ Program for selection Sort
using namespace std;
void selection_sort(int a[], int n){
int min,loc,temp,i,j;
min=a[0];
for(i=0 ; i<n ; i++)
{
min=a[i];
loc=i;
for(j=i+1 ; j<n ; j++)
{
if( a[j]<min )
{
min=a[j];
loc=j;
}
}
if(loc != i)
{
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
}
}
int main() {
int n,i;
cout<<"How many elements?"<<"\n";
cin>>n;
int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
selection_sort(arr, n);
cout<<"Sorted array is:\n";
for(i=0 ; i<n ; i++){
cout<<arr[i]<<"\n";
}
return 0;
}
Output
How many Elements?
5
Enter elements of array
25
15
30
9
99
Elements of array after sorting are:
9
15
25
30
99
Comments