More Array Exercising

In this topic, you will be learning more about the Computer Science of sorting algorithms. This also happens to be a way for you to get some practice working with arrays, and thinking about their use. This topic will introduce you to another standard sorting algorithm.

The selection sort

The selection sort is an algorithm for sorting objects that searches through a list, finds the lowest value quantity, and places it in the first slot. It then searches through all the list except the first slot, finds the item with the lowest value, and places it in the second slot. It continues in this fashion until the whole list is sorted. Each "lowest" value is moved out of the next search by swapping the value at the "lowest Index" location with the location having the lowest value. A graphical example is shown below.

This process will be broken down into two functions, the actual sorting function, called selectionSort, and a utility function called findLowestValueIndex.

As previously described, the task of the selectionSort function is simply to start at the lowest index, search for the lowest valued item, and place it at that location. Then it moves to each next element, and repeats the same process. Here is the code for this sort.

   /*
   Name: runSelectionSort_A
   Process: sorts characters using the selection sort algorithm;
            function uses nested loops
   Function input/parameters: array of characters (char[]),
                              size of array (int)
   Function output/parameters: letters sorted in alphabetical order (char [])
   Function output/returned: none
   Device input/keyboard: none
   Device output/monitor: none
   Dependencies: swapChars
   */
   void runSelectionSort_A( char letters[], int arraySize )
      {
       // initialize function/variables
       int listIndex, lowestIndex, currentSearchIndex;

       // loop across list
        // loop up to, but not including last item
       for( listIndex = 0; listIndex < arraySize - 1; listIndex++ )
          {
           // set initial lowestIndex at first element to be searched
           lowestIndex = listIndex;

           // loop across list from current element to end
           for( currentSearchIndex = listIndex + 1;
                   currentSearchIndex < arraySize; currentSearchIndex++ )
             {
              // check for current element less than currently lowest element
              if( letters[ currentSearchIndex ] < letters[ lowestIndex ] )
                 {
                  // reset lowest index to current search index
                  lowestIndex = currentSearchIndex;
                 }
             }
           // end search loop

           // swap the item at the present position
           //   with the item at the lowest value position
              // function: swapChars
           swapChars( &listIndex, &lowestIndex );
          }
       // end list loop
      }

This function finds the smallest element within the whole list and places it at the first position, then it finds the lowest element starting at the second element in the list and places the lowest at that location, then it finds the lowest element starting at the third element in the list and places the lowest at that location, and so on. Notice it uses the swapCharsAtIndex function after finding the index of the lowest value to swap it with the current starting index. There is another, slightly more modular way to do this. Consider the following code.

   /*
   Name: runSelectionSort_B
   Process: sorts characters using the selection sort algorithm;
   function uses another function within outer loop
   Function input/parameters: array of characters (char[]),
                              size of array (int)
   Function output/parameters: letters sorted in alphabetical order (char [])
   Function output/returned: none
   Device input/keyboard: none
   Device output/monitor: none
   Dependencies: findLowestValueIndex, swapCharsByIndex
   */
   void runSelectionSort_B( char letters[], int arraySize )
      {
       // initialize function/variables
       int index, lowIndex;

       // loop up to, but not including last item
       for( index = 0; index < arraySize - 1; index++ )
          {
           // find index of lowest valued item in list
              // function: findLowestValueIndex
           lowIndex = findLowestValueIndex( letters, index, arraySize - 1 );

           // swap the item at the present position
           //   with the item at the lowest value position
              // function: swapCharsByIndex
           swapCharsByIndex( letters, index, lowIndex );
          }
       // end list loop
      }

The task of the findLowestValueIndex function is to, well, find the index of the lowest value in the list, specifically between two indices. As mentioned above, the range of the list searched will be reduced every time one pass is made and each of the succeeding first elements are found and placed.

Here is the code for the findLowestValueIndex function.

   /*
   Name: findLowestValueIndex
   Process: finds the index of the lowest value
            between two specified indices, inclusive
   Function input/parameters: character array (char[]),
                              start and end indices (int)
   Function output/parameters: none
   Function output/returned: index of lowest value as specified
   Device input/keyboard: none
   Device output/monitor: none
   Dependencies: none
   */
   int findLowestValueIndex( char[] charArr,
                  int startIndex, int endIndex )
      {
       // initialize function/variables
       int currentIndex;
       int lowestValIndex = startIndex;

       // loop across specified segment of array - start to end, inclusive
       for( currentIndex = startIndex + 1;
                                currentIndex <= endIndex; currentIndex++ )
          {
           // check for current element less than currently lowest element
           if( charArr[ currentIndex ] < charArr[ lowestValIndex ] )
              {
               // reset currently lowest index to current index
               lowestValIndex = currentIndex;
              }
          }
    // end search loop

    // return found lowest index
    return lowestValIndex;
   }

The findLowestValueIndex function is given the lowest index and the highest index, and searches for the index of the item with the lowest value. The index of the lowest value in this list would be one (1). So, when findLowestValueIndex returns the index one, the contents of index one and index zero (i.e., the lowest, starting index) are swapped, resulting in the list shown below.

Now, you can see that the lowest value object (i.e., the letter 'd') is at the lowest position. You can think of this as a list of one item that is already sorted. The next operation will be that findLowestValueIndex will find the lowest valued item starting at the next index up. In other words, it will search from index one to index four, inclusive, and find the lowest value in that group. That lowest value is the letter 'e', and it will be swapped with the second location in the list (i.e., index one). This is displayed below.

Again, you can think of the list of two items as sorted. You are now working with two kinds of lists. The list toward the left (i.e., letters 'd' and 'e') is sorted, while the list on the right (i.e., letters 'x', 'm', and 'r') is unsorted. The process will continue as follows. In the third iteration, findLowestValueIndex will return the index three because 'm' is the lowest of the remaining three. The contents of index two and three will be swapped.

In the fourth iteration, findLowestValueIndex will return the index four because 'r' is less than 'x', and since the last item ('x') is already in the right place, the sorting loop does not need to continue. The finally sorted list will appear as follows.

The selection sort makes simple sense. Find the lowest item and put it in the lowest spot. Then find the next lowest item and place it in the next lowest spot. In fact, this is a very popular strategy for most card players; they just don't know that they are applying a cool Computer Science strategy.

Watch this video to see the selection sort process animated.