Sorting Techniques
1. Selection Sort:
Idea: The inner loop selects the minimum element in the unsorted array and places the elements in increasing order.
Time complexity: O(N 2 )
#include <iostream>
using namespace std;
int main() {
int n;
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]<<" ";
}
return 0;
}
2. Bubble Sort:
Idea: if arr[i] > arr[i+1] swap them. To place the element in their respective position, we have to do the following operation N-1 times.
Time Complexity: O(N 2 )
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int counter=1;
while(counter<n){
for(int i=0;i<n-counter;i++){
if(arr[i]>arr[i+1]){
int temp=arr[i+1];
arr[i+1]=arr[i];
arr[i]=temp;
}
}counter++;
}
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
3. Insertion Sort:
Idea: Take an element from the unsorted array, place it in its corresponding position in the sorted part, and shift the elements accordingly.
Time Complexity: O(N 2 )
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=1;i<n;i++){
int cu=arr[i];
int j=i-1;
while(j>=0 && arr[j]>cu)
{
arr[j+1]=arr[j];
j--;
}arr[j+1]=cu;
}
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
Instagram 👇
👍
ReplyDelete