Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Insertion Sort | Simple Algorithms
Sorting Algorithms

book
Insertion Sort

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

              
123456789101112131415

            
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
copy
Oppgave

Swipe to start coding

Use the insertionSort() function to sort an array. You can either use the existing function or implement it yourself. Output the sorted array.

Løsning

arr = [9.66, 13.94, 49.51, 3.94, 58.6, 60.86, 51.8, 18.51, 14.57, 57.28, 56.3, 31.95, 15.07]
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

arr = insertionSort(arr)
print(arr)

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 4
arr = [9.66, 13.94, 49.51, 3.94, 58.6, 60.86, 51.8, 18.51, 14.57, 57.28, 56.3, 31.95, 15.07]

def insertionSort():
_ _ _

# Sort the arr and print the result
toggle bottom row
some-alt