Write a version of insertion sort that is capable of sorting an array of objects
ID: 3815020 • Letter: W
Question
Write a version of insertion sort that is capable of sorting an array of objects of any class that implements the Comparable interface. Write Junit tests to thoroughly test your method. Please note that you will not receive credit if you do not have any test cases. Don't forget the JUnit tests.
Example
Integer[] test = {1, 0, -4, -6, 2, 10};
insertionSort(test);
// test is now {-6, -4, 0, 1, 2, 10} Student bob = new Student(“Bob”, 4.0);
Student alice = new Student(“Alice”, 3.5);
Student carol = new Student(“Carol”, 3.5);
Student dave = new Student(“Dave”, 3.7);
Student[] test = {bob, alice, carol, dave};
// assume Students are compared first on GPA and then on name
// test is now {bob, dave, alice, carol}
Explanation / Answer
HI, Please find my implementation.
import java.util.Arrays;
public class InsertionSortGenerics {
public static <T extends Comparable<T>> void insertionSort(T[] list) {
for (int i=0; i < list.length; i++) {
/* Insert a[i] into the sorted sublist */
T v = list[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (list[j].compareTo(v) <= 0)
break;
list[j + 1] = list[j];
}
list[j+1] = v;
}
}
public static void main(String[] args){
Integer[] test = {1, 0, -4, -6, 2, 1};
insertionSort(test);
System.out.println(Arrays.toString(test));
// test is now {-6, -4, 0, 1, 2, 10}
Student bob = new Student("Bob", 4.0);
Student alice = new Student("Alice", 3.5);
Student carol = new Student("Carol", 3.5);
Student dave = new Student("Dave", 3.7);
Student[] test1 = {bob, alice, dave, carol};
// assume Students are compared first on GPA and then on name
// test is now {bob, dave, alice, carol}
insertionSort(test1);
System.out.println(Arrays.toString(test1));
}
}
class Student implements Comparable<Student>{
private String name;
private double gpa;
public Student(String name, double gpa) {
this.name = name;
this.gpa = gpa;
}
@Override
public int compareTo(Student o) {
if(gpa < o.gpa)
return -1;
else if(gpa > o.gpa)
return 1;
else{
return name.compareTo(o.name);
}
}
@Override
public String toString() {
return name;
}
}
/*
Sample run:
[-6, -4, 0, 1, 1, 2]
[Alice, Carol, Dave, Bob]
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.