C++ Tutorials

# C++ Tutorials

Selection Sort in C++, the strategy is to find the smallest number in the array and exchange it with the value in the first position of array.

## Selection Sort in C++ With Function

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int selectionSort(int arr[], int n){
for(int i=0; i<n-1; i++){
//find out the smallest element index in the unsorted part
int minIndex=i;
for(int j=i; j<=n-1; j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
//Swap
swap(arr[i], arr[minIndex]);

}
}

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
selectionSort(arr,n);
for(int i=0; i<n; i++){
cout<<arr[i]<<",";
}

return 0 ;
}``````

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}

for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(arr[j]<arr[i]){
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
for(int i=0; i<n; i++){
cout<<arr[i]<<" ";
}
cout<<endl;

return 0 ;
}``````

Selection sort let’s say we’re given the following array and we want it sorted in increasing order how will we do this during each iteration we’ll select the smallest item from the unsorted partition of our array and move it to the sorted partition.

We’ll keep track of the current minimum and current item with red and blue arrows let’s get started we always set the current minimum to the first number in the unsorted partition in this case: two we progress the length of the array looking for a smaller number we find one at the end of the array and set it as our current minimum we swap one and two.

We now have one item in our sorted partition moving on, we set eight as our current minimum and scan the remainder of the array for a smaller number updating the current minimum as we progress at the end we find two and swap it with eight.

We’re ready for the next iteration this time three moves into our sorted partition let’s watch the rest of the algorithm play out pretty simple with each iteration you select the smallest item that hasn’t yet been sorted here’s the pseudocode for selection sort as you can tell from the code and the nested for loop selection sort has a time complexity of big O of n squared.

## Explain Selection sort in C++

Selection sort. Selection sort is a simple in-place comparison based sorting algorithm with the time complexity in best, average and worst case as O(n^2) and a space complexity of O(1). So now lets see how selection sort works.

Firstly we divide the array of elements that we need to sort into two sub-arrays is ‘sorted’ & ‘unsorted’ sub-arrays where initially we consider the whole array to be unsorted and element by element we sort the array, thus increasing the size of the sorted sub-array and eventually decreasing the size of the unsorted sub-array and for that we select the leftmost element in the unsorted sub-array and swap it with the smallest element in the unsorted sub-array. So let’s take an example to understand it.

Suppose this is the array given to us with 5 elements and initially we consider the whole array to be unsorted, next we select the leftmost element in the unsorted sub-array using the variable ‘i’, now in the next step we have to find the smallest element in the unsorted sub-array and swap it with the leftmost element.

Therefore to find the smallest element we will take a variable ‘small’ which will store the index of the smallest element and we will equate it to ‘i’, So initially both the variables ‘i’ and ‘small’ have the index 0 and we will use another variable ‘j’ to loop through the rest of the array in order to find the smallest element.

So at every step we will compare the value at ‘small’ and the value at ‘j’ and if the value at ‘j’ is smaller than the value at ‘small’ then we will store the index of that element in small, so by comparison 2 is smaller than 3, therefore by equating ‘small’ to ‘j’ we will store the index 1 in small and we will increment ‘j’ to move on to the next element and again we will compare the value at ‘j’ and the value at ‘small’, the value at ‘j’ is 5 which is greater than 2, therefore there would be no change in our variable small and we will move on to the next element, again comparing the values 1 is smaller than 2, so again we will equate ‘small’ to ‘j’ and ‘small’ now has the index 3, now again incrementing ‘j’ we reach the last element and comparing the values 4 is greater than 1, thus there would be no change in the value of small. Now as we have reached the end of the array so in the last step we will swap the values at ‘i’ and ‘small’ and therefore 1 will become a part of the sorted sub-array. Now again we will repeat the procedure and increment ‘i’ by 1 to select the leftmost element in the unsorted sub-array and we will again use the variable ‘small’ to store the index of the smallest element.

Now again looping through the unsorted sub-array one by one using the variable ‘j’ and we compare the value at ‘small’ and the value at ‘j’ and as 2 is smaller than 5 there would be no change in the value of small, moving forward to the next element now again 2 is smaller than 3 so we will not make any change in our variable small, now finally moving on to the last element we see that 4 is also greater than 2 therefore at the end our variable ‘small’ will contain the index 1 and as variable ‘i’ and variable ‘small’ are pointing to the same element this means that 2 is already at its sorted position. So in the next step 1 & 2 become part of the sorted sub-array.

So now incrementing ‘i’ by 1 to select the leftmost element in the unsorted sub-array and equating ‘small’ to ‘i’ both ‘i’ and ‘small’ will have the index 2 and using the variable ‘j’ to find the smallest element, we compare the values at ‘small’ and ‘j’ and as 3 is smaller than 5, we equate ‘small’ to ‘j’ and therefore ‘small’ now has the index 3 and moving on to the next element as 4 is greater than 3 there would be no change in the variable small, and now in the final step, we will swap the values at ‘i’ and the variable ‘small’ which would result in an array with 1,2,3 in the sorted sub-array.

Therefore again incrementing ‘i’ by 1 and equating ‘small’ to ‘i’, ‘i’ and ‘small’ will have the index 3, and using the variable ‘j’ we compare the values at ‘j’ and ‘small’ and as 4 is smaller than 5 we equate ‘small’ to ‘j’, therefore ‘small’ now has the index 4 and as there are no more elements in the array, we will perform the swap operation which would result in a fully sorted array. Therefore if we observe throughout the process we were using two loops using ‘i’ and ‘j’ where ‘i’ is the outer loop which runs from 0 to n-2, where n is the size of the array and ‘j’ is the inner loop which runs from i+1 to n-1.

So now let’s implement this using C++. We start our selectionSort function which takes as arguments an array ‘A’ and an integer ‘n’ which is the size of the array or the number of elements in the array, where small indicates the smallest element index, ‘i’ points to the leftmost element in the unsorted array and we use ‘j’ to loop through the unsorted array in-order to find the smallest element and then we start our outer loop which runs from 0 to n-2 as n-1 is the last element and when we are comparing the last and the second last element it would always result in a sorted array, so firstly we equate ‘small’ to ‘i’ and then we start our inner loop using the variable ‘j’ which runs from the index i+1 to n-1 which is till the last element and every step we compare the value at ‘j’ and the value at ‘small’ and if the value at ‘j’ is less than the value at ‘small’ then we store the index ‘j’ in ‘small’ and at the end of this loop we will have the index of smallest element in the variable ‘small’ and when the loop ends we will perform our swap operation using the temporary variable, we will store the value at index ‘i’ in ‘temp’ and store the value at ‘small’ at index ‘i’ , and finally we will store the value of the temporary variable at ‘small’ and we will repeat this process for every element from 0 to n-2.