How to implement Selection sort in Java
Selection sort is an in-place sorting algorithm; it does not require any extra space apart from the given array. The array will be divided into two parts: sorted and unsorted.
In our example, the sorted part comes before the unsorted part; however, it may be the opposite with some slight changes.
The algorithm works as follows:
- Initially, the whole array is unsorted.
- Find the minimum of the unsorted part and swap it with the first element.
- Now, consider the minimum number chosen in the previous step as part of the sorted array. The size of the sorted part grows this way.
- Continue steps one through three until there are no elements left in the un-sorted part.
Given an array, we need to sort it using Selection sort. Hence, we must select the smallest element in the array.
1 of 8
Implementation
class SelectionSort {public static void main(String[] args){SelectionSort ss = new SelectionSort();int[] arr = {2,1,0,8,-4};System.out.println("Original Array:");ss.printArr(arr);arr = ss.sort(arr);System.out.println("\nSorted Array:");ss.printArr(arr);}int[] sort(int[] arr){int min, minIndex, temp;// 'start' is the point where 'unsorted' array beginsfor(int start = 0; start < arr.length - 1; start++){// Finding the minimummin = arr[start];minIndex = start;for(int i = start + 1; i < arr.length; i++){if(arr[i] < min){min = arr[i];minIndex = i;}}// Swap the minimum with the first elementtemp = min;arr[minIndex] = arr[start];arr[start] = temp;}return arr;}void printArr(int[] arr){for(int i = 0; i < arr.length; i++)System.out.print(arr[i] + " ");}}
Copyright ©2024 Educative, Inc. All rights reserved
TRENDING TOPICS
