insertion sort

What is Insertion Sort

• is a non-comparison sorting algorithm that sorts elements by counting the number of occurrences of each unique element.

• builds the final sorted array one item at a time by comparing each new item to the already sorted items and inserting it into the correct position.

• repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• is an in-place comparison sorting algorithm that divides the input list into two parts: the sorted part at the front and the unsorted part at the back.

How it works?(insertion sort)

• 1. Assume the first element is sorted.

  2. Take the next element and insert it into the sorted portion of the array at the correct position.

  3. Repeat until all elements are sorted.

• 1. Iterate over the list multiple times. 2. Compare each pair of adjacent items.

  3. Swap them if they are in the wrong order.

  4. Repeat until no swaps are needed

• 1. Initial State: Entire array is unsorted.

  2. Find the minimum element in the unsorted array.

  3. Swap it with the first unsorted element.

  4. Repeat steps 2-3 for the remaining unsorted portion

• 1. Find the range (maximum value) of the input elements. 2. Initialize a count array of this range.

  3. Count the occurrence of each element.

  4. Modify the count array by adding the previous counts

Time Complexity?(insertion sort)

• Best: O(n)

  Average: O(n)

  Worst:O(n)^2

• All:O(n)

• Best:O(n)

  Worst and Average: O(n^2)

• Best: O(n^2)

  Worst and Average:O(n+k)

Space Complexity(insertion sort)

• O(n)

• O(1)

What are the advantages of the insertion sort?

• Linear time complexity for a fixed range of input.

  Efficient for sorting integers.

• Simple to understand and implement. Efficient for large datasets

• Simple to implement. Performs well on small lists

• Efficient for small data sets. Stable and in-place. Works well on nearly sorted data

Insertion sort stability? and in place?

• stable

  in place

• no stable

  in place

• no stable

  no in place

• stable

  no in place