Quick Sort Assignment: Data Structures and Algorithms

This assignment delves into the implementation of the Quick Sort algorithm in Java, focusing on data structures and algorithm design. The student provides the Person and Queue classes, along with a MainClass to demonstrate the sorting functionality. The program takes user input for person details (first name, last name, and age), enqueues them, and then sorts the queue by last name and age. The assignment includes code snippets, screenshots of the program's execution, and a 'Lessons Learned Reflection' section summarizing key concepts from the course, such as sorting algorithms, Big-Oh notation, and the Java Collections Framework. The reflection emphasizes the importance of algorithm selection, time and space complexity, and efficient use of data structures for robust application development. The assignment concludes by highlighting the significance of algorithms and data structures in application performance and efficiency.

Running head: Quick Sort 1
Assignment
Student
Course
Instructor
Date

QUICK SORT 2
Quick Sort
Java is one of the most popular and widely used programming languages. It is also a
platform which is used by various applications to develop and run programs written in any
programming language. Java provides many important features like speed, platform
independence, security, and so on. Java is widely used to develop and run web applications,
scientific supercomputers, gaming consoles, cell phones, and various other areas of the internet.
(GeeksforGeeks, 2019)
A data structure is a method for storing and organizing data on a computer system so that
it can be used easily and efficiently. Furthermore, it is a specialized format by which the data can
be stored, processed, and retrieved. A data structure is usually selected or designed for the
purpose of working on it with algorithms. Therefore, these are very essential for managing large
amounts of data, such as information kept in databases. (javatpoint, 2019)
However, quick sort is one of the most efficient sorting algorithms and it is based on a
divide and conquer algorithm. The input array is divided into smaller arrays in each step. The
name of this algorithm itself denotes that it can sort a list of data elements considerably faster as
compared to the other sorting algorithms. (InterviewBit, 2019)
A pivot element is chosen in quick sort and the left side of the pivot contains all the
elements that are less than the pivot element whereas the right side will contain all the elements
greater than the pivot component. (HackerEarth, 2019)
Person.java Program

QUICK SORT 3
public class Person {
private String firstName;
private String lastName;
private int age;
public Person(String firstName, String lastName, int age) {
super();
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public int getAge() {
return age;

QUICK SORT 4
}
@Override
public String toString() {
return firstName +" "+ lastName + " [" + age + " years]";
}
}
Queue.java programming
import java.util.ArrayList;
import java.util.List;
public class Queue {
private Person[] queue;
public Queue()
{
this.queue=new Person[0];
}

QUICK SORT 5
public void enque(Person person)
{
increaseSize();
this.queue[this.queue.length-1]=person;
}
public boolean isEmpty()
{
return this.queue.length==0;
}
public Person deque()
{
if(isEmpty())
return null;
Person p = this.queue[0];
decreaseSize();
return p;

QUICK SORT 6
}
private void increaseSize()
{
Person[] temp=new Person[this.queue.length+1];
System.arraycopy(queue, 0, temp, 0, this.queue.length);
this.queue=temp;
}
private void decreaseSize()
{
Person[] temp=new Person[this.queue.length-1];
System.arraycopy(queue, 0, temp, 1, this.queue.length-1);
this.queue=temp;
}
public List<Person> getSortedByLastName()
{
sort(queue, 0, queue.length-1, false);
return returnAsList();

QUICK SORT 7
}
public List<Person> returnAsList()
{
List<Person> result=new ArrayList<Person>();
for(int i=0;i<queue.length;i++)
result.add(queue[i]);
return result;
}
public List<Person> getSortedByAge()
{
sort(queue, 0, queue.length-1, true);
return returnAsList();
}
private int partition(Person arr[], int low, int high, boolean byAge)

QUICK SORT 8
{
Person pivot = arr[high];
int i = (low-1);
for (int j=low; j<high; j++)
{
boolean flag=byAge ? arr[j].getAge() > pivot.getAge() :
arr[j].getLastName().compareTo(pivot.getLastName())>0;
if (flag)
{
i++;
swap(arr, i, j);
}
}
swap(arr,i+1,high);
return i+1;
}
private void sort(Person arr[], int low, int high,boolean byAge)

QUICK SORT 9
{
if (low < high)
{
int pivot = partition(arr, low, high,byAge);
sort(arr, low, pivot-1, byAge);
sort(arr, pivot+1, high,byAge);
}
}
private void swap(Person arr[], int i, int j)
{
Person temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
MainClass.java program

QUICK SORT 10
import java.util.List;
import java.util.Scanner;
public class MainClass {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
Queue queue=new Queue();
for(int i=0;i<5;i++)
{
System.out.println("Enter details for person "+(i+1)+": ");
System.out.print("First name: ");
String fName=sc.nextLine();
System.out.print("Last name: ");
String lName=sc.nextLine();
System.out.print("Age: ");
int age=Integer.parseInt(sc.nextLine());
Person p = new Person(fName, lName, age);
queue.enque(p);

QUICK SORT 11
System.out.println("Queue after inserting person "+(i+1)+": ");
printQueue(queue.returnAsList());
}
System.out.println("Queue in Descending order by last name");
printQueue(queue.getSortedByLastName());
System.out.println("Queue in Descending order by Age");
printQueue(queue.getSortedByAge());
sc.close();
}
private static void printQueue(List<Person> pList) {
for(Person p :pList)
System.out.println(p);
System.out.println();

QUICK SORT 12
}
}
Screenshot of The Sample Program
Figure 1