Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Selection Sort | Simple Algorithms
Sorting Algorithms
course content

Course Content

Sorting Algorithms

Sorting Algorithms

1. Simple Algorithms
What is the SortingBig-O Notation OverviewSelection SortInsertion SortCounting SortBubble SortCocktail Sort
2. Divide and Conquer Algorithms
Merge SortQuicksort
3. Problems
Problem AProblem BProblem CProblem 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)
copy

Task

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

Task

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

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Section 1. Chapter 3
toggle bottom row

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

Task

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

Task

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

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Section 1. Chapter 3
toggle bottom row

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

Task

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

Task

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

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

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

Task

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

Switch to desktop for real-world practiceContinue from where you are using one of the options below
Section 1. Chapter 3
Switch to desktop for real-world practiceContinue from where you are using one of the options below
We're sorry to hear that something went wrong. What happened?
some-alt