Question
Assume that a team of 50 players have to arrange in descending order, based on the date of the covid19 vaccine has been taken, to identify 15 players who have vaccinated first.
(1) Design and develop a suitable sorting algorithm to sort these players based on their vaccination date.
(2) Implement the sorting algorithm using a java programming language.
(3) Hand trace the algorithm using a completely different set of dates for five players.
(4) Calculate the complexity of the program you implemented above.
Answer
Used Bubble Sort Algorithm to Solve this problem.
1)
2) Java code implementaion
import
java.time.LocalDate;
public class Players {
public String name;
public LocalDate vDate;
public Players(String name, LocalDate d) {
this.name = name;
vDate = d;
}
// Function
public static void
sortDesc(Players[] team) {
int i, j;
for (i = 0; i < (team.length - 1); i++) {
for (j = 0; j < team.length - i - 1; j++) {
if (team[j].vDate.isBefore(team[j + 1].vDate)) {
LocalDate
temp = team[j].vDate;
team[j].vDate = team[j + 1].vDate;
team[j + 1].vDate = temp;
String tName = team[j].name;
team[j].name = team[j + 1].name;
team[j + 1].name = tName;
}
}
}
}
// main method
public static void
main(String[] args) {
int i;
Players[]
team = new
Players[15];
// insert 15 players
team[0] = new Players("Nimal", LocalDate.of(2021, 4, 20));
team[1] = new Players("Kamal", LocalDate.of(2021, 5, 7));
team[2] = new Players("Sunimal", LocalDate.of(2021, 5, 1));
team[3] = new Players("Amali", LocalDate.of(2021, 7, 2));
team[4] = new Players("Sriua", LocalDate.of(2021, 8, 4));
team[5] = new Players("Nisha", LocalDate.of(2021, 5, 20));
team[6] = new Players("Nimala", LocalDate.of(2021, 3, 20));
team[7] = new Players("Saman", LocalDate.of(2021, 4, 7));
team[8] = new Players("Sunil", LocalDate.of(2021, 10, 5));
team[9] = new Players("Shsheka", LocalDate.of(2021, 2, 2));
team[10] = new Players("Udaya", LocalDate.of(2021, 4, 6));
team[11] = new Players("Kasun", LocalDate.of(2021, 8, 15));
team[12] = new Players("Kamani", LocalDate.of(2021, 7, 19));
team[13] = new Players("Sumeda", LocalDate.of(2021, 6, 14));
team[14] = new Players("Susan", LocalDate.of(2021, 7, 11));
sortDesc(team);
System.out.println("Sorted(Desc) vaccinated date players were vaccinated.");
for (i = 0; i < team.length; i++) {
System.out.println(" Name: " + team[i].name + " -> Vaccinated date: " + team[i].vDate);
}
}
}
___________________________________________________-
Output|
Sorted(Desc) vaccinated date
players were vaccinated. Name: Sunil -> Vaccinated date:
2021-10-05 Name: Kasun -> Vaccinated date:
2021-08-15 Name: Sriua -> Vaccinated date:
2021-08-04 Name: Kamani -> Vaccinated date:
2021-07-19 Name: Susan -> Vaccinated date:
2021-07-11 Name: Amali -> Vaccinated date:
2021-07-02 Name: Sumeda -> Vaccinated date:
2021-06-14 Name: Nisha -> Vaccinated date:
2021-05-20 Name: Kamal -> Vaccinated date:
2021-05-07 Name: Sunimal -> Vaccinated date:
2021-05-01 Name: Nimal -> Vaccinated date:
2021-04-20 Name: Saman -> Vaccinated date:
2021-04-07 Name: Udaya -> Vaccinated date:
2021-04-06 Name: Nimala -> Vaccinated date:
2021-03-20 Name: Shsheka -> Vaccinated date:
2021-02-02 |
3) Hand trace Bubble sort
.png)
int i, j;
// first loop
for (i = 0; i < (team.length - 1); i++) {
// second loop
for (j = 0; j < team.length - i - 1; j++) {
if (team[j].vDate.isBefore(team[j + 1].vDate)) {
LocalDate
temp = team[j].vDate;
team[j].vDate = team[j + 1].vDate;
team[j + 1].vDate = temp;
String
tName = team[j].name;
team[j].name = team[j + 1].name;
team[j + 1].name = tName;
}
}
}
- In the above code there are two for loops for example “for (i = 0; i < (team.length - 1); i++) “ outer and for (j = 0; j < team.length - i - 1; j++) inner loop.
- The inner loop is executed the following number of times.
- (n-1) + (n-2) +…+(n-ksorted) = ½(2n-ksorted-1)ksorted . Where ksorted is the number of executions of the outer loop before there is pass during which there are no exchanges.
- The inner loop contains one comparison and sometimes an exchange.
- The worst case is derived when ksorted is n-1. The inner loop is executed as follows, ½ (2n – (n‐1) ‐1)(n‐1) = ½ n(n‐1) = O (n2)
The main advantage of Bubble Sort is the simplicity of the algorithm.
