Bubble Sort Selection Sort and Insertion Sort Algorithms

Photo by Dimitry B on Unsplash

Introduction

In this post, we are going to discuss basic sorting algorithms. The sorting operation works as an intermediate solution to many interview problems.

Sorting algorithms are fundamental tools used to arrange data in a specific order, typically ascending or descending. This seemingly simple task plays a crucial role in various computing applications.

Bubble Sort

Bubble sort is the easiest sorting algorithm, In each iteration, we just compare the elements adjacent to each other swap them if they are in the wrong order and finally take the greatest element at the last position. The number of comparisons is more in bubble sort compared to selection and insertion sort. Here is the code block.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Time Complexity = O(n^2)
Spcae Complexity = O(1)

Selection Sort

It is a sorting technique in which we select one element(smallest/greatest) in each iteration and put it in the correct place in the collection.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

Time Complexity = O(n^2)
Spcae Complexity = O(1)

Insertion Sort

In this sorting algorithm, we make one element a key in each iteration and put it in the correct place of the collection. which means in every iteration it takes out one element from the list and puts it into its correct position.

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

Time Complexity = O(n^2)
Spcae Complexity = O(1)

These are basic implementations of Bubble Sort, Selection Sort and Insertion Sort algorithms in Java. They are not the most efficient sorting algorithms for large datasets, but they are easy to understand and implement.

In the next post, I will explain Merge sort and Quick sort which have better complexities and are used when we have large datasets to sort.

Thanks for reading!!