articles

Home / DeveloperSection / Articles / Selection Sort Implementation in Java: Programming and Analysis (Part-2)

Selection Sort Implementation in Java: Programming and Analysis (Part-2)

Ailsa Singh1436 10-May-2016

Previously we have seen how selection sort works and sorts the following array:

numArray

56

47

78

64

14

32

51

· We will make count of these passes by assuming the variable h go from 0 to 5.In this  selection sorting procedure, we made six passes.

·   On each pass, we then find the smallest number between the positions h to 6.

·   Suppose that the smallest number is in position small,  so we swap the numbers in positions h and small.

In general, for an array of size n, we  need to make n-1 passes. In this example, we sorted 7 numbers in 6 passes.

Pseudo code:

The following is a pseudo code outline of the algorithm for sorting num[0..n-1]:

for h = 0 to n – 2 

       s = position of smallest number from numArray[h] to numArray[n-1] 
         swap numArray[h] and numArray[s] 

end for
 selectionSort Method:

We can implement this algorithm as described here, using the generic parameter list:

public static void selectionSort(int[] numArray, int lo, int hi)
 {
           //sort numArray[lo] to numArray[hi] in ascending order
               for (int h = lo; h < hi; h++) {                         int small = getSmallest(numArray, h, hi);                       swap(numArray, h, small);
              }
}

 The two statements within the for loop could be substituted by the following statement:

         swap(numArray, h, getSmallest(numArray, h, hi));

getSmallest Method:

We can implement getSmallest as described here:

public static int getSmallest(int numArray[], int lo, int hi)
 {
       //return location of smallest from numArray[lo..hi]
         int small = lo;
         for (int h = lo + 1; h <= hi; h++){
                       if (numArray[h] < numArray[small])
                            small = h;
        }
         return small;
}
 
swap Method:

We can write swap as follows:

public static void swap(int numArray[], int i, int j)
 {
         //swap elements numArray[i] and numArray[j]
             int temp = numArray[i];              numArray[i] = numArray[j];
             numArray[j] = temp;
}
 Test Class:

To test whether selectionSort works properly, we write test Program to test implementations. Only main is shown. To complete the program, just add selectionSort, getSmallest, and swap methods as explained above.

import java.util.*;

public class SelectSortTest {
          final static int MaxNum = 10;
          public static void main(String[] args) {
                   Scanner in = new Scanner(System.in);
                   int[] numArray = new int[MaxNum];
                   System.out.printf("Type up to %d numbers followed by 0\n", MaxNum);                    int n = 0;
                   int v = in.nextInt();
                    while (v != 0 && n < MaxNum) {
                             numArray[n++] = v;
                             v = in.nextInt();
                   }
                   if (v != 0) {
                             System.out.printf("\nMore than %d numbers entered\n", MaxNum);                              System.out.printf("First %d used\n", MaxNum);
                   }
                   if (n == 0) {
                             System.out.printf("\nNo numbers supplied\n");
                             System.exit(1);

                   }
                   // n numbers are stored from numArray[0] to numArray[n-1]
                   selectionSort(numArray, 0, n - 1);
                   System.out.printf("\nThe sorted numbers are\n");
                   for (v = 0; v < n; v++)
                             System.out.printf("%d ", numArray[v]);
                   System.out.printf("\n");
          } // end of method main
                   // selectionSort, getSmallest and swap go here
} // end of class SelectSortTest

 The program requests maximum of 10 integer numbers (as defined by MaxNum), stores them in the array num, calls selectionSort, and then prints the sorted list. 

Analysis of Selection Sort

To determine the smallest of k items, we make k-1 comparisons. On the very  first pass, we make n-1 comparisons to determine the smallest of n items. On the second pass, we make n-2 comparisons to determine the smallest of n-1 items. And so on, until the last pass where we make one comparison to determine the smaller of two items. In particular, on the jth pass, we make n-j comparisons to determine the smallest of n-j+1 items. Hence, we have this expression:

Total number of comparisons = 1 + 2 + …+ n-1 = ½ n(n-1) » ½ n2

We can say selection sort is of order O(n2) (“big O n squared”). The constant ½ is not important in “big O” notation because, as n gets very big, the constant becomes insignificant.

On every pass, we swap two items by using three assignments. Because we make n-1 passes, this gives us 3(n-1) assignments in all. In “big O” notation, we can say that the number of assignments is of order O(n). The constants 3 and 1 are not important as n gets bigger.

Does this selection sort perform any better if there is order in the data? No. If we work through the algorithm, we will see that the method is oblivious to order in the data.

It will make the exactly same number of comparisons every time, regardless of the data.

As we will see, several sorting methods needs extra array storage to implement them.Note that selection sort is performed “in place” in the given array and doesn’t need additional storage.


Updated 30-Nov-2017

Leave Comment

Comments

Liked By