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

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 3
toggle bottom row

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 3
toggle bottom row

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

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 desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 1. Chapter 3
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt