September 14, 2023 in 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.
September 14, 2023 in Data Structure
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 linked list is traversed until the proper position for x[k] is found, or until the end of the list is reached. At that point x[k] can be inserted into the list by merely adjusting the pointers without shifting any elements in the array which reduces insertion time.
September 14, 2023 in Data Structure
Insertion sort as there is no movement of data if the list is already sorted and complexity is of the order O(N).
September 14, 2023 in Data Structure
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:
f(n) = 1+2+3+………+(n–k)+…..+(n-2)+(n-1) = n(n-1)/2 = O(n2)
September 14, 2023 in Data Structure
The Insertion Sort uses the swap operation since it is ordering numbers within a single list.
September 14, 2023 in Data Structure
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 repeated for all the elements in the list until we get the sorted elements.
September 14, 2023 in Data Structure
Ans: 3 9 46 16 28 14
September 14, 2023 in Data Structure
It finds the lowest value from the collection and moves it to the left. This is repeated until the complete collection is sorted.
September 14, 2023 in Data Structure
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.
September 14, 2023 in Data Structure
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.
