Java

Java Selection Sort

The lowest element comes first in the selection sort. Then, the beginning node is switched, and we repeat for the rest of the list. The selection sort in Java does not require any more space for sorting that involves repeatedly determining the smallest element and swapping it with the one which is already present in the suitable position. Additionally, we can determine the complexity of the selection sort by counting the number of loops. Since the selection sort uses two for-loop, the time complexity is O(n2).

Example 1:

The selection sort iterates over the elements in the specified unsorted array. The minimum element is selected and moved to the sorted subarray in each iteration of the selection sort. The following program is used for the selection sort to sort an array in ascending order:

The “AscendingSelectionSort” class is built in the Java program which is mentioned previously. This class is implemented with the void “sort” function where the integer array “MyArray” is passed a parameter. Inside the “sort” function, we decalre the “ArraySize” object to get the size of the array from the length method. Furthermore, we deploy the for-loop method which iterates the boundary of the unsorted array, one at a time.

The next step is to develop an object called “min” that locates the unsorted array element with the lowest value. The other for-loop is invoked to fetch the index position of the minimum element from the array. The for-loop iterate from “i+1” to the last element of an array. Next, we have an if-statement to verify whether the “MyArray[j]” is smaller than “MyArray[min]” or not. If so then, the minimum index will be incremented. Then, we apply the swapping algorithm by swapping the minimum value of the array with the first value. There, we have another function, the “PrintArray”, which is established to print the sorted array from the selection sort. We print the sorted array by iterating each element of the array through the for-loop.

In the end, we test the implementation of the selection sort inside the main() method. Here, we define the object “obj” for the “AscendingSelectionSort” class and also initialize the “MyArray” array with the integer elements. Then, we use the “Sort” function using that array as a parameter to sort the array, which was then printed on the console.

The selection sort technique is used to produce the following array which is sorted in ascending order:

Example 2:

The selection sort can also be used for the array which is not preset. The user first enters the size of the array. Then, it enters the element inside the array with the specified array.

In the previous program of Java, we defined the “UserDefinedSelectionSort” class. The class is defined with the “swapping” function and takes the “x[]”, “i” and “j” as parameters. The array elements are compared first and then swapped with the “temp” variable. After that, we have another function – “UserDefinedSelectionSort” – where the “x[]”array and the object size is defined as a parameter. This function is called with the nested for-loop. We first traversed the unsorted array from the first index to the last.

Then, we traverse the unsorted array from “i+1” to the last value of the array to get the minimum element from the unsorted array and update the minimum index. After that, we call the “swapping” function to swap the x[i] with the x[min_index]. Then, we have a main() method form where we take the input from the user by creating the object “input” and calling the system in the method. The “s” object denotes the length of the array which uses the nextInt() method to read the next token from the input value by the user. The array length is declared inside the array “x[]” and then obtained as the value for the array within the array size. The initial array is displayed first, then the sorted array from the selection sort method is traversed and displayed.

On the compilation of the previous code, the terminal first asked to enter the size of the array. After defining the size of the array, the user inputs the random elements. Then, the selection sort is performed. The initial unsorted array and the selection sorted array is displayed in the following:

Example 3:

Next, the selection sort is done on the singly linked list. The technique involves the swapping of the linked list node instead of the data inside the nodes.

In the previous program, we have a Java class “LinkedListSelectionSort” where we define another class, the “Node”. The “Node” class is declared with the “MyData” object and the node object, “next_node”. Then, we have a “swapNodes” function where the current node “curr_n1” is swapped with another current node “curr_n2” without swapping the node elements in the linked list. First, we made the “curr_n2” ahead and then adjust the links. After that, we swap the nodes with the temp variable.

There, we have another “SelectionSort” function that uses the recursive selection sort approach to sort the linked list. We figure out with the if-statement whether the linked list has the node. Then, we define the pointer node “min_node” for the minimum data value and the “prev_min” node pointer to have the previous data value of the node. The for-loop traverses all the nodes of the linked list and increments the minimum node and the previous node. Next, we apply the condition – if the min_node and the head node are different, we swap the min_node with the head node. The remaining linked list is sorted recursively by putting the “head.next_node” in the SelectionSort function.

Furthermore, we create the “SortNodes” function which verifies that the given linked list should not be empty and sort the list via the SelectionSort() function. Then, we have the next function which is “push” to add a node to the starting position of the linked list. We define the “NewNode” object to allocate the node and insert the data inside that node. After that, we link the head reference with the new node and reallocate the head reference to a new node. Next, we create a “DisplayList” function to print the linked list through the while loop.

We have a main() method where the linked list is initialized using the push method. The unsorted linked list elements will be printed. Then, we invoke the sortNodes() function which takes the head object as a parameter to perform the selection sort operation. The sorted linked list is printed by the DisplayList() method which also takes the “head” as an argument.

The original linked list is displayed. After that, the sorted linked list is printed in the following:

Conclusion

The selection sort essentially specifies where an element starts from the other elements. The selection sort in Java is applied when the small lists need to be sorted. It also impacts the rate of writing to memory, especially the flash memory. The core concept of using the selection sort in Java is to split an array into the sorted and unsorted sections and then sort the array using comparisons. The selection sorting examples are demonstrated with the default and the other case.

About the author

Saeed Raza

Hello geeks! I am here to guide you about your tech-related issues. My expertise revolves around Linux, Databases & Programming. Additionally, I am practicing law in Pakistan. Cheers to all of you.