BUBBLE SORT:
To check the graphical comparison between the time complexity of different techniques click
https://www.cuplex2b.com/2020/09/compare-and-plot-graph-of-cpu-time-for.html
Bubble sort is a basic sorting technique that works with repeatedly swapping adjacent elements. This algorithm works as follows. Lets take an array of size 6
a[6]={ 3,7,1,5,2,9}
Now, we will sort this array in increasing order using bubble sort. First, it compares each adjacent elements and swap if they are not in order. The process is repeated until the array get sorted. The pictorial representation is shown below:
we can see that in every step we get the relatively large number and the number of comparison decreases by one for every value of i=0 to i=n-1
We are performing n(n-1)/2 comparisons. So, the time complexity will be n^2 in general.
Code can be implemented as follows:
CODE:
#include <iostream>
using namespace std;
int main()
{
int a[6]={3,7,1,5,2,9};
int n=6;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
swap(a[j],a[j+1]); //swap is a built in function used to swap two numbers
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
OUTPUT:
1 2 3 5 7 9
TIME COMPLEXITY AND PERFORMANCE:
1. Time complexity for all cases is O(n^2).
2. Space complexity is O(1).
3. The technique is unstable.
INSERTION SORT:
This is one of the efficient sorting technique as compared to bubble sort and selection sort. In this technique, in every step, we compare an element with it's previous element. It is a greedy method of sorting.
Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and start with one card at a time. We pick up one card at a time and place it in the correct position in the left hand. To find out the correct position, we compare it with all the previously placed card on the left hand.
let's take an array
a[6]={ 5,8,1,9,10,3}
|
|
|
5 |
8 |
1 |
9 |
10 |
3 |
|
|
i=1 |
j=0 |
5 |
8 |
1 |
9 |
10 |
3 |
key=8 |
|
i=2 |
j=1 |
5 |
1 |
8 |
9 |
10 |
3 |
key=1 |
|
i=2 |
j=0 |
1 |
5 |
8 |
9 |
10 |
3 |
key=1 |
|
|
|
1 |
5 |
8 |
9 |
10 |
3 |
|
|
i=3 |
j=2 |
1 |
5 |
8 |
9 |
10 |
3 |
key=9 |
|
|
|
1 |
5 |
8 |
9 |
10 |
3 |
|
|
i=4 |
j=3 |
1 |
5 |
8 |
9 |
10 |
3 |
key=10 |
|
|
|
1 |
5 |
8 |
9 |
10 |
3 |
|
|
i=5 |
j=4 |
1 |
5 |
8 |
9 |
3 |
10 |
key=3 |
|
i=5 |
j=3 |
1 |
5 |
8 |
3 |
9 |
10 |
key=3 |
|
i=5 |
j=2 |
1 |
5 |
3 |
8 |
9 |
10 |
key=3 |
|
i=5 |
j=1 |
1 |
3 |
5 |
8 |
9 |
10 |
key=3 |
|
|
|
1 |
3 |
5 |
8 |
9 |
10 |
|
#include <iostream>
using namespace std;
int main()
{
int a[6]={5,8,1,9,10,3};
int n=6;
int i, key, j;
for (i = 1; i < n; i++)
{
key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key;
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
TIME COMPLEXITY AND PERFORMANCE:
QUICK SORT:
This is a divide and conquer sorting technique. In divide the array in small small partitions and sort the small parts and at last combine them to get the sorted final array.
First we take a pivot element. let us take the first element as pivot element and now we will traverse from left right to find out an element which is greater than the pivot element and will stop there. Again, we will traverse from right to left to find out an element lesser than or equal to the pivot element and will stop there. If we the traversal don't cross each other, then we will swap the two element that we found out. If we cross each other, then we will swap pivot element will the smaller element.
CODE:
#include <bits/stdc++.h>
using namespace std;
int partition (int a[], int left, int right)
{
int pivot = a[right];
int mn = (left - 1);
for (int i= left;i<right;i++)
{
if (a[i] < pivot) // check if there is a element which is greater than pivot
{
mn++;
swap(a[mn],a[i]);
}
}
swap(a[mn+ 1],a[right]); //since the loop gives the element greater than pivot
return (mn + 1);
}
void quickSort(int a[], int left, int right)
{
if (left< right)
{
int pp = partition(a, left, right);
quickSort(a, left, pp- 1);
quickSort(a, pp + 1,right);
}
}
int main()
{
int a[7] = {30,40,10,20,5,80,50};
int n=7;
quickSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
OUTPUT: 5 10 20 30 40 50 80
The code is explained step by step below with pictorial representation. Try to understand it taking the code as reference.
TIME COMPLEXITY AND PERFORMANCE:
1. Time complexity in best case is O(n log n).
2. Time complexity in worst case is O(n^2).
3. Time complexity in average case is O(n log n).
4. This sorting technique is not stable in general.
5. It is in place sorting technique as it doesn't take extra space to manipulate the code.
0 Comments