public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { //iterate through each array index
for (int j = 0; j < n - i - 1; j++) { //iterate through every index before i
if (arr[j] > arr[j + 1]) { //compare every j and the number before it
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6}; //Make array
System.out.println("Unsorted array");
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
System.out.println();
bubbleSort(array); //run sort
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
}
BubbleSort.main(null)
Unsorted array
5 2 9 1 5 6
Sorted array:
1 2 5 5 6 9
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { //iterate through each array index
int minIndex = i; // record the minimum index
for (int j = i + 1; j < n; j++) { //iterate through every index after i
if (arr[j] < arr[minIndex]) {
minIndex = j; //if the current index is less than the minimum, assign it as the new minimum
}
}
// Swap arr[i] and arr[minIndex]
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Unsorted array:");
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
System.out.println();
selectionSort(array);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
}
SelectionSort.main(null)
Unsorted array:
5 2 9 1 5 6
Sorted array:
1 2 5 5 6 9
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) { // iterate through every index starting at the second one
int key = arr[i]; // mark current value as key
int j = i - 1; // create a second variable for the previous index
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) { //if j is greater than 0 and j-value is greater than key
arr[j + 1] = arr[j]; // replaces the index above j with j-value
j -= 1; // decreases j by one
}
arr[j + 1] = key; //adds key back because it has been removed from j-value swap
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Unsorted array:");
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
System.out.println();
insertionSort(array);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
}
InsertionSort.main(null)
Unsorted array:
5 2 9 1 5 6
Sorted array:
1 2 5 5 6 9
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) { //if left index (beginning index) is less than right index (ending index)
int mid = (left + right) / 2; //math to find middle of indexes
// Split array in half
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1; // length of first half of the array
int n2 = right - mid; // length of second half of the array
// Create temporary arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temporary arrays L[] and R[]
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) { //goes through each element for both arrays
if (L[i] <= R[j]) { // if the current value for L[] is bigger
arr[k] = L[i]; // assign that value to the big non-temporary array
i++; // counter for L[]
} else {
arr[k] = R[j]; // same but for R[]
j++; // counter for R[]
}
k++; //counter for arr[]
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Unsorted array:");
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
System.out.println();
mergeSort(array, 0, array.length - 1); // input the array, the beginning index and ending index
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
}
MergeSort.main(null)
Unsorted array:
5 2 9 1 5 6
Sorted array:
1 2 5 5 6 9
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index
int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Select the rightmost element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) { //goes through the entire given array
if (arr[j] < pivot) { // if the current value is less than pivot
i++; //increase i
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
System.out.println("Unsorted array:");
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
System.out.println();
quickSort(array, 0, array.length - 1); // input the array, the beginning index and ending index
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}
}
QuickSort.main(null)
Unsorted array:
5 2 9 1 5 6
Sorted array:
1 2 5 5 6 9
public class Power {
public String name;
public int powerLevel;
public Power(String name, int powerLevel) {
this.name = name;
this.powerLevel = powerLevel;
}
public boolean compareTo(Power person) {
if (this.powerLevel < person.powerLevel) {
return true;
} else {
return false;
}
}
public static void selectionSort(ArrayList<Power> arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) { //iterate through each array index
int minIndex = i; // record the minimum index
for (int j = i + 1; j < n; j++) { //iterate through every index after i
if (arr.get(j).compareTo(arr.get(minIndex))) {
minIndex = j; //if the current index is less than the minimum, assign it as the new minimum
}
}
// Swap arr[i] and arr[minIndex]
Power temp = arr.get(i);
arr.set(i, arr.get(minIndex));
arr.set(minIndex, temp);
}
}
public static void main(String[] args) {
Power One = new Power("Asher", 9002);
Power Two = new Power("Evan", 9001);
Power Three = new Power("Kali", 10000000);
Power Four = new Power("Isaiah", 1);
Power Five = new Power("A Rock", 3);
Power Six = new Power("Luis", 2);
ArrayList<Power> array = new ArrayList<Power>();
array.add(One);
array.add(Three);
array.add(Four);
array.add(Five);
array.add(Two);
array.add(Six);
System.out.println("Unsorted array:");
for (Power person : array) {
System.out.println(person.name + " " + person.powerLevel);
}
System.out.println();
selectionSort(array);
System.out.println("Sorted array:");
for (Power person : array) {
System.out.println(person.name + " " + person.powerLevel);
}
}
}
Power.main(null)
Unsorted array:
Asher 9002
Kali 10000000
Isaiah 1
A Rock 3
Evan 9001
Luis 2
Sorted array:
Isaiah 1
Luis 2
A Rock 3
Evan 9001
Asher 9002
Kali 10000000