Java Coding Test Course, Insertion Sort

Hello! In this article, we will discuss one of the algorithms that frequently appear in coding tests using the Java programming language: ‘Insertion Sort’. Insertion Sort is a comparison-based sorting algorithm that is widely used among beginner programmers due to its efficiency and simplicity. In this article, we will explain the theoretical background of Insertion Sort, implement the sorting algorithm through a problem, and describe the process in detail.

What is Insertion Sort?

Insertion Sort is a sorting algorithm that inserts each element of an unsorted dataset into a sorted portion one by one. You can think of this algorithm as similar to organizing cards in a card game. In other words, you take out each card and insert it into the appropriate position in a pile of already sorted cards.

How the Insertion Sort Algorithm Works

  1. Consider an array that is divided into a sorted part and an unsorted part.
  2. Select the first element from the unsorted part.
  3. Find the position of the selected element in the sorted part and insert it there.
  4. Repeat the above process until there are no unsorted elements left.

The time complexity of this algorithm is O(n^2) in the worst case, O(n) in the best case, and O(n^2) on average. However, because of its slow performance on smaller datasets, other sorting algorithms (e.g., Quick Sort, Heap Sort, etc.) may be more suitable for large datasets.

Algorithm Problem: Implementing Insertion Sort

Here is a problem to implement the Insertion Sort algorithm.

Problem Description

Write a function to sort a given integer array in ascending order.

Input

Length of the array n (1 ≤ n ≤ 1000)
Integer array a (1 ≤ a[i] ≤ 10^6)

Output

Array sorted in ascending order

Sample Input

5
5 2 9 1 5

Sample Output

1 2 5 5 9

Process for Solving the Problem

To solve this problem, we will implement the Insertion Sort algorithm in Java following the steps below.

1. Input the Array

First, we need to input the length of the array and its elements. This can be easily done using Java’s Scanner class.

import java.util.Scanner;

public class InsertionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Input the length of the array
        int n = scanner.nextInt();
        int[] arr = new int[n];
        
        // Input the elements of the array
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
    }
}

2. Implement the Insertion Sort Algorithm

Next, we implement the Insertion Sort algorithm. The main idea is to compare the current element with the previous elements and insert it in the appropriate position. We will use nested loops to implement this.

public static void insertionSort(int[] arr) {
    int n = arr.length;

    for (int i = 1; i < n; i++) {
        int key = arr[i]; // The element to compare
        int j = i - 1;

        // Move elements that are greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Insert key at the appropriate position
        arr[j + 1] = key;
    }
}

3. Print the Array

To print the sorted array, we will write a simple output function.

public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

4. Integrate the Whole Program

Finally, we will combine all the above functionalities into the main method to create the complete program.

public class InsertionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        insertionSort(arr);
        printArray(arr);
    }

    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--;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Conclusion

In this lesson, we learned how to implement the Insertion Sort algorithm using Java. Insertion Sort helps to understand the basics of algorithms and can greatly contribute to improving skills. As this is a topic that frequently appears in algorithm problem-solving, it is recommended to practice adequately. Understanding the advantages and disadvantages of Insertion Sort and comparing it with other sorting algorithms is also a good way to learn.

Finally, for algorithm problem-solving and coding test preparation, I recommend solving more diverse problems and studying algorithms systematically. Thank you!