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

QUICK SORT 13
Figure 2
Lessons Learned Reflection
The computer science course taught a lot of things. For instance, I learned that sorting
algorithms are a very important part of the programming world and the use of various sorting
algorithms like radix sort and quick sort. Furthermore, sorting algorithms are used to rearrange
an array according to the given comparison criteria. The sorting algorithm for a problem is
usually selected according to the inputs and each sorting algorithm has its use case.
(GeeksforGeeks, 2019)
Another major topic that was learnt in this course is big-Oh notation. Multiple algorithms
can be used in any programming language to solve a problem. However, the Big-Oh notation
defines an upper bound of the algorithm. It can be used to measure the time complexity and the

QUICK SORT 14
space complexity of an algorithm. It is widely used to measure the performance of an algorithm
as it provides the worst-case complexity of the algorithm. (GeeksforGeeks, 2019)
Furthermore, the collections framework is a very important part of Java that provides an
architecture to store and to manipulate groups of objects. It allows to perform various operations
like search, sort, add, remove, and so on. Therefore, this coursework taught me about the
collection framework, various types of java collections available, efficient use, and utilization of
these collections. (javatpoint, 2019)
The last important aspect taught in this coursework is on algorithms. An algorithm refers
to a procedure or formula for solving a problem. There are various ways or algorithms to solve a
problem, but choosing the most efficient algorithm for any problem is very important. An
algorithm refers to a small procedure to solve the recurrent problem. In this coursework, we
worked on various algorithms like radix sort, quick sort, postfix evaluation, queue
implementation, and so on. (WhatIs, 2019)

QUICK SORT 15
Conclusion
The algorithms and data structure are the most important part of an application. The
whole application’s performance and efficiency depends on the algorithm and the data structure
used in that application. All the work completed in this course teaches about the proper use of
algorithm, data structure and collections. A n intelligent use of all these aspects will give
robustness and efficiency to any application.

QUICK SORT 16
References
GeeksforGeeks. (2019). Analysis of Algorithms. Retrieved from
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/
javatpoint. (2019). Collections in Java. Retrieved from https://www.javatpoint.com/collections-
in-java
javatpoint. (2019). Data structures tutorial. Retrieved from https://www.javatpoint.com/data-
structure-tutorial
GeeksforGeeks. (2019). Java programming language. Retrieved from
https://www.geeksforgeeks.org/java/
HackerEarth. (2019). Quick Sort. Retrieved from
https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/tutorial/
InterviewBit. (2019). Quick sort algorithm. Retrieved from
https://www.interviewbit.com/tutorial/quicksort-algorithm/
GeeksforGeeks. (2019). Sorting Algorithms. Retrieved from
https://www.geeksforgeeks.org/sorting-algorithms/
WhatIs.com. (2019). What is algorithm. Retrieved from
https://whatis.techtarget.com/definition/algorithm