Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Selection Sort, Bubble Sort, & Insertion Sort

Explore the fundamentals of selection sort, bubble sort, and insertion sort algorithms. Understand how each organizes arrays by comparison and swapping, their time and space complexities, and practical use cases. This lesson helps you recognize the key differences and efficiency considerations among these basic sorting methods.

We'll cover the following...

What is sorting?

Sorting is any process of arranging items systematically. In computer science, sorting algorithms put elements of a list in a certain order.

The most frequently used orders are numerical (according to numbers) and lexicographical (according to letters). Efficient sorting is important for optimizing the efficiency of other algorithms which require sorted input or sort given input as part of their process.

Formal Definition

A list or array is sorted in ascending order if ∀\forall ii, such that i≤n−1i \leq n-1, A[i]≤A[i+1]A[i]\leq A[i+1]. Similarly, a list or array is sorted in descending order if ∀\forall ii, such that i≤n−1i \leq n-1, A[i]≥A[i+1]A[i]\geq A[i+1].

Selection Sort Algorithm

The algorithm divides the input array into two parts: the sublist of already-sorted elements, which is built up from left to right, and the sublist of the remaining elements that occupy the rest of the list and need to be sorted.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

In other words, this algorithm works by iterating over the array and swapping each element with the minimum element found in the rest of the array.

Look at the illustration for a clearer picture.

Also, here is the code. Note that we’ve made most helper functions such as findMin() and printArray() available in most code widgets in this course; found in a file called AuxiliaryFunctions.cpp you just have to import it. You can have a look at how the functions work in the appendix.

Attribution: wikipedia. CC-BY-SA 3.0

C++
#include "AuxiliaryFunctions.h"
void selectionSort(int* arr, int arrSize) {
  int maxInd;
  for(int i = 0; i < arrSize; i++) {
    maxInd = findMin(arr, i, arrSize-1); // findMin expects a start and end index so arrSize won't work
    swap(arr[i],arr[maxInd]);
  }
}
int main() {
  int arr[] = {5,4,1,0,5,95,4,-100,200,0};
  int arrSize = 10;
  selectionSort(arr, arrSize);
  printArray(arr,arrSize);
}

Time Complexity

The time complexity of this code is in O(n2)O(n^2) because findMin() iterates over the entire array for each element of the given array. The quadratic time complexity makes it impractical for large inputs.

Bubble Sort Algorithm

This is another famous sorting algorithm also known as ‘sinking sort’. It works by comparing adjacent pairs of elements and swapping them if they are in the wrong order. This is repeated until the array is sorted.

Think of it this way: a bubble passes over the array and ‘catches’ the maximum/minimum element and brings it over to the right side.

C++
#include <iostream>
using namespace std;
#include "AuxiliaryFunctions.h"
void bubbleSort(int arr[], int arrSize) { 
   int i, j; 
   for (i = 0; i < arrSize-1; i++)       
       // Last i elements are already in place    
       for (j = 0; j < arrSize-i-1; j++)  
           if (arr[j] > arr[j+1]) 
              swap(arr[j], arr[j+1]); 
}
int main() {
  int arr[] = {5,4,1,0,5,95,4,-100,200,0};
  int arrSize = 10;
  bubbleSort(arr, arrSize);
  printArray(arr, arrSize);
}

Time Complexity

The time complexity of this code is in O(n2)O(n^2). Again, this algorithm is not very efficient.

Insertion Sort

Insertion sort is another very famous sorting algorithm, and works the way you would naturally sort in real life.

It iterates over the given array, and figures out what the correct position of every element is and inserts it there.

Attribution: wikipedia. CC-BY-SA 3.0

C++
#include "AuxiliaryFunctions.h"
void printArray(int* arr, int arrSize) {
  for(int i = 0; i < arrSize; i++)
    cout<<arr[i]<< " ";
  cout << endl;
}
int findMin(int* arr, int start, int end) {
  if(end<=0 || start < 0)
    return -1; 
  
  int minInd = start;
  for(int i = start+1; i <= end; i++) {
    if(arr[minInd] > arr[i])
      minInd = i;
  }
  return minInd;     
} 
int findMax(int* arr, int start, int end) {
  if(end<=0 || start < 0)
    return -1; 
  
  int maxInd = start;
  for(int i = start+1; i <= end; i++) {
    if(arr[maxInd] < arr[i])
      maxInd = i;
  }
  return maxInd;     
}

Time Complexity

The algorithm is in O(n2)O(n^2), which, again, makes it a poor choice for large input sizes. However, notice that the complexity is actually n2n^2 only when the input array is sorted in reverse. So the ‘best-case’ complexity (when the array is sorted in the correct order) is Ω(n)\Omega(n).

Space Complexity

Also, note that all of these algorithms are in-place, hence their space complexity is in O(1)O(1).