Quick Sort!
It divides the list into smaller sublists based on a chosen pivot element, then recursively sorts each sublist.
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class House implements Comparable<House>{
public int price;
private int id;
public House(int price, int id) {
this.price = price;
this.id = id;
}
public int getPrice() {
return price;
}
@Override
public int compareTo(House other) {
// Compare persons based on their age
return Integer.compare(this.price, other.price);
}
@Override
public String toString() {
return "House{" +
"House ID ='" + id + '\'' +
", price =" + price +
'}';
}
}
public class QuickSort<T extends Comparable<T>> {
public void quickSort(List<T> list, int start, int end) {
if (start < end) {
int pivotIndex = partition(list, start, end);
quickSort(list, start, pivotIndex - 1);
quickSort(list, pivotIndex + 1, end);
}
}
public int partition(List<T> list, int start, int end) {
T pivot = list.get(end);
int i = start - 1;
for (int j = start; j < end; j++) {
if (list.get(j).compareTo(pivot) < 0) {
i++;
T temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
T temp = list.get(i + 1);
list.set(i + 1, list.get(end));
list.set(end, temp);
return i + 1;
}
public static void main(String[] args) {
House house1 = new House(500, 1);
House house2 = new House(405, 2);
House house3 = new House(602, 3);
House house4 = new House(600, 4);
List<House> list = new ArrayList<>(Arrays.asList(house1, house2, house3, house4)); // sorts based off of price, it's messy but whatever
System.out.println("Original list: " + list);
QuickSort<House> quickSort = new QuickSort<>();
long startTime = System.nanoTime();
quickSort.quickSort(list, 0, list.size() - 1);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Sorted list: " + list);
System.out.println("Time taken: " + duration + " nanoseconds");
}
}
QuickSort.main(null);
Original list: [House{House ID ='1', price =500}, House{House ID ='2', price =405}, House{House ID ='3', price =602}, House{House ID ='4', price =600}]
Sorted list: [House{House ID ='2', price =405}, House{House ID ='1', price =500}, House{House ID ='4', price =600}, House{House ID ='3', price =602}]
Time taken: 3042 nanoseconds
Selection Sort!
It repeatedly selects the minimum element from the unsorted portion of the list and moves it to the beginning.
import java.util.Arrays;
class House implements Comparable<House>{
public int price;
private int id;
public House(int price, int id) {
this.price = price;
this.id = id;
}
public int getPrice() {
return price;
}
@Override
public int compareTo(House other) {
// Compare persons based on their age
return Integer.compare(this.price, other.price);
}
@Override
public String toString() {
return "House{" +
"House ID ='" + id + '\'' +
", price =" + price +
'}';
}
}
public class SelectionSort<T extends Comparable<T>> {
public void selectionSort(List<T> 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;
}
}
// Swap the found minimum element with the element at index i
T temp = list.get(minIndex);
list.set(minIndex, list.get(i));
list.set(i, temp);
}
}
// main method for testing
public static void main(String[] args) {
House house1 = new House(500, 1);
House house2 = new House(405, 2);
House house3 = new House(602, 3);
House house4 = new House(600, 4);
List<House> list = new ArrayList<>(Arrays.asList(house1, house2, house3, house4)); // sorts based off of price, it's messy but whatever
System.out.println("Original list: " + list);
SelectionSort<House> selectionSort = new SelectionSort<>();
long startTime = System.nanoTime();
selectionSort.selectionSort(list);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Sorted list: " + list);
System.out.println("Time taken: " + duration + " nanoseconds");
}
}
SelectionSort.main(null);
Original list: [House{House ID ='1', price =500}, House{House ID ='2', price =405}, House{House ID ='3', price =602}, House{House ID ='4', price =600}]
Sorted list: [House{House ID ='2', price =405}, House{House ID ='1', price =500}, House{House ID ='4', price =600}, House{House ID ='3', price =602}]
Time taken: 9041 nanoseconds
Bubble Sort!
It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
import java.util.Arrays;
class House implements Comparable<House>{
public int price;
private int id;
public House(int price, int id) {
this.price = price;
this.id = id;
}
public int getPrice() {
return price;
}
@Override
public int compareTo(House other) {
// Compare persons based on their age
return Integer.compare(this.price, other.price);
}
@Override
public String toString() {
return "House{" +
"House ID ='" + id + '\'' +
", price =" + price +
'}';
}
}
public class BubbleSort<T extends Comparable<T>> {
public void bubbleSort(List<T> list) {
int n = list.size();
for (int i = 0; i < n; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (list.get(j).compareTo(list.get(j + 1)) > 0) {
T temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
House house1 = new House(500, 1);
House house2 = new House(405, 2);
House house3 = new House(602, 3);
House house4 = new House(600, 4);
List<House> list = new ArrayList<>(Arrays.asList(house1, house2, house3, house4)); // sorts based off of price, it's messy but whatever
System.out.println("Original list: " + list);
BubbleSort<House> bubbleSort = new BubbleSort<>();
long startTime = System.nanoTime();
bubbleSort.bubbleSort(list);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Sorted list: " + list);
System.out.println("Time taken: " + duration + " nanoseconds");
}
}
BubbleSort.main(null);
Original list: [House{House ID ='1', price =500}, House{House ID ='2', price =405}, House{House ID ='3', price =602}, House{House ID ='4', price =600}]
Sorted list: [House{House ID ='2', price =405}, House{House ID ='1', price =500}, House{House ID ='4', price =600}, House{House ID ='3', price =602}]
Time taken: 7666 nanoseconds
Merge Sort!
It divides the list into smaller sublists until each sublist is sorted, then merges the sublists back together in sorted order.
import java.util.Arrays;
import java.util.List;
class House implements Comparable<House>{
public int price;
private int id;
public House(int price, int id) {
this.price = price;
this.id = id;
}
public int getPrice() {
return price;
}
@Override
public int compareTo(House other) {
// Compare persons based on their age
return Integer.compare(this.price, other.price);
}
@Override
public String toString() {
return "House{" +
"House ID ='" + id + '\'' +
", price =" + price +
'}';
}
}
public class MergeSort<T extends Comparable<T>> {
// Function to perform Merge Sort
public void mergeSort(List<T> list, int left, int right) {
if (left < right) {
// Find the middle point to divide the list into two halves
int mid = left + (right - left) / 2;
// Recursively sort the first and second halves
mergeSort(list, left, mid);
mergeSort(list, mid + 1, right);
// Merge the sorted halves
merge(list, left, mid, right);
}
}
// Function to merge two sublists of list
public void merge(List<T> list, int left, int mid, int right) {
// Find sizes of two sublists to be merged
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
List<T> L = list.subList(left, mid + 1);
List<T> R = list.subList(mid + 1, right + 1);
// Merge the temporary arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L.get(i).compareTo(R.get(j)) <= 0) {
list.set(k, L.get(i));
i++;
} else {
list.set(k, R.get(j));
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
list.set(k, L.get(i));
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
list.set(k, R.get(j));
j++;
k++;
}
}
// Utility function to print the list
public void printList(List<T> list) {
for (T item : list) {
System.out.print(item + " ");
}
System.out.println();
}
public static void main(String[] args) {
House house1 = new House(500, 1);
House house2 = new House(405, 2);
House house3 = new House(602, 3);
House house4 = new House(600, 4);
List<House> list = new ArrayList<>(Arrays.asList(house1, house2, house3, house4)); // sorts based off of price, it's messy but whatever
System.out.println("Original list: " + list);
BubbleSort<House> bubbleSort = new BubbleSort<>();
long startTime = System.nanoTime();
bubbleSort.bubbleSort(list);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Sorted list: " + list);
System.out.println("Time taken: " + duration + " nanoseconds");
}
}
MergeSort.main(null);
Original list: [House{House ID ='1', price =500}, House{House ID ='2', price =405}, House{House ID ='3', price =602}, House{House ID ='4', price =600}]
Sorted list: [House{House ID ='2', price =405}, House{House ID ='1', price =500}, House{House ID ='4', price =600}, House{House ID ='3', price =602}]
Time taken: 9833 nanoseconds
Insertion Sort!
It builds the sorted list one element at a time by repeatedly taking the next element and inserting it into its correct position in the sorted part of the list.
import java.util.Arrays;
import java.util.List;
class House implements Comparable<House>{
public int price;
private int id;
public House(int price, int id) {
this.price = price;
this.id = id;
}
public int getPrice() {
return price;
}
@Override
public int compareTo(House other) {
// Compare persons based on their age
return Integer.compare(this.price, other.price);
}
@Override
public String toString() {
return "House{" +
"House ID ='" + id + '\'' +
", price =" + price +
'}';
}
}
public class InsertionSort<T extends Comparable<T>> {
// Function to perform Insertion Sort
public void insertionSort(List<T> list) {
int n = list.size();
// Traverse through the list starting from the second element
for (int i = 1; i < n; i++) {
// Choose the key element to be inserted
T key = list.get(i);
int j = i - 1;
// Move elements of list[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && list.get(j).compareTo(key) > 0) {
list.set(j + 1, list.get(j));
j--;
}
// Place the key element at its correct position
list.set(j + 1, key);
}
}
// Utility function to print the list
public void printList(List<T> list) {
System.out.println("Sorted list: " + list);
}
public static void main(String[] args) {
House house1 = new House(500, 1);
House house2 = new House(405, 2);
House house3 = new House(602, 3);
House house4 = new House(600, 4);
List<House> list = new ArrayList<>(Arrays.asList(house1, house2, house3, house4)); // sorts based off of price, it's messy but whatever
System.out.println("Original list: " + list);
BubbleSort<House> bubbleSort = new BubbleSort<>();
long startTime = System.nanoTime();
bubbleSort.bubbleSort(list);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Sorted list: " + list);
System.out.println("Time taken: " + duration + " nanoseconds");
}
}
InsertionSort.main(null);
Original list: [House{House ID ='1', price =500}, House{House ID ='2', price =405}, House{House ID ='3', price =602}, House{House ID ='4', price =600}]
Sorted list: [House{House ID ='2', price =405}, House{House ID ='1', price =500}, House{House ID ='4', price =600}, House{House ID ='3', price =602}]
Time taken: 2791 nanoseconds