Insertion Sort is another simple sort algorithm that works with sorted and unsorted parts of an array. Values from unsorted part picked and placed to correct position in sorted part.

## Example1

## Example 2

[4 | `3` 2 10 12 1 4 6] -> [`3` 4 | 2 10 12 1 4 6]

[3 4 | `2` 10 12 1 4 6] -> [`2` 3 4 | 10 12 1 4 6]

[2 3 4 | `10` 12 1 4 6]-> [2 3 4 `10` | 12 1 4 6]

[2 3 4 10 | `12` 1 4 6] -> [2 3 4 10 `12` | 1 4 6]

[2 3 4 10 12 | `1` 4 6] -> [`1` 2 3 4 10 12 | 4 6]

[1 2 3 4 10 12 | `4` 6] -> [1 2 3 4 `4` 10 12 | 6]

[1 2 3 4 4 10 12 | `6`] -> [1 2 3 4 4 `6` 10 12]

*Time complexity* is O(N^2), because each next element of an unsorted part iterates through elements of the sorted part. There are two nested loops in the algorithm.

*Space complexity*: O(1).

def insertionSort(arr):
  
  # Iterate unsorted subarrays
  for i in range(1, len(arr)):
    key = arr[i] # Element to move
    j = i-1

    # Iterate sorted part and replace elements one position right
    while j>=0 and key < arr[j]: 
      arr[j+1] = arr[j]
      j-=1

    # Put key element on its position
    arr[j+1]= key
  return arr

Sorting is one of the main topics on Tech Interviews. There are a lot of different sorting algorithms that differ by time and space complexity and approaches. In this mini-course, we’ll take a look through the most popular and relevant of them. Then6 you'll try to solve some Interview problems.

Some useful info about algorithms. You'll familiarize yourself with the popular algorithms for beginners.

More advanced, but commonly used algorithms.

Try to solve interview problems using Sorting Algorithms!

Insertion Sort

Example1

Example 2

解答