Question

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 

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) {

}

// 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));
}
}
}

Answer 1

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) {
      
      
       String piv = userIDs.get(k);
       int index = (i - 1);
       for (int j = i; j < k; j++) {

           if (userIDs.get(j).compareTo(piv) <= 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);

           quicksort(userIDs, i, pi - 1);
           quicksort(userIDs, pi + 1, 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));
       }
   }
}

===========================================================
SEE OUTPUT

Thanks, PLEASE UPVOTE if there is any concern.