Contenido del Curso

Sorting Algorithms

1. Simple Algorithms

What is the Sorting Big-O Notation Overview Selection Sort Insertion Sort Counting Sort Bubble Sort Cocktail Sort

2. Divide and Conquer Algorithms

Merge Sort Quicksort

3. Problems

Problem A Problem B Problem C Problem D

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).


              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

Tarea

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

Tarea

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

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

Sección 1. Capítulo 4

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).


              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

Tarea

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

Tarea

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

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

Sección 1. Capítulo 4

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).


              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

Tarea

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

Tarea

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

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

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).


              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

Tarea

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

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

Sección 1. Capítulo 4

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones