AppDividend
Latest Code Tutorials

Selection Sort In Java Example | Java Selection Sort Program

0

Selection Sort In Java Example | Java Selection Sort Program is today’s topic. First of all, understand what do we mean by sorting? Sorting means to put all the elements in ascending order. The question that strikes our mind is that the first, what is the procedure involved in sorting through a process Selection Sort. Selection Sort is the process in which we repeatedly find the smallest element in the array from the unsorted subpart of the array.

#Selection Sort

The selection sort 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 algorithm maintains two subarrays in the given array.

1) The subarray, which is already sorted.
2) Remaining subarray which 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.

Selection Sort in Java

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

The left part is the sorted one, and the right part is the unsorted one. And in 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 that is 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 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 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 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}

Now 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 useful when the memory write is the 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

Finally, Selection Sort In Java Example | Java Selection Sort Program is over.

Leave A Reply

Your email address will not be published.

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