Selection sort in java

Let’s learn selection sort in java.

Selection sort in java

In selection sort algorithm smallest element in unsorted array is shifted to its correct position in an array. The number of times sorting takes place will always be one less than the number of integer elements in an array.

To select lowest element we need to scan all “n” number of elements in an array. In selection sort comparing takes “n – 1” times and lastly swapping element to first position.

For comparisons, (n − 1) + (n − 2) + … + 2 + 1 = n(n − 1) / 2

Here in selection sort algorithm we need two subarrays, first subarray for sorted array and second subarray for unsorted array.

In selection sort, loop continues until integer elements from unsorted subarray are arranged in the ascending order in sorted subarray. Let’s see an example on selection sort.

public class SelectionSortInJava
{
   void toSort(int[] arrNum)
   {
      int number = arrNum.length;
      for(int a = 0; a < number - 1; a++)
      {
         // finding minimum element
         int minimum = a;
         for(int b = a + 1; b < number; b++)
         {
            if(arrNum[b] < arrNum[minimum])
            {
               minimum = b;
            }
         }
         // swapping minimum element with first element
         int temp = arrNum[minimum];
         arrNum[minimum] = arrNum[a];
         arrNum[a] = temp;
      }
   }
   // printing array
   void displayArray(int[] arrPrint)
   {
      int num = arrPrint.length;
      for(int a = 0; a < num; ++a)
      {
         System.out.print(arrPrint[a] + " ");
      }
      System.out.println();
   }
   public static void main(String[] args)
   {
      SelectionSortInJava obj = new SelectionSortInJava();
      int[] arrInput = {5, 4, -3, 2, -1};
      obj.toSort(arrInput);
      System.out.println("After sorting : ");
      obj.displayArray(arrInput);
   }
}

Output:

Selection sort in java is considered as one of the simplest algorithms. But not the fastest sorting algorithm.

Because outer “for loop” places the value to correct position while inner “for loop” finds next largest or smallest element. Selection sort is useful for small data sets.

Time complexity: O(n²) because of outer and inner “for loops”.

Auxiliary space: O(1)

Selection sort in descending order

Let’s learn selection sort in descending order.

public class SelectionSortDemo 
{
   public static void selectionSortDescending(int[] arrNumber)
   {
      int a, b, first, temp; 
      for(a = arrNumber.length - 1; a > 0; a--) 
      {
         first = 0;
         for(b = 1; b <= a; b++)
         {
            if(arrNumber[b] < arrNumber[first])
            {
               first = b;
            }
         }
         temp = arrNumber[first];
         arrNumber[first] = arrNumber[a];
         arrNumber[a] = temp; 
      }          
   }
   void displayArray(int[] arrPrint)
   {
      int num = arrPrint.length;
      for(int a = 0; a < num; ++a)
      {
         System.out.print(arrPrint[a] + " ");
      }
      System.out.println();
   }
   public static void main(String[] args) 
   {
      SelectionSortDemo obj = new SelectionSortDemo();
      int[] arrInput = {10, 40, 30, 20, 50};
      selectionSortDescending(arrInput);
      System.out.println("Selection sort in descending order: ");
      obj.displayArray(arrInput);
   }
}

Output:

Selection sort in descending order: 50 40 30 20 10