Describe the insertion sort algorithm for sorting a sequence of numbers in an ar

Question

Describe the insertion sort algorithm for sorting a sequence of numbers in an array.

Explanation / Answer

Dear, Insertion sort : It keeps making the left side of the array sorted until the whole array is sorted. It sorts the values seen far away and repeatedly inserts unseen values in the array into the left sorted array. void insertionSort(int numbers[], int array_size) { int i, j, index; for (i=1; i 0) && (numbers[j-1] > index)) { numbers[j] = numbers[j-1]; j = j - 1; } numbers[j] = index; } } Time complexity: Best case: O(n). It occurs when the data is in sorted order. After making one pass through the data and making no insertions, insertion sort exits. Average case: ?(n^2) since there is a wide variation with the running time. Worst case: O(n^2) if the numbers were sorted in reverse order. Examples: 30 9 65 52 28 21 The algorithm sees that 9 is smaller than 30 so it swaps. 9 30 65 52 28 21 52 is smaller than 65 so it swaps 9 30 52 65 28 21 28 is smaller than 30 so, it moves to appropriate location 9 28 30 52 65 21 21 is smaller than 28 so, it moves to appropriate location 8 21 28 30 52 65

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.