COMP 182: Lab Assignment 4.1 - Sorting User IDs

import java . util .*; public class Lab4_1 { public static void main ( String [] args ) { Scanner scnr = new Scanner ( System . in ); ArrayList < String > userIDList = new ArrayList < String >(); String userID ; System . out . print ( "Please enter words (enter -1 to stop): " ); 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 )); } } public static void quicksort ( ArrayList < String > userIDs , int i , int k ) { // Base case: If there are 1 or zero entries to sort, partition is already sorted if ( k - i <= 0 ) return ; // Partition the data within the array. Value j returned from partitioning is location of last item in low partition. int j = partition ( userIDs , i , k ); // Recursively sort low partition (i to j) and high partition (j + 1 to k) quicksort ( userIDs , i , j ); quicksort ( userIDs , j + 1 , k ); } public static int partition ( ArrayList < String > userIDs , int i , int k ) { int l = i ; int h = k ; int midpoint ; String pivot = "" ; String temp = "" ; // Pick middle element as pivot midpoint = ( l + h ) / 2 ; pivot = userIDs . get ( midpoint ); while ( true ) { // Increment l while numbers[l] < pivot while ( userIDs . get ( l ). compareTo ( pivot ) < 0 ) l ++; // Decrement h while pivot < numbers[h]

while ( pivot . compareTo ( userIDs . get ( h )) < 0 ) h --; // If there are zero or one item remaining, all numbers are partitioned. Return h if ( l >= h ) return h ; else { // Swap numbers[l] and numbers[h], // update l and h temp = userIDs . get ( l ); userIDs . set ( l , userIDs . get ( h )); userIDs . set ( h , temp ); l ++; h --; } } } }