Sorting Technique - Insertion Sort

Q.1) What is the process of insertion sort?

Insertion sort is an in-place sort in which sorted and unsorted data resides in the same array.

In this sorting technique, next element is selected and inserted in the sorted part of array (sorted sub-array). This process continues till all elements get inserted in sorted subarray.

Q.2) Sort Given integers using Insertion Sort : 32, 35, 12, 92, 86, 48, 37, 25

		0	1	2	3	4	5	6	7
	a[]	42	12	18	11	92	76	82	36
Pass 1		12	42	18	11	92	76	82	36
Pass 2		12	18	42	11	92	76	82	36
Pass 3		11	12	18	42	92	76	82	36
Pass 4		11	12	18	42	92	76	82	36
Pass 5		11	12	18	42	76	92	82	36
Pass 6		11	12	18	42	76	82	92	36
Pass 7		11	12	18	36	42	76	82	92

Q.3) Write a C function to implement Insertion Sort.

int main(int a[], int n)

{

int hold;

int pass, i;

for(pass=1; pass<n ; pass++)

{

hold = a[pass];

for (i=pass-1;i>=0 && hold < a[i]; i--)

a[i+1] = a[i];

a[i+1] = hold;

}

}

Q.4) What are the advantages of Insertion Sort?

Insertion Sort has two advantages :

i) It avoids one critical (expensive) operation - swapping or interchanges.

ii) It is an in-place sort method - it holds sorted as well as unsorted data in same array.

iii) It works efficiently (faster) for partially sorted or fully sorted data.

Q.5) What is the Time Complexity of Insertion Sort?

Insertion sort has three cases:

Best Case - Data is partially / fully sorted - O(n)

Average Case - Unsorted Data - O(n-square)

Worst Case - Oppositely Sorted Data - O(n-square)

Q.6) What is the Space Complexity of Insertion Sort?

Insertion Sort is an in-place sort technique which requires n memory locations and one extra location to hold element temporarily,

Hence, Space Complexity of Insertion Sort is O(n+1).

Q.7) Why Insertion Sort is better than Bubble and Quick Sort?

Insertion Sort does not require swapping of data , hence it is better than Bubble and Quick Sort.

Q.8) How Insertion Sort is more space efficient than Merge Sort?

Merge Sort has O(2n) Space Complexity which means it requires double space than Insertion Sort. Hence, Insertion Sort is more space efficient than Merge sort.

Want to read more?

Subscribe to questionbankos.com to keep reading this exclusive post.

Subscribe Now