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

Selection Sort

The Selection Sort is intuitive algorithm where we select elements one by one and compare with others. The main approach of selection sort is to find the minimum element of the array and put it in the first position. There is the first element of the sorted subarray. Then, find the minimum element in the rest of the array (which is unsorted), and move it next to the sorted subarray as second one, and so on.

Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.

Example 1

Example 2: Step by Step

arr = [0, -4, 12, 4, 10, 4]

Find min element in subarray arr[0:] and place it to the beginning:

arr = [ -4, 0, 12, 4, 10, 4]

Find min element in subarray arr[1:] and place it at the end of sorted subarray:

arr = [-4, 0, 12, 4, 10, 4 ]

Find min element in subarray arr[2:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 12, 10, 4 ]

Find min element in subarray arr[3:] and place it to the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Find min element in subarray arr[4:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.

arr = [-4, 0, 4, 4, 10, 12]

Time complexity of the algorithm is O(N^2), where N is the length of array. That's because there are two nested loops in the algorithm. To be clear, the number of operations is N-1 + N-2 + … 2+1 = N(N-1)/2, which is O(N^2).

Space complexity: O(1).


              12345678910111213141516
            
arr = [-12, 9, 1, 3, 40, 17, 3]
 
for i in range(len(arr)-1):
     
  # Find the minimum element in unsorted array arr[i+1:]
  ind = i 
  for j in range(i+1, len(arr)): # Find ind of min element
    if arr[ind] > arr[j]:
            ind = j
             
  # Swap the found minimum element with
  # The first element of unsorted subarray      
  arr[i], arr[ind] = arr[ind], arr[i]

print(arr)

Tarea

Modify Selection Sort algorithm to do the sort in descending order.

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

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 3

Selection Sort

Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.

Example 1

Example 2: Step by Step

arr = [0, -4, 12, 4, 10, 4]

Find min element in subarray arr[0:] and place it to the beginning:

arr = [ -4, 0, 12, 4, 10, 4]

Find min element in subarray arr[1:] and place it at the end of sorted subarray:

arr = [-4, 0, 12, 4, 10, 4 ]

Find min element in subarray arr[2:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 12, 10, 4 ]

Find min element in subarray arr[3:] and place it to the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Find min element in subarray arr[4:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.

arr = [-4, 0, 4, 4, 10, 12]

Space complexity: O(1).


              12345678910111213141516
            
arr = [-12, 9, 1, 3, 40, 17, 3]
 
for i in range(len(arr)-1):
     
  # Find the minimum element in unsorted array arr[i+1:]
  ind = i 
  for j in range(i+1, len(arr)): # Find ind of min element
    if arr[ind] > arr[j]:
            ind = j
             
  # Swap the found minimum element with
  # The first element of unsorted subarray      
  arr[i], arr[ind] = arr[ind], arr[i]

print(arr)

Tarea

Modify Selection Sort algorithm to do the sort in descending order.

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

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 3

Selection Sort

Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.

Example 1

Example 2: Step by Step

arr = [0, -4, 12, 4, 10, 4]

Find min element in subarray arr[0:] and place it to the beginning:

arr = [ -4, 0, 12, 4, 10, 4]

Find min element in subarray arr[1:] and place it at the end of sorted subarray:

arr = [-4, 0, 12, 4, 10, 4 ]

Find min element in subarray arr[2:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 12, 10, 4 ]

Find min element in subarray arr[3:] and place it to the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Find min element in subarray arr[4:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.

arr = [-4, 0, 4, 4, 10, 12]

Space complexity: O(1).


              12345678910111213141516
            
arr = [-12, 9, 1, 3, 40, 17, 3]
 
for i in range(len(arr)-1):
     
  # Find the minimum element in unsorted array arr[i+1:]
  ind = i 
  for j in range(i+1, len(arr)): # Find ind of min element
    if arr[ind] > arr[j]:
            ind = j
             
  # Swap the found minimum element with
  # The first element of unsorted subarray      
  arr[i], arr[ind] = arr[ind], arr[i]

print(arr)

Tarea

Modify Selection Sort algorithm to do the sort in descending order.

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

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.

Example 1

Example 2: Step by Step

arr = [0, -4, 12, 4, 10, 4]

Find min element in subarray arr[0:] and place it to the beginning:

arr = [ -4, 0, 12, 4, 10, 4]

Find min element in subarray arr[1:] and place it at the end of sorted subarray:

arr = [-4, 0, 12, 4, 10, 4 ]

Find min element in subarray arr[2:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 12, 10, 4 ]

Find min element in subarray arr[3:] and place it to the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Find min element in subarray arr[4:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.

arr = [-4, 0, 4, 4, 10, 12]

Space complexity: O(1).


              12345678910111213141516
            
arr = [-12, 9, 1, 3, 40, 17, 3]
 
for i in range(len(arr)-1):
     
  # Find the minimum element in unsorted array arr[i+1:]
  ind = i 
  for j in range(i+1, len(arr)): # Find ind of min element
    if arr[ind] > arr[j]:
            ind = j
             
  # Swap the found minimum element with
  # The first element of unsorted subarray      
  arr[i], arr[ind] = arr[ind], arr[i]

print(arr)

Tarea

Modify Selection Sort algorithm to do the sort in descending order.

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 3

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