Sorting

Because a sorted array facilitates much faster search algorithms, it is desireable to sort an array. There are many algorithms for sorting arrays. Unfortunately, the efficient ones tend to be difficult to understand.

This section presents an inefficient method to sort an array, but it is considered a little easier to understand. This is called selection sort.

In selection sort, the algorithm keeps track of an unsorted range in the array (to be sorted). In this range, the algorithm finds the least element, and swap it with the first element in the range. Then the algorithm makes the unsorted range one element smaller and repeat the same process.

The algorithm is presented as the following Pascal procedure:

procedure selectSort(var nums : array of integer;
                     n : integer);
  var
    t : integer;
    i : integer;
    minIndex : integer;
    firstUnsorted : integer;
  begin
    firstUnsorted := 0;
    while (firstUnsorted < n - 1)
      begin

        {first the least element from firstUnsorted}
        minIndex := firstUnsorted;
        i := firstUnsorted+1;
        while (i < n) do
          begin
            if nums[minIndex] < nums[i] then
              minIndex := i;
            i := i + 1
          end;

        {swap the least element with what's occupying its place}
        t := nums[firstUnsorted];
        nums[firstUnsorted] := nums[minIndex];
        nums[minIndex] := t;

        {advance firstUnsorted}
        firstUnsorted := firstUnsorted + 1
      end;
  end;

This algorithm is a little difficult to read because it is too long. We can convert this long procedure into two to make it more readable. We can extract the inner while loop because it serves a particular purpose: to find the index of the least element from nums[firstUnsorted] to nums[n-1]:

function findMinIndex(var nums : array of integer;
                       n : integer;
                       firstUnsorted : integer) : integer;
  var
    minIndex : integer;
    i : integer;
  begin
    {first the least element from firstUnsorted}
    minIndex := firstUnsorted;
    i := firstUnsorted+1;
    while (i < n) do
      begin
        if nums[minIndex] > nums[i] then
          minIndex := i;
        i := i + 1
      end;
    findMinIndex := minIndex
  end;

It also helps to define a small procedure to encapsulate the swap operation:

procedure swap(var x, y : integer);
  var 
    t : integer;
  begin
    t := x;
    x := y;
    y := t
  end;

We now have the function findMinIndex to find the index of the least element from index firstUnsorted to the end of the array. We also have a procedure swap to swap the values of two integers. Now, we can specify the overall sorting algorithm more clearly:

procedure selectSort(var nums : array of integer;
                     n : integer);
  var
    t : integer;
    minIndex : integer;
    firstUnsorted : integer;
  begin
    firstUnsorted := 0;
    while (firstUnsorted < n - 1)
      begin
        minIndex := findMinIndex(nums, n, firstUnsorted);
        swap(nums[minIndex], nums[firstUnsorted]);
        firstUnsorted := firstUnsorted + 1
      end;
  end;