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.

Advantages of Sorting:

·   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.