Class DirectInsertion

java.lang.Object
topics.sorting.insertion.DirectInsertion
All Implemented Interfaces:
SortingAlgorithm
public class DirectInsertion extends Object implements SortingAlgorithm

Direct Insertion Sort

An educational sorting implementation that builds the final sorted array one item at a time. It operates similarly to how one might sort a hand of playing cards: picking an element and inserting it into its mathematically correct position among the already sorted elements to its left.

Algorithm Steps

  1. Assume the first element (index 0) is already sorted.
  2. Pick the next element, referred to as the key.
  3. Compare the key with elements in the sorted sub-array to its left.
  4. Shift all elements strictly greater than the key one position to the right.
  5. Insert the key into the newly vacated correct position.
  6. Repeat until the boundary reaches the end of the array.

Complexity Analysis

  • Time Complexity (Worst/Average): O(N²) - Occurs when the array is in reverse order.
  • Time Complexity (Best): O(N) - Occurs when the array is already sorted (the inner while loop never executes).
  • Space Complexity: O(1) - Sorts entirely in-place without recursion overhead.
  • Stability: Yes - Maintains the relative order of equal elements because it only shifts strictly greater elements.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Summary

    Constructors
    Constructor
    Description
    DirectInsertion()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • DirectInsertion

      public DirectInsertion()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place silently.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.