Selection Sort

Many sorting algorithms exist. The sorting algorithm discussed here is called the selection sort.

In a selection sort, a list is arranged by selecting an element in the list and moving it to its proper position in the list.

Let list be a list of integers. Arrange the elements in the list in ascending order.

This algorithm finds the location of the smallest element in the unsorted list and moves it to the top of the list.

  • The first time we locate the smallest element in the entire list.
  • The second time we locate the smallest element in the list starting from the second element in the list, and so on.

[0] [1] [2] [3] [4] [5][6] [7] [8][9]

16 / 30 / 24 / 7 / 25 / 62 / 45 / 5 / 65 / 50

list

Initially, the list is unsorted. So we find the smallest element in the list. The smallest element is in position 7.

Because the smallest element is in position 7, swap it with the element in position 1. The newly arranged list is shown in Fig 8.2

[0] [1] [2] [3] [4] [5][6] [7] [8][9]

5 / 30 / 24 / 7 / 25 / 62 / 45 / 16 / 65 / 50

Figure 8.3

List

Figure 8.4 shows the unsorted portion of the list that must be sorted.

[0] [1] [2] [3] [4] [5][6] [7] [8][9]

5 / 30 / 24 / 7 / 25 / 62 / 45 / 16 / 65 / 50

Unsorted portion of list

Figure 8.4

The next smallest element in the list is 7 in position 3. Swap this element with the element in the first element in the unsorted part of the list. See Figure 8.5

[0] [1] [2] [3] [4] [5][6] [7] [8][9]

5 / 7 / 24 / 30 / 25 / 62 / 45 / 16 / 65 / 50

Unsorted portion of list

Figure 8.5

Now the unsorted list is list[2] … list[9]. So we repeat the preceding process of finding the position of the smallest element in the unsorted portion of the list. When this position is found exchange the element found with the element at the beginning of the unsorted portion of the list.

In other words, the algorithm requires the following steps:

  1. Find the location of the smallest element in the unsorted portion of the list. At the beginning the unsorted portion of the list would be the entire list.
  2. Exchange/swap the element at the position with the first element in the unsorted portion of the list.

That is,

Applying this to the RainfallReading class. Here is a skeletal outline of the algorithm.

// The method would look somewhat like this

for (int startScan = 0; startScan < rainfall.length – 1; startScan ++)

{

int position = findPosition(startScan );

swap( position, startScan );

}

int findPosition(int startScan )

{

// define method

}

void swap( int minIndex, int startScan )

{

// define method

}

// Method

int findPosition(int startFrom)

{

int position = startFrom;

for (int i = startFrom + 1; i < rainfall.length; i++)

if (rainfall[i] < rainfall[position])

position = i;

return position;

}

// Method

void swap(int i, int j)

{

// Swap the rainfalls

double temp = rainfall[i];

rainfall[i] = rainfall[j];

rainfall[j] = temp;

// Swap the months

String str = months[i];

months[i] = months[j];

months[j] = str;

}