# Selection Sort, Bubble Sort, and Insertion Sort

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

## 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$ $i$, such that $0 \leq$ $i \leq n-1$, $A[i]\leq A[i+1]$. Similarly, a list or array is sorted in *descending order* if $\forall$ $i$, such that $0 \leq$ $i \leq n-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`

.

class Sorting {static Helper obj = new Helper();public static void selectionSort(int[] arr, int arrSize) {int minInd;//traverse through all elements of the arrayfor (int i = 0; i < arrSize; i++) {//find the minimum element in the unsorted arrayminInd = obj.findMin(arr, i, arrSize - 1);//Swap the found minimum element with the leftmost unsorted elementint 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(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.

class Sorting {static Helper obj = new Helper();static void bubbleSort(int arr[], int arrSize) {int i, j, temp;//Traverse through all array elementsfor (i = 0; i < arrSize - 1; i++)// Last i elements are already in placefor (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 elementif (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(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.

class Sorting {static Helper obj = new Helper();static void insertionSort(int[] arr, int arrSize) {int ele, j;//Traverse through 1 to size of the arrayfor (int i = 1; i < arrSize; i++) {ele = arr[i]; // Element to be insertedj = i - 1;//shifts elements back to create space for the element to be insertedwhile (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(n^2)$, which, again, makes it a poor choice for large input sizes. However, notice that the complexity is actually $n^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 $\Omega(n)$.

## Space complexity

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