Selection Sort - StarShipTutor/StarshipTutorAPCS GitHub Wiki

See also tutorialspoint.com

Concept

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

Scan the array from X[0] to X[N - 1] using index i If the current item X[i] < X[0] then swap X[i] and X[0] Making X[0] the smallest item found so far After all N items have been scanned X[0] is the smallest item in the array

Now start with X[1] and repeat At the end of that scan X[0] is the smallest and X[1] is the second smallest At the end of N - 1 scans the array is sorted

Algoritm

int[] X; 
int i, j, indexOfSmallestX;

for ( i = 0; i < X.length; i++ )
{
   indexOfSmallestX = i;
   for ( j = i + 1; j < X.length; j++ )
   {
       if (X[j] < X[indexOfSmallest] )
       {
          indexOfSmallestX = j; 
       }
    } // End for ( j )

   temp = X[i];
   X[i] = X[indexOfSmallest];
   X[indexOfSmallest] = temp;

}  // End for ( i )

Java Code

 public void selectionSort ()
    {
        for (int sortedIndex = 0; sortedIndex < this.size(); sortedIndex++)
        {
            int tempValue;
            int unsortedIndex;

            int minIndex = sortedIndex;                 // Starting point for unsorted list
            for ( unsortedIndex = sortedIndex; unsortedIndex < this.size(); unsortedIndex++)
            {

                if (( int ) this.get( unsortedIndex ) < ( int ) this.get( minIndex ))

                {
                    minIndex = unsortedIndex;            // log location of nextGuess as new smallest value
                }
            } // End For ( unsortedIndex )

            if (( int ) this.get( minIndex ) < ( int ) this.get(sortedIndex))   // If smallest value is smaller than the initial guess
            {
                tempValue = ( int ) this.get ( minIndex );
                this.set(minIndex, this.get(sortedIndex));  // Swap new smallest value into place
                this.set(sortedIndex, tempValue);
            }
        } // End for ( sortedIndex ) 
    } // selectionSort