-
Notifications
You must be signed in to change notification settings - Fork 0
/
insertion_sort.cpp
45 lines (40 loc) · 1.09 KB
/
insertion_sort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
Best-case time complexity O(n)
Average-case time complexity O(n^2)
worst-case time complexity O(n^2)
space complexity O(1)
it is inplace and stable sorting algorithm
*/
/* hint :-
have two parts :- sorted and unsorted
sorted part has one element the first one and unsorted part have rest of the elements.
select each element of the unsorted part and save that value in a vairable(make a hole) then
start compairing with elements of the sorted part and shift sorted element accordingly
*/
#include <iostream>
using namespace std;
int main(){
cout<<"enter the size of array?"<<endl;
int n,i,j,k;
cin>>n;
cout<<"enter the elements of the array......."<<endl;
int arr[n];
for(i=0;i<n;++i){
cin>>arr[i];
}
int value,hole;
for(i=1;i<n;++i){
value=arr[i];
hole=i;
while(hole>0 && arr[hole-1] > arr[hole]){
arr[hole]=arr[hole-1];
hole--;
}
arr[hole]=value;
}
cout<<"sorted array: ";
for(i=0;i<n;++i){
cout<<arr[i]<<" ";
}cout<<endl;
return 0;
}