Need help on Arraylist quicksort and partition

Question

Instructions:

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.

Sample Input:

kaylasimms 
julia 
myron1994 
kaylajones 
-1

Sample output:

julia 
kaylajones
kaylasimms
myron1994 

I ran and build my code and it shows no error so I'm guessing there is something wrong with the way I'm doing it. The output only shows the Strings in the exact order I entered them but without the -1.

My 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 void main(String[] args) {
      Scanner scnr = new Scanner(System.in);

      ArrayList<String> userIDList = new ArrayList<String>();

      String userID = "";

      while (true) {
         userID = scnr.next();
         if(userID.equals("-1")){
            break;
         }
         userIDList.add(userID);
      }

      // Initial call to quicksort
      quicksort(userIDList, 0, userIDList.size()-1);

      for (int i = 0; i < userIDList.size(); ++i) {
         System.out.println(userIDList.get(i));
      }
   }

public static int partition(ArrayList<String> values, int lowIndex, int highIndex) {
   // Pick middle element as pivot
   String pivot = values.get((lowIndex + (highIndex - lowIndex) / 2));
   
   boolean done = false;
   while (!done) {
      // Increment lowIndex while numbers[lowIndex] < pivot
      while (values.get(lowIndex).compareTo(pivot) < 0) {
         lowIndex += 1;
      }
      
      // Decrement highIndex while pivot < numbers[highIndex]
      while (values.get(highIndex).compareTo(pivot) > 0) {
         highIndex -= 1;
      }
      
      // If zero or one elements remain, then all numbers are 
      // partitioned. Return highIndex.
      if (lowIndex >= highIndex) {
         done = true;
      }
      else {
         // Swap numbers[lowIndex] and numbers[highIndex]
         String temp = values.get(lowIndex);
         values.set(lowIndex,values.get(highIndex));
         values.set(highIndex,temp);

         // Update lowIndex and highIndex
         lowIndex += 1;
         highIndex -= 1;
      }
   }
   
   return highIndex;
}

public static void quicksort(ArrayList<String> numbers, int lowIndex, int highIndex) {
   // Base case: If the partition size is 1 or zero 
   // elements, then the partition is already sorted
   if (lowIndex >= highIndex) {
      return;
   }
   
   // Partition the data within the array. Value lowEndIndex 
   // returned from partitioning is the index of the low 
   // partition's last element.
   int lowEndIndex = partition(numbers, lowIndex, highIndex);
   
   // Recursively sort low partition (lowIndex to lowEndIndex) 
   // and high partition (lowEndIndex + 1 to highIndex)
   quicksort(numbers, lowIndex, lowEndIndex);
   quicksort(numbers, lowEndIndex + 1, highIndex);
}  


}

Answer 1

At some point you need to actually swap the values, right? You calculate indexes, but you never do anything like numbers.set(index, value) ... it should be no surprise that the result is identical to the input.

Answer 2

import java.util.Scanner;
import java.util.ArrayList;

public class UserIDSorting {

   public static void main(String[] args) {
      Scanner scnr = new Scanner(System.in);

      ArrayList<String> userIDList = new ArrayList<String>();

      String userID = "";

      while (true) {
         userID = scnr.next();
         if(userID.equals("-1")){
            break;
         }
         userIDList.add(userID);
      }

      // Initial call to quicksort
      quicksort(userIDList, 0, userIDList.size()-1);

      for (int i = 0; i < userIDList.size(); ++i) {
         System.out.println(userIDList.get(i));
      }
   }

public static int partition(ArrayList<String> values, int lowIndex, int highIndex) {
   // Pick middle element as pivot
   String pivot = values.get((lowIndex + (highIndex - lowIndex) / 2));
   
   boolean done = false;
   while (!done) {
      // Increment lowIndex while numbers[lowIndex] < pivot
      while (values.get(lowIndex).compareTo(pivot) < 0) {
         lowIndex += 1;
      }
      
      // Decrement highIndex while pivot < numbers[highIndex]
      while (values.get(highIndex).compareTo(pivot) > 0) {
         highIndex -= 1;
      }
      
      // If zero or one elements remain, then all numbers are 
      // partitioned. Return highIndex.
      if (lowIndex >= highIndex) {
         done = true;
      }
      else {
         // Swap numbers[lowIndex] and numbers[highIndex]
         String temp = values.get(lowIndex);
         values.set(lowIndex,values.get(highIndex));
         values.set(highIndex,temp);

         // Update lowIndex and highIndex
         lowIndex += 1;
         highIndex -= 1;
      }
   }
   
   return highIndex;
}

public static void quicksort(ArrayList<String> numbers, int lowIndex, int highIndex) {
   // Base case: If the partition size is 1 or zero 
   // elements, then the partition is already sorted
   if (lowIndex >= highIndex) {
      return;
   }
   
   // Partition the data within the array. Value lowEndIndex 
   // returned from partitioning is the index of the low 
   // partition's last element.
   int lowEndIndex = partition(numbers, lowIndex, highIndex);
   
   // Recursively sort low partition (lowIndex to lowEndIndex) 
   // and high partition (lowEndIndex + 1 to highIndex)
   quicksort(numbers, lowIndex, lowEndIndex);
   quicksort(numbers, lowEndIndex + 1, highIndex);
}  


}