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.<\/p>\n
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.<\/p>\n
The time complexity of this algorithm is Here is a problem to implement the Insertion Sort algorithm.<\/p>\n Write a function to sort a given integer array in ascending order.<\/p>\n To solve this problem, we will implement the Insertion Sort algorithm in Java following the steps below.<\/p>\n First, we need to input the length of the array and its elements. This can be easily done using Java’s 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.<\/p>\n To print the sorted array, we will write a simple output function.<\/p>\n Finally, we will combine all the above functionalities into the main method to create the complete program.<\/p>\n 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.<\/p>\n Finally, for algorithm problem-solving and coding test preparation, I recommend solving more diverse problems and studying algorithms systematically. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"O(n^2)<\/code> in the worst case, O(n)<\/code> in the best case, and O(n^2)<\/code> 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.<\/p>\nAlgorithm Problem: Implementing Insertion Sort<\/h2>\n
Problem Description<\/h3>\n
Input<\/h3>\n
Length of the array n (1 \u2264 n \u2264 1000)\nInteger array a (1 \u2264 a[i] \u2264 10^6)<\/code><\/pre>\nOutput<\/h3>\n
Array sorted in ascending order<\/code><\/pre>\nSample Input<\/h3>\n
5\n5 2 9 1 5<\/code><\/pre>\nSample Output<\/h3>\n
1 2 5 5 9<\/code><\/pre>\nProcess for Solving the Problem<\/h2>\n
1. Input the Array<\/h3>\n
Scanner<\/code> class.<\/p>\nimport java.util.Scanner;\n\npublic class InsertionSort {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n \/\/ Input the length of the array\n int n = scanner.nextInt();\n int[] arr = new int[n];\n \n \/\/ Input the elements of the array\n for (int i = 0; i < n; i++) {\n arr[i] = scanner.nextInt();\n }\n }\n}<\/code><\/pre>\n2. Implement the Insertion Sort Algorithm<\/h3>\n
public static void insertionSort(int[] arr) {\n int n = arr.length;\n\n for (int i = 1; i < n; i++) {\n int key = arr[i]; \/\/ The element to compare\n int j = i - 1;\n\n \/\/ Move elements that are greater than key one position ahead\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n \/\/ Insert key at the appropriate position\n arr[j + 1] = key;\n }\n}<\/code><\/pre>\n3. Print the Array<\/h3>\n
public static void printArray(int[] arr) {\n for (int i = 0; i < arr.length; i++) {\n System.out.print(arr[i] + \" \");\n }\n System.out.println();\n}<\/code><\/pre>\n4. Integrate the Whole Program<\/h3>\n
public class InsertionSort {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int n = scanner.nextInt();\n int[] arr = new int[n];\n\n for (int i = 0; i < n; i++) {\n arr[i] = scanner.nextInt();\n }\n\n insertionSort(arr);\n printArray(arr);\n }\n\n public static void insertionSort(int[] arr) {\n int n = arr.length;\n for (int i = 1; i < n; i++) {\n int key = arr[i];\n int j = i - 1;\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j];\n j--;\n }\n arr[j + 1] = key;\n }\n }\n\n public static void printArray(int[] arr) {\n for (int i = 0; i < arr.length; i++) {\n System.out.print(arr[i] + \" \");\n }\n System.out.println();\n }\n}<\/code><\/pre>\nConclusion<\/h2>\n