Category: Data Structure

The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted.

Insertion sort is easily adaptable to singly linked list. In this method there is an array link of pointers, one for each of the original array elements. Thus the array can be thought of as a linear link list pointed to by an external pointer first initialized to 0. To insert the kth element the…

Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order O(N).

The worst case performance in insertion sort occurs when the elements of the input array are in descending order. In that case, the first pass requires one comparison, the second pass requires two comparisons, third pass three comparisons,….kth pass requires (k-1), and finally the last pass requires (n-1) comparisons. Therefore, total numbers of comparisons are:…

The Insertion Sort uses the swap operation since it is ordering numbers within a single list.

In every iteration an element is compared with all the elements before it. While comparing if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position up and inserts the desired element at the suitable position. This procedure is…

Ans: 3 9 46 16 28 14

It finds the lowest value from the collection and moves it to the left. This is repeated until the complete collection is sorted.

The bubble sort stops when it examines the entire array and finds that no “swaps” are needed. The bubble sort keeps track of the occurring swaps by the use of a flag.

Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.