CS 261 University of Puget Sound Spring, 2020
 
Computer Science II
Abstract Data Types and their Implementations, Some Basic Algorithms,
Object-oriented Problem Solving, and Efficiency
 

Warning: This course is under development. Although the basic structure of this course is largely established, nothing on this Web site should be considered official or even possibly correct.
DO NOT MAKE PLANS BASED ON THE CONTENTS OF THIS SITE UNTIL JANUARY, 2020.

Selection Sort

Given an array a[0], ..., a[n], the idea of a selection sort is to find the largest element in an array segment a[0], ..., a[k], and swap this largest element with a[k]. In more detail, the algorithm proceeds as follows:

The algorithm stops after the array segment contains just two elements, the largest element is located, and that largest element is swapped for the code segment A[0], ..., A[1]

This process is illustrated in the following diagram:

selection sort for [4, 8, 6, 9, 7, 3, 5]

Some coding details

Finding the Maximum and Swapping

Given the array segment a[0], ..., a[k], methodically start with element a[0] as the smallest element encountered so far, and then examine each successive array element—updating the index of the largest as needed. The basic code is 

     //find the index of the maximum array element in A[0], ..., A[k]
     int maxIndex = 0;  // as the search begins, the largest is at index 0
     for (index = 1; index ≤ k; index++) {   //proceed through the array
         if (A[maxIndex] < A[index]) {       // update maxIndex when
            maxIndex = index;                // something bigger is found
        }
     }

     //swap largest with A[k]
     temp = A[k];
     A[k] = A[maxIndex];
     A[maxIndex] = temp;

Repeat process for k = n, n-1, n-2, ..., 1

Nesting the above search and swap in a loop completes the algorithm: 

  for (k = n; k ≥ 1; k--} {
     //find the index of the maximum array element in A[0], ..., A[k]
     int maxIndex = 0;  // as the search begins, the largest is at index 0
     for (index = 1; index ≤ k; index++) {   //proceed through the array
         if (A[maxIndex] < A[index]) {       // update maxIndex when
            maxIndex = index;                // something bigger is found
          }
     }

     //swap largest with A[k]
     temp = A[k];
     A[k] = A[maxIndex];
     A[maxIndex] = temp;
  }
created 22 January 2020
revised 22-23 January 2020 		Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.