CC-5 : Implement Selection Sort Algorithm.

Description:

Selection Sort works by building the sorted array by finding smallest element of the unsorted array to its correct position. Then it iterates through rest of elements and finds smallest element and places it to its correct sorted position. These steps are repeated till all elements are placed at their corrected position. Given an input array, sort its elements using Selection Sort

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Sorted Array: 1, 3, 4, 20, 33, 62, 97, 122, 124,

Pseudocode:

selectionSort(nums[]):

Integer array named nums is received as input parameter.

Iterate through using for loop with iidx as iteration variable and values of iidx ranging from 0 to nums.length-1:

Initialize int variable smallestNumIdx. We will use this variable to store values smallest element of the array in current iteration, that we will move to its correct sorted position.

Iterate through using for loop with jidx as iteration variable and values of jidx ranging from iidx+1 to nums.length:

If (nums[jidx]< nums[smallestNumIdx] then:

Set smallestNumIdx to jidx.

If smallestNumIdx != iidx, then swap elements at position smallestNumIdx and iidx. This way smallest element in each iteration will move to its sorted position.

The element of nums array have been sorted now using Selection Sort, so return nums array from the method.

Code:

public int[] selectionSort(int[] nums){
	for (int iidx=0;iidx < nums.length-1;iidx++) {
		int smallestNumIdx=iidx;
		for (int jidx=iidx+1;jidx < nums.length;jidx++) {
			if (nums[jidx]< nums[smallestNumIdx]) {
				smallestNumIdx=jidx;
			}			
		}
		if (smallestNumIdx != iidx) {
			int swap=nums[iidx];
			nums[iidx]=nums[smallestNumIdx];
			nums[smallestNumIdx]=swap;
		}
	}
	return nums;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SortSelectionSort {

public int[] selectionSort(int[] nums){
	for (int iidx=0;iidx < nums.length-1;iidx++) {
		int smallestNumIdx=iidx;
		for (int jidx=iidx+1;jidx < nums.length;jidx++) {
			if (nums[jidx]< nums[smallestNumIdx]) {
				smallestNumIdx=jidx;
			}			
		}
		if (smallestNumIdx != iidx) {
			int swap=nums[iidx];
			nums[iidx]=nums[smallestNumIdx];
			nums[smallestNumIdx]=swap;
		}
	}
	return nums;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	
	SortSelectionSort sort=new SortSelectionSort();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	System.out.println("\nSorted Array:");
	retVal=sort.selectionSort(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}