Analysis of Sorting Algorithms: Java Implementation and Performance

This assignment focuses on the implementation and analysis of fundamental sorting algorithms in Java. It includes Java code for Bubble Sort, Insertion Sort, and Selection Sort, along with a main method to demonstrate their usage with an array of Student objects. The code sorts students by their last names. The assignment also presents performance analysis, showing the execution time of the algorithms with different array sizes. Multiple examples are provided, demonstrating the time taken by these algorithms with increasing input sizes, highlighting the efficiency and potential limitations of each sorting method, especially with larger datasets, where some algorithms may experience timeouts. This homework provides a practical understanding of sorting algorithms and their efficiency.

Solution 1
public class Student {
public String firstName;
public String lastName;
public int id;
public Student(String firstName, String lastName, int id)
{
this.firstName = firstName;
this.lastName = lastName;
this.id = id;
}
}
public class BubbleSort {
// bubble sort method to sort according to last name
public void bubbleSort(Student[] s) {
for (int i = 0; i <s.length; i++) {
for (int j = i + 1; j < s.length; j++) {
if ((s[i].lastName.compareTo(s[j].lastName)) > 0) {
String firstName=s[j].firstName;
String lastName= s[j].lastName;
int id=s[j].id;
s[j].firstName=s[i].firstName;
s[j].lastName=s[i].lastName;
s[j].id=s[i].id;
s[i].firstName=firstName;
s[i].lastName=lastName;
s[i].id=id;
}
}
}
for (Student stu : s) {
System.out.println(stu.firstName + " " + stu.lastName + " " + stu.id);
}
}
}

public class InsertionSort {
// insertionSort method to sort according to last name
public void insertionSort(Student[] s) {
int n =s.length;
for (int j = 1; j < n; j++) {
String key = s[j].lastName;
String key1 = s[j].firstName;
int key2 = s[j].id;
int i = j-1;
while ( (i > -1) && ( s[i].lastName.compareTo(key) >0 ) ) {
s[i+1].firstName=s[i].firstName;
s[i+1].lastName=s[i].lastName;
s[i+1].id=s[i].id;
i--;
}
s[i+1].lastName = key;
s[i+1].firstName=key1;
s[i+1].id=key2;
}
for (Student stu : s) {
System.out.println(stu.firstName + " " + stu.lastName + " " + stu.id);
}
}
}
public class SelectionSort {
// selectionSort method to sort according to last name
public void selectionSort(Student[] s) {
for (int i = 0; i < s.length - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < s.length; ++j) {
if (s[j].lastName.compareTo(s[minIndex].lastName) < 0) {
minIndex = j;
}
String firstName = s[i].firstName;
String lastName = s[i].lastName;

int id= s[i].id;
s[i].firstName = s[minIndex].firstName;
s[i].lastName = s[minIndex].lastName;
s[i].id = s[minIndex].id;
s[minIndex].firstName = firstName;
s[minIndex].lastName = lastName;
s[minIndex].id = id;
}
}
for (Student stu : s) {
System.out.println(stu.firstName + " " + stu.lastName + " " + stu.id);
}
}
}
public class NamesMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
Student[] s = new Student[8];
s[0] = new Student("Saoud", "Mohamed", 3);
s[1] = new Student("Abdelkader", "Farouk", 2);
s[2] = new Student("Beshr", "Alsharqawy", 1);
s[3] = new Student("Nader", "Salah", 4);
s[4] = new Student("Basem", "Hawary", 5);
s[5] = new Student("Abdullah", "Babaker", 6);
s[6] = new Student("Abdelaal", "Khairy", 7);
s[7] = new Student("Mohamedain", "Marsily", 8);
//Unsorted Array
System.out.println("Unsorted by the last name ");
for (Student stu : s) {
System.out.println(stu.firstName + " " + stu.lastName + " " + stu.id);
}
System.out.println();
System.out.println("------------------------Bubble Sort-----------------------");

BubbleSort bb=new BubbleSort();
bb.bubbleSort(s);
System.out.println();
System.out.println();
System.out.println("-------------------------Insertion Sort----------------------");
InsertionSort is=new InsertionSort();
is.insertionSort(s);
System.out.println();
System.out.println();
System.out.println("-------------------------Selection Sort----------------------");
SelectionSort se=new SelectionSort();
se.selectionSort(s);
}
}
OUTPUT

Solution 2
EXAMPLE 1
ARRAY SIZE TIME(ms)
1000 12
10000 16
100000 16
1000000 22
10000000 22
0 2000000 4000000 6000000 8000000 10000000 12000000
0
5
10
15
20
25
12
1616
22 22
EXAMPLE 1
ARRAY SIZE
TIME(ms)

EXAMPLE 2
ARRAY SIZE TIME(ms)
1000 12
10000 13
100000 15
1000000 17
10000000 19
0 2000000 4000000 6000000 8000000 10000000 12000000
0
2
4
6
8
10
12
14
16
18
20
12
13
15
17
19
EXAMPLE 2
ARRAY SIZE
TIME(ms)

EXAMPLE 3
ARRAY SIZE TIME(ms)
1000 19
10000 41
100000 2530
1000000 TIME OUT
10000000 TIME OUT
0 2000000 4000000 6000000 8000000 10000000 12000000
0
500
1000
1500
2000
2500
3000
1941
2530
EXAMPLE 3
ARRAY SIZE
TIME(ms)

EXAMPLE 4
ARRAY SIZE TIME(ms)
1000 13
10000 16
100000 18
1000000 20
10000000 25
0 2000000 4000000 6000000 8000000 10000000 12000000
0
5
10
15
20
25
30
13
16
18
20
25
EXAMPLE 4
ARRAY SIZE
TIME(ms)