Lab Assignment Report - Sorting User IDs

Objective

The objective of this lab assignment is to implement the Quicksort algorithm to sort user IDs in ascending order. The program reads user IDs from the user until the input "-1" is encountered, and then it sorts and displays the user IDs in ascending order.

Procedure

This lab assignment involves implementing the Quicksort algorithm in Java to sort a list of user IDs. The following components are crucial to the implementation:

partition Method

The partition method is responsible for partitioning the user IDs and selecting a pivot point for the Quicksort algorithm.

It picks the middle element as the pivot and compares values using two index variables, i and h, initialized to the left and right sides of the elements being sorted. It determines if a swap is necessary based on comparisons and returns the index of the last item in the low partition.

public static int partition(ArrayList 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 quality help now

            

                

	                			                               
                

                    

                                                    Bella Hamilton                                            
                    

                        
                        Verified writer
                    
                                        

                        
Proficient in: Technology
                    
                                    
            

            

                

                    

                        
                        
                        
                        
                         5 (234)
                    
                    

                        
“ Very organized ,I enjoyed and Loved every bit of our professional interaction ”
                    
                
            

            

                

                                            
                                            
                                            
                                    
                

                    +84 relevant experts are online
                
            

            Hire writer
        
    

get(midpoint);

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

	

		Get to Know The Price Estimate For Your Paper
	
	

		

			Topic
			
		
	
	

		

			
				Deadline: 10 days left
				

					
					
				
			
		
	
	

		

			Number of pages
			

				
					
				
				
				
					
				
			
		
	
	

		

			Email
			
			Invalid email
		
	
	

		

			
				
				
			
			

				By clicking “Check Writers’ Offers”, you agree to our terms of service and privacy policy. We’ll occasionally send you promo and account related email
			
		
		
"You must agree to out terms of services and privacy policy"
	
	

		Write my paper
        
You won’t be charged yet!
	

set(l, userIDs.get(h));
        userIDs.set(h, temp);
        l++;
        h--;
    }
}
}

quicksort Method

The quicksort method initiates the Quicksort algorithm. It serves as the entry point for sorting the user IDs. It first checks the base case, where there is only one or zero entries to sort, in which case the partition is already sorted. If not, it proceeds to partition the data within the array and recursively sorts the low and high partitions.

public static void quicksort(ArrayList 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);
}

Main Program

The main program reads user IDs from the user until the input "-1" is encountered. It stores the user IDs in an ArrayList and then calls the quicksort method to sort the IDs in ascending order. Finally, it prints the sorted user IDs one per line.

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

public class Lab4_1 {
public static void main(String[] args) {
Scanner scnr = new Scanner(System.in);
ArrayList userIDList = new ArrayList();
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));
    }
}
}

Example Run

Let's consider an example run of the program to demonstrate its functionality:

Please enter words (enter -1 to stop): kaylasimms
julia
myron1994
kaylajones
-1
julia
kaylajones
kaylasimms
myron1994

Conclusion

In conclusion, this lab assignment has successfully implemented the Quicksort algorithm in Java to sort user IDs in ascending order. The program efficiently partitions and sorts the user IDs and provides an organized list as output. It demonstrates the use of arrays, recursive algorithms, and string comparisons in Java.

References

1. Java ArrayList Documentation: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html