All of the sorts:
Bubble Sort:
- repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order
public class BubbleSort {
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) { //Ensures it makes all consecutive swaps for the necessary amount of times
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
// swap array[j+1] and array[j]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
System.out.print("Current Array: ");
for (int k : array) {
System.out.print(k + " ");
}
System.out.println();
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array:");
for (int el : arr) {
System.out.print(el + " ");
}
}
}
BubbleSort.main(null);
Current Array: 34 64 25 12 22 11 90
Current Array: 34 25 64 12 22 11 90
Current Array: 34 25 12 64 22 11 90
Current Array: 34 25 12 22 64 11 90
Current Array: 34 25 12 22 11 64 90
Current Array: 25 34 12 22 11 64 90
Current Array: 25 12 34 22 11 64 90
Current Array: 25 12 22 34 11 64 90
Current Array: 25 12 22 11 34 64 90
Current Array: 12 25 22 11 34 64 90
Current Array: 12 22 25 11 34 64 90
Current Array: 12 22 11 25 34 64 90
Current Array: 12 11 22 25 34 64 90
Current Array: 11 12 22 25 34 64 90
Sorted array:
11 12 22 25 34 64 90
Selection Sort
- repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
System.out.print("Current Array: ");
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
SelectionSort.main(null);
Current Array: 64 25 12 22 11
Current Array: 64 25 12 22 11
Current Array: 64 25 12 22 11
Current Array: 11 25 12 22 64
Current Array: 11 12 25 22 64
Sorted array:
11 12 22 25 64
Insertion Sort
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
System.out.print("Current Array: ");
for (int k : arr) {
System.out.print(k + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
insertionSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
InsertionSort.main(null);
Current Array: 25 64 12 22 11
Current Array: 12 25 64 22 11
Current Array: 12 22 25 64 11
Current Array: 11 12 22 25 64
Sorted array:
11 12 22 25 64
Merge Sort
Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts the two halves independently, and then merges the sorted halves.
public class MergeSort {
public static void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
System.out.print("Current Array: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
MergeSort.main(null);
Current Array: 11 12 13 5 6 7
Current Array: 11 12 13 5 6 7
Current Array: 11 12 13 5 6 7
Current Array: 11 12 13 5 6 7
Current Array: 5 6 7 11 12 13
Sorted array:
5 6 7 11 12 13
Quicksort
Quicksort is based on: based on the divide-and-conquer strategy. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
public class QuickSort {
public static void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
System.out.print("Current Array: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 4, 7,11,15,23,34,54,21, 8, 9, 1, 5,100,23,1234};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
QuickSort.main(null);
Current Array: 1 4 5 11 15 21 8 9 10 7 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 100 54 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 54 100 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 54 100 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 54 100 1234
Current Array: 1 4 5 7 8 9 10 11 15 21 23 23 34 54 100 1234
Sorted array:
1 4 5 7 8 9 10 11 15 21 23 23 34 54 100 1234
My own sorting program
import java.util.Scanner;
public class SortingProgram {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Choose a sorting algorithm:");
System.out.println("1. Bubble Sort");
System.out.println("2. Selection Sort");
System.out.println("3. Insertion Sort");
System.out.println("4. Merge Sort");
System.out.println("5. Quick Sort");
System.out.print("Enter the number corresponding to the sorting algorithm: ");
int choice = scanner.nextInt();
int[] arr = {64, 25, 12, 22, 11}; // Sample array for demonstration
switch (choice) {
case 1:
System.out.println("Your input: ");
System.out.println(choice);
BubbleSort.bubbleSort(arr);
break;
case 2:
System.out.println("Your input: ");
System.out.println(choice);
SelectionSort.selectionSort(arr);
break;
case 3:
System.out.println("Your input: ");
System.out.println(choice);
InsertionSort.insertionSort(arr);
break;
case 4:
System.out.println("Your input: ");
System.out.println(choice);
MergeSort.mergeSort(arr, 0, arr.length - 1);
break;
case 5:
System.out.println("Your input: ");
System.out.println(choice);
QuickSort.quickSort(arr, 0, arr.length - 1);
break;
default:
System.out.println("Invalid choice!");
}
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
SortingProgram.main(null);
Choose a sorting algorithm:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
Enter the number corresponding to the sorting algorithm: Your input:
2
Current Array: 64 25 12 22 11
Current Array: 64 25 12 22 11
Current Array: 64 25 12 22 11
Current Array: 11 25 12 22 64
Current Array: 11 12 25 22 64
Sorted array:
11 12 22 25 64