Can someone please explain the logic so i understand what is happening in the me
ID: 3918482 • Letter: C
Question
Can someone please explain the logic so i understand what is happening in the method
public static void sort(ArrayList<Integer> list) that i have below? Thanks.
Here is the problem with the solution :
/*
(Sort ArrayList) Write the following method that sorts an ArrayList of
numbers:
public static void sort(ArrayList<Integer> list)
Write a test program that prompts the user to enter 5 numbers, stores them in an
array list, and displays them in increasing order.
*/
import java.util.ArrayList;
import java.util.Scanner;
public class Exercise11_11 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
System.out.println("Enter 5 Integers : ");
int temp;
for (int i = 0; i < 5; i++) {
temp = scan.nextInt();
list.add(temp);
}
scan.close();
System.out.println("Here is your List : " + list);
sort(list);
System.out.println("Here is your list sorted : " + list);
}
public static void sort(ArrayList<Integer> list) {
for (int i = 0; i < list.size() - 1; i++) {
int currentMin = list.get(i);
int currentIndex = i;
for (int j = i + 1; j < list.size(); j++) {
if (currentMin > list.get(j)) {
currentMin = list.get(j);
currentIndex = j;
}
}
if (currentIndex != i) {
list.set(currentIndex, list.get(i));
list.set(i, currentMin);
}
}
}
}
Explanation / Answer
This program is a classic example of SELECTION SORT.
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Following example explains the above steps:
Please find below the code with detailed inline comments.
import java.util.ArrayList;
import java.util.Scanner;
public class Exercise11_11 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>(); // create an empty list of integers
System.out.println("Enter 5 Integers : "); // input 5 integers from user
int temp;
for (int i = 0; i < 5; i++) {
temp = scan.nextInt();
// add user inputted integer to the list
list.add(temp);
}
scan.close();
// display the list before sorting
System.out.println("Here is your List : " + list);
sort(list);
// display the list after sorting
System.out.println("Here is your list sorted : " + list);
}
public static void sort(ArrayList<Integer> list) {
// One by one move boundary of unsorted sublist
for (int i = 0; i < list.size() - 1; i++) {
// Find the current minimum element and minimum index in unsorted array
int currentMin = list.get(i); // stores the minimum element
int currentIndex = i; // stores the minimum index
// now loop through i+1 to list.size() to update the minimum element and minimum index
for (int j = i + 1; j < list.size(); j++) {
if (currentMin > list.get(j)) {
currentMin = list.get(j);
currentIndex = j;
}
}
// Swap the found minimum element with the first element
if (currentIndex != i) {
list.set(currentIndex, list.get(i));
list.set(i, currentMin);
}
}
}
}