Sorting:

Sorting is the process by which a set of values are arranged in ascending or descending order. There are various reasons to sort. Sometimes we sort in order to produce more effective and readable output (for instance, to produce an alphabetical ordered list of names). A professors may need to sort his candidates in order by name or by average score.

·   If we have a very large set of values and we want to determine duplicates, we can easily do so by sorting; the repeated values will come together in the sorted list.

·   Another advantage of sorting is that many operations can be performed quicker and more efficiently with sorted data. For instance, if data is sorted, it is possible to search it using binary search—this is much  more effective and faster than using a sequential search.

·   Also, merging two indidvidual lists of items can be done much faster than if the lists were unsorted.

Selection Sort:

Consider the following list of numbers stored in a Java array, numArray:

numArray

 56 47 78 64 14 32 51

0               1            2            3          4             5            6

Sorting numArray in ascending order using selection sort proceeds as follows:

1st pass

·   Find the smallest number in the entire list, from positions 0 to 6; the smallest is 14, found in position 4.

·  Interchange the numbers in positions 0 and 4. This gives us the following:

numArray

 14 47 78 64 56 32 51

0               1            2            3          4             5            6

2nd Pass:

·    Find the smallest number in positions 1 to 6; the smallest is 32, found in position 5.

·    Interchange the numbers in positions 1 and 5. This gives us the following:

numArray

 14 32 78 64 56 47 51

0               1            2            3          4             5            6

3rd Pass

·    Find the smallest number in positions 2 to 6; the smallest is 47, found in position 5.

·    Interchange the numbers in positions 2 and 5. This gives us the following:

numArray

 14 32 47 64 56 78 51

0               1            2            3          4             5            6

4th Pass

·    Find the smallest number in positions 3 to 6; the smallest is 51, found in position 6.

·    Interchange the numbers in positions 3 and 6. This gives us the following:

numArray

 14 32 47 51 56 78 64

0               1            2            3          4             5            6

5th Pass:

·    Find the smallest number in positions 4 to 6; the smallest is 56, found in position 4.

·    Interchange the numbers in positions 4 and 4. This gives us the following:

numArray

 14 32 47 51 56 78 64

0               1            2            3          4             5            6

6th Pass:

·   Find the smallest number in positions 5 to 6; the smallest is 64, found in position 6.

·  Interchange the numbers in positions 5 and 6. This gives us the following:

numArray

 14 32 47 51 56 64 78

0               1            2            3          4             5            6

The array is now completely sorted. Note that once the sixth largest (64) has been placed in its final position (5), the largest (78) would automatically be in the last position (6).

Next, we implement this approach using java and do the analysis for Selection sort, which we see in the next part.

Modified On Dec-16-2017 03:43:08 AM