c code for insertion sort.
write a c code for insertion sort.
WAP to sort an array of n integers in a descending order using insertion sort.
Content
Complexity Analysis for Insertion Sort
We examine Algorithms broadly on two prime factors, i.e.,
-
Running Time : Running Time of an algorithm is execution time of each line of algorithm
As stated, Running Time for any algorithm depends on the number of operations executed. We could see in the psuedocode that there are precisely 7 operations under this algorithm. So, our task is to find the Cost or Time Complexity of each and trivially sum of these will be the Total Time Complexity of our Algorithm.
We assume Cost of each i operation as C i where i ∈ {1,2,3,4,5,6,8} and compute the number of times these are executed. Therefore the Total Cost for one such operation would be the product of Cost of one operation and the number of times it is executed.
We could list them as below:
| COST OF LINE | NO. OF TIMES IT IS RUN |
|---|---|
| C1 | n |
| C2 | n - 1 |
| C3 | n - 1 |
| C4 | Σ n - 1j = 1(tj) |
| C5 | Σ n - 1j = 1 (tj - 1) |
| C6 | Σ n - 1j = 1(tj - 1) |
| C8 | n - 1 |
Then Total Running Time of Insertion sort (T(n)) = C1 * n + ( C2 + C3 ) * ( n - 1 ) + C4 * Σ n - 1j = 1( t j ) + ( C5 + C6 ) * Σ n - 1j = 1( t j ) + C8 * ( n - 1 )
-
Memory usage : Memory required to execute the Algorithm.
As we could note throughout the article, we didn't require any extra space. We are only re-arranging the input array to achieve the desired output. Hence, we can claim that there is no need of any auxiliary memory to run this Algorithm. Although each of these operation will be added to the stack but not simultaneoulsy the Memory Complexity comes out to be O(1)
Best Case Analysis
In Best Case i.e., when the array is already sorted, tj = 1
Therefore,T( n ) = C1 * n + ( C2 + C3 ) * ( n - 1 ) + C4 * ( n - 1 ) + ( C5 + C6 ) * ( n - 2 ) + C8 * ( n - 1 )
which when further simplified has dominating factor of n and gives T(n) = C * ( n ) or O(n)
Worst Case Analysis
In Worst Case i.e., when the array is reversly sorted (in descending order), tj = j
Therefore,T( n ) = C1 * n + ( C2 + C3 ) * ( n - 1 ) + C4 * ( n - 1 ) ( n ) / 2 + ( C5 + C6 ) * ( ( n - 1 ) (n ) / 2 - 1) + C8 * ( n - 1 )
which when further simplified has dominating factor of n2 and gives T(n) = C * ( n 2) or O( n2 )
Average Case Analysis
Let's assume that tj = (j-1)/2 to calculate the average case
Therefore,T( n ) = C1 * n + ( C2 + C3 ) * ( n - 1 ) + C4/2 * ( n - 1 ) ( n ) / 2 + ( C5 + C6 )/2 * ( ( n - 1 ) (n ) / 2 - 1) + C8 * ( n - 1 )
which when further simplified has dominating factor of n2 and gives T(n) = C * ( n 2) or O( n2 )
Code
#include <stdio.h>
void printArray(int *A, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
}
void insertionSort(int *A, int n)
{
int key, j;
for (int i = 1; i <= n - 1; i++)
{
key = A[i];
j = i - 1;
while (j >= 0 && A[j] < key)
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = key;
}
}
int main()
{
int n = 6;
int A[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &A[i]);
}
printArray(A, n);
insertionSort(A, n);
printArray(A, n);
return 0;
}