AppDividend
Latest Code Tutorials

Selection Sort in Java: Everything You Need to Know

Sorting means putting all the elements in ascending order. The question that strikes our mind is the first, what is the procedure involved in sorting through a Selection Sort process. Selection Sort is when we repeatedly find the smallest element in the array from the unsorted subpart of the array.

Selection Sort in Java

The selection sort in the java algorithm sorts the array by repeatedly finding a minimum item (considering the ascending order) from an unsorted part and putting it at the beginning of the array.

The selection sort maintains two subarrays in the given array.

1) The subarray, which is already sorted.
2) The remaining subarray is unsorted and about to be sorted.

In every iteration of the selection sort, the minimum item (considering ascending order) from an unsorted subarray is picked and moved to a sorted subarray.

In the selection sort, we have to maintain two subparts: the left and the right.

The left part is the sorted one, and the right part is the unsorted one. And every time, the smallest element from the sorted get detached from the unsorted part and included in the sorted part list.

Algorithm of Selection Sort In Java

See the following algorithm.

Selection(A,N)
Step1: Repeat step 2 and 3 for (k=0;k<N-1;k++)
Step2: Call MINIMUM(A,K,N,LOC)
Step3: Swap A[K] and A[LOC]
Step4: Exit

MINIMUM(A,K,N,LOC)
Step1: Set min=A[K] and LOC=K
Step2: Repeat step 3 and 4 for(i=k;i<N;i++)
Step3: if min>a[i]
Step4: set min=a[i] and LOC=i
Step5: Return LOC

Let’s take an example:

Suppose we have an array={ 11,4,13,8,10,7}

Step: 1

Select the minimum element in the given array.

That is 4, and swap it with the first element of the unsorted part 11.

The array will become {4,11,13,8.10,7}

In this array, now 4 is the only element present in the sorted part, and the remaining elements are present in the unsorted part.

Step: 2

Select the minimum element in the unsorted part that is 7 and swaps it with 11 that is the first element in the unsorted part, and the array will become {4, 7,13,8,10,11}

Now there is an increment in the sorted list and a decrement in the unsorted list of the array.

Step: 3

Then again, select the minimum element in the unsorted part that is 8 and swap it with 13 that is the first element in the unsorted part, and the array will become {4, 7, 8, 13,10,11}

Now there is an increment in the sorted list and a decrement in the unsorted list of the array.

Step: 4

Similarly, select the minimum element in the unsorted part that is 10 and swaps it with 13 that is the first element in the unsorted part, and the array will become {4, 7, 8, 10,13,11}

Now there is an increment in the sorted list and a decrement in the unsorted list of the array.

Step: 5

Then again, select the minimum element in the unsorted part that is 11 and swap it with 13 that is the first element in the unsorted part, and the array will become {4, 7, 8, 10,11,13}

The whole array becomes sorted, and there is nothing in the unsorted part.

Time Complexity of Selection Sort

O(n2) as there are two nested loops.

Auxiliary Space

O(1). The good thing about the selection sort is it never makes more than O(n) swaps and can be helpful when memory writing is a costly operation.

Java Program of Selection Sort

See the following program.

class Selection {
  void sort(int ar[]) {
    int n = ar.length;
    for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
        if (ar[j] < ar[min])
          min = j;
      }
      int t = ar[min];
      ar[min] = ar[i];
      ar[i] = t;
    }
  }

  public static void main(String args[]) {
    Selection ss = new Selection();
    int ar[] = { 11, 4, 13, 8, 10, 7 };
    ss.sort(ar);
    int n = ar.length;
    System.out.println("Array after Selection Sort: ");
    for (int i = 0; i < n; ++i)
      System.out.print(ar[i] + " ");
    System.out.println();
  }
}

See the following output.

Selection Sort In Java Example

That’s it for this tutorial.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.