Lab Assignment Report - Sorting User IDs

Categories: Technology

Report, Pages 3 (619 words)

Views

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.

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!

Don't use plagiarized sources. Get your custom paper on

“ Lab Assignment Report – Sorting User IDs ”

Get high-quality paper

NEW! smart matching with writer

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(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.


    
        
            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
        
    

 Return h if (l >= h) return h;
    else {
        // Swap userIDs[l] and userIDs[h], update l and h
        temp = userIDs.get(l);
        userIDs.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.