{"id":34624,"date":"2024-11-01T09:30:15","date_gmt":"2024-11-01T09:30:15","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34624"},"modified":"2024-11-01T11:40:27","modified_gmt":"2024-11-01T11:40:27","slug":"javascript-coding-test-course-insertion-sort","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34624\/","title":{"rendered":"JavaScript Coding Test Course, Insertion Sort"},"content":{"rendered":"

<\/p>\n

Hello! In this post, we will learn how to solve algorithm problems using JavaScript. The topic is ‘Insertion Sort’. All algorithms are means to solve specific problems, and insertion sort is one of the most fundamental and important sorting algorithms. Through this article, we will understand the concept of insertion sort and explore in detail how to implement it in JavaScript.<\/p>\n

1. What is Insertion Sort?<\/h2>\n

Insertion sort is a very efficient sorting algorithm when the data is nearly sorted. This algorithm basically divides the list into two parts and builds a sorted list by inserting new elements into their appropriate positions. It has a methodology of comparing each element one by one and inserting it into its rightful place.<\/p>\n

1.1. How Insertion Sort Works<\/h3>\n

The basic process of insertion sort works as follows:<\/p>\n

    \n
  1. Compare the first two elements.<\/li>\n
  2. If the first element is greater than the second element, swap their positions.<\/li>\n
  3. Select the next element and appropriately insert it into the sorted list. Repeat this process until all elements are sorted.<\/li>\n<\/ol>\n

    2. Time Complexity of Insertion Sort<\/h2>\n

    The average time complexity of insertion sort is O(n\u00b2). Even in the worst case, it remains O(n\u00b2), and it only shows O(n) performance in the best case. However, the best case occurs when the data is already sorted. For this reason, insertion sort is very efficient for cases with a small number of elements or nearly sorted data.<\/p>\n

    3. Problem Definition<\/h2>\n

    3.1. Problem Statement<\/h3>\n

    Given an integer array like the following, write a function to sort the array in ascending order using insertion sort.<\/p>\n

    \nInput: [5, 2, 9, 1, 5, 6]\nOutput: [1, 2, 5, 5, 6, 9]\n    <\/code><\/pre>\n
    4. Algorithm Implementation<\/h2>\n
    Now let’s actually implement insertion sort in JavaScript. The code is simple and is as follows:<\/p>\n
    \nfunction insertionSort(arr) {\n    for (let i = 1; i < arr.length; i++) {\n        let key = arr[i];\n        let j = i - 1;\n\n        \/\/ Compare the current key with the sorted part to find position\n        while (j >= 0 && arr[j] > key) {\n            arr[j + 1] = arr[j];  \/\/ Move position\n            j--;\n        }\n        arr[j + 1] = key;  \/\/ Insert position\n    }\n    return arr;\n}\n\n\/\/ Test\nconst input = [5, 2, 9, 1, 5, 6];\nconsole.log(insertionSort(input));  \/\/ [1, 2, 5, 5, 6, 9]\n    <\/code><\/pre>\n
    4.1. Code Explanation<\/h3>\n
    The above code is structured as follows:<\/p>\n