Selection sort, algorithm

In this code fragment, assume that: I, J, and temp are declared as type INTEGER, MAX, is a CONST equal to ten, the size therefore of the array test_array.

Believe it or not, that is all the code required to sort through an array of any size.
The initial condition of the array can be seen below

Figure 2 - Sorting arrays : Before sorting

The first step in selection sort is to compare the values in the elements indicated by the subscript values of both I, and J. If the value in test_array[J] is not less than the value in test_array[I] then the counter J is incremented by one, while the value of I remains at one.
The control variable J, is incremented until the value in test_array[J] is less than the value in test_array[I], this brings us to the performance of the first swapping action, see below.

Figure 3 - Sorting : Step 1

Once a value is found in test_array[J] to be less than that value in test_array[I], the first swap can occur. There are three steps in this operation.

• The swap algorithm:
  Copy the contents of test_array[J] into the temp variable.
  Copy the contents of test_array[I] into test_array[J].
  Copy the contents of temp into test_array[I].

Note:- The type of temp must be the same as the elements of the array. If the array is of the type INTEGER, then temp must be an INTEGER, but if its type is a record structure then temp must also be a record structure. The result of the first swap is shown below.

Figure 4 - Sorting : Step 2

The counter I is still equal to one, while the counter J is again incremented until the value in test_array[J] is found to be less than that in test_array[I]. This next occurs when J = 6, and the value in test_array[J] is two - see below.

Figure 5 - Sorting : Step 3

The result of the this swap is shown below.

Figure 6 - Sorting : Step 4

By now you can see that the value contained in test_array[I] is the lowest value in the whole array, but J continues to be incremented until it reaches the termination value of the for loop, namely when J = 10, in this case.
The sorting algorithm then increments I to two, in the outer FOR loop and the whole cycle starts over.

Figure 7 - Sorting : Step 5

Note:- Before the second FOR loop is entered each time, the counter I is set first, then the counter J takes that value plus one, so that J will always be just in front of I at the beginning of each cycle. After this sorting, there is a drastic reduction of the not in array time search time, since the search can be stopped when the position where the searched for value should be, is passed. For instance, if you were searching a library database for the author name 'Fitzgerald', and you had reached the element which contained 'Hemingway', then you know, because the array is sorted, that there is no possibility of an entry for 'Fitzgerald' being further on in the array so you can stop the search. The next program uses this example and sort algorithm, and steps through the sorting process, on the screen.

Program 4

Now you can sort an array you can add this algorithm before a search algorithm in any program, and so reduce the not in array time.
Some examples of average search times, through a 200,000 element array, assuming a random distribution of values:

The not in array time

Unsorted linear search: 55-60 seconds average.
Sorted linear search: 25-30, roughly half.

I suppose you can see a huge improvement in the time it takes the program to report to the user or to the program that the searched for data item is not in the array. This is important, because sorted or unsorted, in an array with a normal distribution of values, the found in array time is roughly the same, because sometimes the search will have to run all the way to the end of the array, and sometimes the value will be found at the beginning of the array.

Date: 2016-03-03; view: 827