JavaScript Code for Insertion Sort

What is Sorting?

Sorting refers to the process of organizing data in a specific sequence. This organization can be numeric, alphabetic, or even tailored to user-defined criteria. A typical application of sorting is the arrangement of student names in alphabetical order or the organization of product prices in ascending order. The practice of sorting enhances the efficiency of search and data manipulation tasks, as data that is sorted is considerably easier to navigate and manage.

There are various types of sorting algorithms, including quicksort, merge sort, insertion sort, and bubble sort. Each algorithm possesses distinct use cases and performance characteristics. Choosing the right algorithm often depends on factors such as the size of the dataset and considerations regarding time complexity.

What is Insertion Sort?

Insertion sort is an exceptionally straightforward and intuitive algorithm, closely resembling the method used to arrange playing cards. It constructs the sorted array incrementally, placing each new item in its appropriate position relative to those that have already been sorted. Insertion Sort is particularly effective when dealing with small datasets or data that is nearly sorted.

Insertion sort operates as an in-place algorithm, meaning it organizes the data by directly comparing and swapping values with one another, performing the sorting without requiring extra space beyond the input array itself. Its time complexity is notably greater than that of several more sophisticated algorithms (for instance, quicksort and mergesort), rendering it less efficient when handling larger datasets.

Working of Insertion Sort

Insertion sort maintains a division between sorted and unsorted elements within a list. Initially, this means that the sorted section contains a single element, while the remaining elements are yet to be sorted. The algorithm iterates through the unsorted portion, selecting each element and placing it into its appropriate position within the already sorted section.

Steps involved in insertion sort:

• ✅ The key will be the second element (with index number 1).
• ✅ Compare the Key with elements of sorted sub-array.
• ✅ When inserting the key into the sorted portion then we will have to shift all elements larger than the key one step to the right.
• ✅ Insert the key to insert at the proper position.

Example: Working of Insertion Sort

Let's examine the array [7, 3, 5, 2] to illustrate the process of insertion sort in a step-by-step manner:

Initial Array: [7, 3, 5, 2]

The initial number 7 is the sole digit that requires sorting. The latter portion represents the unsorted section, commencing with the number 3.

Step 1:

• ✅ Key = 3 (second element)
• ✅ Compare 3 with 7. Since 3 < 7, shift 7 one position to the right.
• ✅ Insert 3 in the first position.
• ✅ Array after Step 1: [3, 7, 5, 2]

Step 2:

• ✅ Key = 5 (third element)
• ✅ Compare 5 with 7. Since 5 < 7, shift 7 one position to the right.
• ✅ Compare 5 with 3. Since 5 > 3, place 5 after 3.
• ✅ Array after Step 2: [3, 5, 7, 2]

Step 3:

• ✅ Key = 2 (fourth element)
• ✅ Compare 2 with 7. Since 2 < 7, move 7 right by one position.
• ✅ Compare 2 with 5. As 2 < 5, move 5 one place to the right.
• ✅ Compare 2 with 3. Now, 2 < 3, so 3 needs to be shifted one position right.
• ✅ Add 2 in the first position.
• ✅ Array after Step 3: [2, 3, 5, 7]

Final Sorted Array: [2, 3, 5, 7]

JavaScript Code for Insertion Sort

The JavaScript execution of the insertion sort algorithm is detailed below:

Example

function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
      let key = array[i];
      let j = i - 1;
  
      while (j >= 0 && array[j] > key) {
        array[j + 1] = array[j];
        j--;
      }
      array[j + 1] = key;
    }
    return array;
  }
  
  // Example usage
  const array = [64, 34, 25, 12, 22, 11, 90];
  console.log("Original Array:", array);
  console.log("Sorted Array:", insertionSort(array));

Output:

Original Array: [
  64, 34, 25, 12,
  22, 11, 90
]
Sorted Array: [
  11, 12, 22, 25,
  34, 64, 90
]

Explanation of the Code

• ✅ The outer loop runs from second element (index 1) because we assume first element is sorted.
• ✅ Key = Current element to be compared.
• ✅ Inner while loop moves values in sorted space to the right if they are bigger than the key.
• ✅ When the appropriate location for the key is discovered, the key is inserted and the next element is reviewed.

Is Insertion Sort Stable?

Indeed, a sorting algorithm is deemed stable if the relative order of equal elements in the input array is maintained in the resulting output array. This characteristic renders insertion sort particularly advantageous in scenarios where it is essential to retain the sequence of duplicate items, such as when sorting records according to multiple criteria.

What Kind of Algorithm is Insertion Sort?

Insertion sort is a sorting algorithm that relies on comparisons to arrange elements within an array stored in memory. It employs a series of comparisons to determine the correct position for each element, shifting them accordingly within the input array without requiring any extra memory allocation. Its straightforward nature and minimal implementation complexity render it suitable for sorting small datasets or those that are nearly sorted.

Is Insertion Sort a Greedy Algorithm?

No, insertion sort does not qualify as a greedy algorithm. Greedy algorithms represent a class of algorithms that make localized decisions at every stage, aiming to achieve an overall optimal solution. Conversely, insertion sort focuses solely on constructing a sorted array by positioning each element correctly, without considering a global optimization strategy at each iteration.

Time Complexity of Insertion Sort Algorithm

Insertion sort is based on input array types:

• ✅ Best Case (O(n)): This happens when the array is in sorted order. It does not need any shifting, and the algorithm can just iterate over the array.
• ✅ Worst Case (O(n²)): When the array is in descending order. For every other element in the sorted section, each element has to be compared and pushed back.
• ✅ Average Case (O(n²)): Applies to random arrangements of elements.

Due to the fact that the worst-case time complexity of insertion sort is quadratic, this sorting algorithm is not an ideal choice for handling large datasets.

Does Insertion Sort Use Divide and Conquer?

No, the concept of divide and conquer involves partitioning the problem into progressively smaller sub-problems, solving each one independently, and then combining their results. Algorithms like quicksort and mergesort exemplify this approach. Conversely, insertion sort organizes the array in a step-by-step manner without the need to break it down into smaller issues.

Why is Insertion Sort Slow?

Due to the average and worst-case time complexity of insertion sort being O(n²), this method tends to be inefficient for handling large datasets. The sorting process involves comparing the current element against all preceding elements within the already sorted portions, and shifting those elements when necessary. This repetitive nature of comparisons and shifting renders insertion sort quite ineffective when tasked with sorting a large array. For handling larger datasets, it is advisable to utilize optimized algorithms like mergesort or quicksort, as they significantly reduce the number of comparisons and swaps required to sort the complete dataset.

Conclusion

Insertion sort is an uncomplicated sorting technique that performs optimally with small or nearly sorted collections of data. Although it may not be the quickest algorithm for larger arrays, it offers a satisfactory performance due to its relative ease of implementation and stability. Understanding its operational principles provides programmers with an opportunity to apply it using JavaScript.