Algorithms for Coding Interviews in Java/

...

/

Selection Sort, Bubble Sort, and Insertion Sort

Selection Sort, Bubble Sort, and Insertion Sort

Here's an overview of introductory sorting algorithms including selection sort, bubble sort, and insertion sort.

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 specific order.

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

Formal definition

A list or array of size n is sorted in ascending order if ∀\forall ii, such that 0≤0 \leq 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 0≤0 \leq 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.

Down below is the code for it as well.

Note: We’ve made most of the helper functions, such as findMin() and printArray(), available in the file Helper.java as a part of the class called Helper.

Attribution: wikipedia. CC-BY-SA 3.0

Press + to interact
main.java
Helper.java
class Sorting {
 static Helper obj = new Helper();
 public static void selectionSort(int[] arr, int arrSize) {
  int minInd;
  //traverse through all elements of the array
  for (int i = 0; i < arrSize; i++) {
   //find the minimum element in the unsorted array
   minInd = obj.findMin(arr, i, arrSize - 1);
   //Swap the found minimum element with the leftmost unsorted element
   int temp = arr[i];
   arr[i] = arr[minInd];
   arr[minInd] = temp;
  }
 }
 public static void main(String args[]) {
  int arr[] = {5,4,1,0,5,95,4,-100,200,0};
  int arrSize = 10;
  selectionSort(arr, arrSize);
  obj.printArray(arr, arrSize);
 }
}

As seen above, you first traverse all the elements of the unsorted array (line 7). Next, use the findMin function to find the minimum element in that array (line 9). Swap the found minimum element with the leftmost unsorted element (lines 11-13). Repeat the process until all the elements are sorted.

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.

Press + to interact
main.java
Helper.java
class Sorting {
 static Helper obj = new Helper();
 static void bubbleSort(int arr[], int arrSize) {
  int i, j, temp;
  //Traverse through all array elements
  for (i = 0; i < arrSize - 1; i++)
   // Last i elements are already in place      
   for (j = 0; j < arrSize - i - 1; j++)
    //Traverse the array from 0 to size of array[i-1] 
    //Swap if the element found is greater than the next element
    if (arr[j] > arr[j + 1]) {
     temp = arr[j];
     arr[j] = arr[j + 1];
     arr[j + 1] = temp;
    }
 }
 public static void main(String args[]) {
  int arr[] = {5,4,1,0,5,95,4,-100,200,0};
  int arrSize = 10;
  bubbleSort(arr, arrSize);
  obj.printArray(arr, arrSize);
 }
}

As seen above, start by traversing all the elements of the array (lines 6-8). Next, compare the current element with the element next to it (line 11). Swap the two if the next element is greater than the current (lines 12-14). Repeat the process until no more swaps are needed, meaning, the entire array is sorted.

Time complexity

The time complexity of the above 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 it works the way you would naturally sort items in real life.

It iterates over the given array, figures out what the correct position of every element is, and inserts each element in its place.

Attribution: wikipedia. CC-BY-SA 3.0

Press + to interact
main.java
Helper.java
class Sorting {
 static Helper obj = new Helper();
 static void insertionSort(int[] arr, int arrSize) {
  int ele, j;
  //Traverse through 1 to size of the array
  for (int i = 1; i < arrSize; i++) {
   ele = arr[i]; // Element to be inserted
   j = i - 1;
   //shifts elements back to create space for the element to be inserted
   while (j >= 0 && arr[j] > ele) {
    arr[j + 1] = arr[j];
    j = j - 1;
   }
   arr[j + 1] = ele;
  }
 }
 public static void main(String args[]) {
  int arr[] = {5,4,1,0,5,95,4,-100,200,0};
  int arrSize = 10;
  insertionSort(arr, arrSize);
  obj.printArray(arr, arrSize);
 }
}

As seen above, start by traversing the array (line 6). Store the element to be inserted in the variable ele (line 7). Next, shift all the elements back to create space for the element to be inserted and then insert the element (lines 11-15).

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