7.11 LAB: Sorting user IDs Given a main() that reads user IDs (until -1), complete the quicksort() and partition() methods to sort the IDs in ascending order using the Quicksort algorithm, and output the sorted IDs one per line. Ex. If the input is: kaylasimms julia myron1994 kaylajones -1 the output is: julia kaylajones kaylasimms myron1994 import java.util.Scanner; import java.util.ArrayList; public class UserIDSorting { // TODO: Write the partitioning algorithm - pick the middle element as the // pivot, compare the values using two index variables l and h (low and high), // initialized to the left and right sides of the current elements being sorted, // and determine if a swap is necessary public static int partition(ArrayList userIDs, int i, int k) { } // TODO: Write the quicksort algorithm that recursively sorts the low and // high partitions public static void quicksort(ArrayList userIDs, int i, int k) { } public static void main(String[] args) { Scanner scnr = new Scanner(System.in); ArrayList userIDList = new ArrayList(); String userID; userID = scnr.next(); while (!userID.equals("-1")) { userIDList.add(userID); userID = scnr.next(); } // Initial call to quicksort quicksort(userIDList, 0, userIDList.size() - 1); for (int i = 0; i < userIDList.size(); ++i) { System.out.println(userIDList.get(i)); } } }
7.11 LAB: Sorting user IDs
Given a main() that reads user IDs (until -1), complete the quicksort() and partition() methods to sort the IDs in ascending order using the Quicksort
Ex. If the input is:
kaylasimms julia myron1994 kaylajones -1the output is:
julia kaylajones kaylasimms myron1994import java.util.Scanner;
import java.util.ArrayList;
public class UserIDSorting {
// TODO: Write the partitioning algorithm - pick the middle element as the
// pivot, compare the values using two index variables l and h (low and high),
// initialized to the left and right sides of the current elements being sorted,
// and determine if a swap is necessary
public static int partition(ArrayList<String> userIDs, int i, int k) {
}
// TODO: Write the quicksort algorithm that recursively sorts the low and
// high partitions
public static void quicksort(ArrayList<String> userIDs, int i, int k) {
}
public static void main(String[] args) {
Scanner scnr = new Scanner(System.in);
ArrayList<String> userIDList = new ArrayList<String>();
String userID;
userID = scnr.next();
while (!userID.equals("-1")) {
userIDList.add(userID);
userID = scnr.next();
}
// Initial call to quicksort
quicksort(userIDList, 0, userIDList.size() - 1);
for (int i = 0; i < userIDList.size(); ++i) {
System.out.println(userIDList.get(i));
}
}
}
Code:
import java.util.Scanner;
import java.util.ArrayList;
public class UserIDSorting {
// TODO: Write the partitioning algorithm - pick the middle element as the
// pivot, compare the values using two index variables l and h (low and high),
// initialized to the left and right sides of the current elements being sorted,
// and determine if a swap is necessary
public static int partition(ArrayList<String> userIDs, int i, int k) {// defining partition function
String pivot = userIDs.get(k);//pivot
int index = (i - 1);//index
for (int j = i; j < k; j++) {//loop for comparision
if (userIDs.get(j).compareTo(pivot) <= 0) {
index++;
String temp = userIDs.get(index);
userIDs.set(index, userIDs.get(j));
userIDs.set(j, temp);
}
}
String temp = userIDs.get(index+1);
userIDs.set(index+1, userIDs.get(k));
userIDs.set(k, temp);
return index + 1;
}
// TODO: Write the quicksort algorithm that recursively sorts the low and
// high partitions
public static void quicksort(ArrayList<String> userIDs, int i, int k) {
if (i < k) {
int pi = partition(userIDs, i, k);//calling partition
quicksort(userIDs, i, pi - 1);
quicksort(userIDs, pi + 1, k);
}
}
public static void main(String[] args) {//main method
Scanner scnr = new Scanner(System.in);//scanner class for taking user input
ArrayList<String> userIDList = new ArrayList<String>();//declaring array list for userId=D list
String userID;
userID = scnr.next();//reading user input
while (!userID.equals("-1")) {
userIDList.add(userID);
userID = scnr.next();
}
// Initial call to quicksort
quicksort(userIDList, 0, userIDList.size() - 1);
for (int i = 0; i < userIDList.size(); ++i) {
System.out.print(userIDList.get(i)+" ");//printing the required output
}
}
}
Code Screenshot:
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
