Using Arrays to sort people by pool noodle size
public class Person {
String name;
int noodleLength;
Person(String name, int noodleLength) {
this.name = name;
this.noodleLength = noodleLength;
}
@Override
public String toString() {
return name + ": " + noodleLength;
}
}
public class BeachNoodleSorter {
public static void insertionSort(Person[] people) {
for (int i = 1; i < people.length; i++) {
Person key = people[i];
int j = i - 1;
// Move elements of people[0..i-1], that are greater than key.noodleLength,
// to one position ahead of their current position
while (j >= 0 && people[j].noodleLength > key.noodleLength) {
people[j + 1] = people[j];
j = j - 1;
}
people[j + 1] = key;
}
}
public static void main(String[] args) {
Person[] people = {
new Person("Beach Volleyball Dude", 8),
new Person("Sandcastle", 11),
new Person("Click, Half Dolphin, Half Man", 10),
new Person("M.A.T.I", 9),
new Person("Scuba Diver", 1)
};
System.out.println("Before sorting:");
System.out.println(Arrays.toString(people) + "\n");
insertionSort(people);
System.out.println("After sorting:");
System.out.println(Arrays.toString(people));
}
}
BeachNoodleSorter.main(null);
Before sorting:
[Beach Volleyball Dude: 8, Sandcastle: 11, Click, Half Dolphin, Half Man: 10, M.A.T.I: 9, Scuba Diver: 1]
After sorting:
[Scuba Diver: 1, Beach Volleyball Dude: 8, M.A.T.I: 9, Click, Half Dolphin, Half Man: 10, Sandcastle: 11]
Using Linked Lists to sort people by pool noodle size
public abstract class Collectable implements Comparable<Collectable> {
public final String masterType = "Collectable";
private String type;
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey();
public String getMasterType() {
return masterType;
}
public String getType() {
return type;
}
public void setType(String type) {
this.type = type;
}
public abstract String toString();
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
public static void print(Collectable[] objs) {
System.out.println(objs.getClass() + " " + objs.length);
if (objs.length > 0) {
Collectable obj = objs[0];
System.out.println(obj.getMasterType() + ": " + obj.getType() + " listed by " + obj.getKey());
}
for (Object o : objs)
System.out.println(o);
System.out.println();
}
}
class People extends Collectable {
public static KeyTypes key = KeyType.name;
public static void setOrder(KeyTypes key) { People.key = key; }
public enum KeyType implements KeyTypes { name, noodleLength }
private final String name;
private final int noodleLength;
People(String name, int noodleLength) {
this.setType("People");
this.name = name;
this.noodleLength = noodleLength;
}
@Override
protected KeyTypes getKey() {
return People.key;
}
@Override
public String toString() {
StringBuilder jsonBuilder = new StringBuilder();
jsonBuilder.append("{");
if (KeyType.name.equals(this.getKey())) {
jsonBuilder.append("\"name\": \"").append(this.name).append("\", ");
} else if (KeyType.noodleLength.equals(this.getKey())) {
jsonBuilder.append("\"noodleLength\": ").append(this.noodleLength).append(", ");
}
jsonBuilder.append("\"type\": \"").append(this.getType()).append("\", ")
.append("\"masterType\": \"").append(this.masterType).append("\"");
jsonBuilder.append("}");
return jsonBuilder.toString();
}
// Bubble sort
public static void bubbleSort(List<Collectable> list) {
int n = list.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (list.get(j).compareTo(list.get(j + 1)) > 0) {
Collectable temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
// Selection sort
public static void selectionSort(List<Collectable> list) {
int n = list.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (list.get(j).compareTo(list.get(minIndex)) < 0) {
minIndex = j;
}
}
Collectable temp = list.get(minIndex);
list.set(minIndex, list.get(i));
list.set(i, temp);
}
}
// Insertion sort
public static void insertionSort(List<Collectable> list) {
int n = list.size();
for (int i = 1; i < n; ++i) {
Collectable key = list.get(i);
int j = i - 1;
while (j >= 0 && list.get(j).compareTo(key) > 0) {
list.set(j + 1, list.get(j));
j = j - 1;
}
list.set(j + 1, key);
}
}
// Merge sort
public static void mergeSort(List<Collectable> list) {
if (list.size() > 1) {
int mid = list.size() / 2;
List<Collectable> left = new java.util.LinkedList<>(list.subList(0, mid));
List<Collectable> right = new java.util.LinkedList<>(list.subList(mid, list.size()));
mergeSort(left);
mergeSort(right);
merge(list, left, right);
}
}
private static void merge(List<Collectable> list, List<Collectable> left, List<Collectable> right) {
int i = 0, j = 0, k = 0;
while (i < left.size() && j < right.size()) {
if (left.get(i).compareTo(right.get(j)) <= 0) {
list.set(k++, left.get(i++));
} else {
list.set(k++, right.get(j++));
}
}
while (i < left.size()) {
list.set(k++, left.get(i++));
}
while (j < right.size()) {
list.set(k++, right.get(j++));
}
}
// Quick sort
public static void quickSort(List<Collectable> list, int low, int high) {
if (low < high) {
int pi = partition(list, low, high);
quickSort(list, low, pi - 1);
quickSort(list, pi + 1, high);
}
}
private static int partition(List<Collectable> list, int low, int high) {
Collectable pivot = list.get(high);
int i = (low - 1);
for (int j = low; j < high; j++) {
if (list.get(j).compareTo(pivot) < 0) {
i++;
Collectable temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
Collectable temp = list.get(i + 1);
list.set(i + 1, list.get(high));
list.set(high, temp);
return i + 1;
}
}
public class CreateBeach {
// test data
public static List<Collectable> people() {
List<Collectable> peopleList = new LinkedList<>();
peopleList.add(new People("Rapper", 8));
peopleList.add(new People("Lifeguard", 6));
peopleList.add(new People("Corn Oil", 5));
peopleList.add(new People("Beach Volleyball Guy", 9));
peopleList.add(new People("Scuba Diver", 1));
return peopleList;
}
}
Sorting using Bubble Sort
List<Collectable> people = CreateBeach.people();
People.setOrder(People.KeyType.noodleLength);
System.out.println("Original: \n" + people + "\n");
People person = new People("", 0);
person.bubbleSort(people);
System.out.println("Sorted by Pool Noodle Length: \n" + people);
Original:
[{"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}, {"noodleLength": 1, "type": "People", "masterType": "Collectable"}]
Sorted by Pool Noodle Length:
[{"noodleLength": 1, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}]
Sorting using Selection Sort
List<Collectable> people = CreateBeach.people();
People.setOrder(People.KeyType.noodleLength);
System.out.println("Original: \n" + people + "\n");
People person = new People("", 0);
person.selectionSort(people);
System.out.println("Sorted by Pool Noodle Length: \n" + people);
Original:
[{"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}, {"noodleLength": 1, "type": "People", "masterType": "Collectable"}]
Sorted by Pool Noodle Length:
[{"noodleLength": 1, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}]
Sorting using Insertion Sort
List<Collectable> people = CreateBeach.people();
People.setOrder(People.KeyType.noodleLength);
System.out.println("Original: \n" + people + "\n");
People person = new People("", 0);
person.insertionSort(people);
System.out.println("Sorted by Pool Noodle Length: \n" + people);
Original:
[{"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}, {"noodleLength": 1, "type": "People", "masterType": "Collectable"}]
Sorted by Pool Noodle Length:
[{"noodleLength": 1, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}]
Sorting using Merge Sort
List<Collectable> people = CreateBeach.people();
People.setOrder(People.KeyType.noodleLength);
System.out.println("Original: \n" + people + "\n");
People person = new People("", 0);
person.mergeSort(people);
System.out.println("Sorted by Pool Noodle Length: \n" + people);
Original:
[{"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}, {"noodleLength": 1, "type": "People", "masterType": "Collectable"}]
Sorted by Pool Noodle Length:
[{"noodleLength": 1, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}]
Sorting using Quick Sort
List<Collectable> people = CreateBeach.people();
People.setOrder(People.KeyType.noodleLength);
System.out.println("Original: \n" + people + "\n");
People person = new People("", 0);
person.quickSort(people, 0, people.size() - 1);
System.out.println("Sorted by Pool Noodle Length: \n" + people);
Original:
[{"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}, {"noodleLength": 1, "type": "People", "masterType": "Collectable"}]
Sorted by Pool Noodle Length:
[{"noodleLength": 1, "type": "People", "masterType": "Collectable"}, {"noodleLength": 5, "type": "People", "masterType": "Collectable"}, {"noodleLength": 6, "type": "People", "masterType": "Collectable"}, {"noodleLength": 8, "type": "People", "masterType": "Collectable"}, {"noodleLength": 9, "type": "People", "masterType": "Collectable"}]