Insertion Sort - StarShipTutor/StarshipTutorAPCS GitHub Wiki

See also tutorialspoint.com

Concept

Assume an array of N items theArray[0] ... theArray[N - 1]

Divide theArray[] into a lower sorted part and an upper unsorted part delimited by :

sortedSubarray[] = theArray[0] ... theArray[largestSortedIndex]

unsortedSubarray[] = theArray[largestSortedIndex + 1] ... theArray[N - 1]

Goal : Insert theArray[largestSortedIndex + 1] into sortedSubarray[]

Scan sortedSubarray[] to find insertLocationIndex

tempValue = theArray[largestSortedIndex + 1];

Move elements from theArray[insertLocationIndex] to theArray[largestSortedIndex] up one

theArray[insertLocationIndex] = tempValue;

largestSortedIndex++;

Repeat

At the end of N - 1 scans the array is sorted

Algoritm

// Variables for Data Values

int[] theArray; 
int tempValue;

// Variables for Array indexes

int largestSortedIndex, insertLocationIndex;

for ( 
       largestSortedIndex = 0; 
       largestSortedIndex < theArray.length;
       largestSortedIndex ++
    )
{

   // scan sorted subarray for insertion location of tempValue

   tempValue = theArray[largestSortedIndex + 1]; // requires more than one element
   for ( 
          insertLocationIndex = 0;
          insertLocationIndex < largestSortedIndex;
          insertLocationIndex++
       )
   {
       if ( theArray[insertLocationIndex] >= tempValue )
       {
          break; // insertLocationIndex set, exit loop
       }

    } // End for ( insertLocationIndex )

    // Shuffle up array values to make room for insertion of tempValue

    for ( int i = largestSortedIndex; i > insertLocationIndex; i--)
    {
       theArray[i + 1] = theArray[i]; 
    }

    if ( insertLocationIndex  < largestSortedIndex ) // if == do nothing
    {
       theArray[insertLocationIndex] = tempValue; // Do the insertion
    }

}  // End for ( largestSortedIndex )

Java Code

public void insertionSort ()
    {
        // System.out.println ( "\nin insertionSort" );

        for (int sortedIndex = 0; sortedIndex < this.size() - 1; sortedIndex++)
        {
            int nextInsertValue, nextInsertIndex;
            int scanIndex, insertIndex;

            insertIndex = nextInsertIndex = sortedIndex + 1;

            nextInsertValue = ( int ) this.get( nextInsertIndex );     // New value to insert
            for ( scanIndex = 0; scanIndex <= sortedIndex; scanIndex++)
            {
                if ( nextInsertValue < ( int ) this.get( scanIndex ))
                {
                    break;   // scanIndex is left at the insert location
                }
            } // End For ( scanIndex )

            // Now move up and insert at insertIndex

            if (scanIndex < nextInsertIndex )
            {
                for ( int i = nextInsertIndex; i > scanIndex; i-- )
                {
                    this.set ( i, this.get ( i - 1));  // Move up elements
                }

                this.set (scanIndex, nextInsertValue );
            }

        } // End for ( sortedIndex )

    } // End insertionSort ()