Computer Science: Quick Sort Program and Reflection

This assignment presents a Java implementation of the quick sort algorithm, a fundamental concept in computer science. The program, written in Java, demonstrates the use of data structures such as queues and employs the quick sort algorithm for sorting data based on different criteria like last name and age. The assignment includes the complete source code for the program, along with screenshots of the program's execution. Furthermore, the assignment includes a 'Lessons Learned Reflection' section, which offers insights into the key takeaways from the course, including the importance of sorting algorithms, big-Oh notation, and the Java collections framework, and their applications in software development. The document also provides a detailed conclusion summarizing the significance of algorithms and data structures in building efficient and robust applications, and concludes with a list of relevant references.

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