Sorting is an important part of computer programming. It helps you arrange items like numbers or words in a specific order. There are different ways to sort things, and in this article, we will learn how to use three popular sorting methods in Java: Bubble Sort, Merge Sort, and Quick Sort. We will explain these methods step by step in simple language.
Bubble Sort in Java
Bubble Sort is one of the easiest sorting methods. It repeatedly compares two adjacent elements and swaps them if they are in the wrong order. After each pass through the list, the largest number "bubbles" to the end of the array.
How Bubble Sort Works?
- Compare the first two elements.
- If the first element is bigger, swap them.
- Move to the next pair and repeat the process.
- Keep doing this until no swaps are needed.
Bubble Sort Code
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:");
printArray(arr);
bubbleSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
Explanation
- The bubbleSort method compares adjacent elements and swaps them if necessary.
- After each pass, the largest number moves to the end.
- This continues until the entire array is sorted.
Output
![]()
Merge Sort in Java
Merge Sort is a more efficient sorting method. It divides the array into two halves, sorts each half, and then combines them back together in order.
How Merge Sort Works?
- Split the array into two halves.
- Sort each half.
- Merge the two sorted halves together.
Merge Sort Code
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length < 2) {
return; // If the array has one or zero elements, it's already sorted
}
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
// Copy data to temporary arrays
System.arraycopy(arr, 0, left, 0, mid);
System.arraycopy(arr, mid, right, 0, arr.length - mid);
mergeSort(left); // Sort the left half
mergeSort(right); // Sort the right half
merge(arr, left, right); // Merge the sorted halves
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
// Merge the two sorted arrays
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
// Copy any remaining elements
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Original array:");
printArray(arr);
mergeSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
Explanation
- The mergeSort method divides the array into two parts.
- It recursively sorts the two halves.
- Then, it combines them back together in the correct order using the merge method.
Output
![]()
Quick Sort in Java
Quick Sort is another efficient sorting method. It works by picking a pivot element, then organizing the array into two parts: one with smaller numbers and the other with larger numbers than the pivot. Afterward, it sorts the two parts.
How Quick Sort Works?
- Pick a pivot element.
- Move elements smaller than the pivot to the left and larger elements to the right.
- Recursively sort the two parts.
Quick Sort Code
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); // Sort the left side
quickSort(arr, pi + 1, high); // Sort the right side
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choose the last element as pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap pivot element with arr[i + 1]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return pivot position
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 3};
System.out.println("Original array:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
Explanation
- The quickSort method sorts the array by dividing it into smaller parts around a pivot.
- The partition method rearranges the array so that numbers less than the pivot come before it, and numbers greater than the pivot come after it.
Output
![]()
Conclusion
We have now seen how to implement three popular sorting methods in Java.
- Bubble Sort: Simple but not very fast for large arrays.
- Merge Sort: Efficient and divides the array into smaller parts, sorting them before merging.
- Quick Sort: Fast on average, using a pivot to divide the array into smaller subarrays.
Each method has its pros and cons, but understanding how they work helps you choose the best one for different situations. By practicing these sorting algorithms, you can improve your problem-solving and programming skills!