How to sort Java array?

Sorting Java Arrays: A Comprehensive Guide

Introduction

Java arrays are a fundamental data structure in programming, used to store collections of elements of the same data type. Sorting a Java array is an essential operation that can be performed to organize the elements in a specific order. In this article, we will explore the different methods of sorting Java arrays, including bubble sort, selection sort, insertion sort, merge sort, and quick sort.

Why Sort a Java Array?

Before we dive into the methods of sorting, let’s consider why sorting a Java array is necessary. Sorting a Java array can be useful in various scenarios, such as:

  • Organizing data in a specific order
  • Comparing elements for equality
  • Performing calculations based on sorted data

Methods of Sorting Java Arrays

Here are the different methods of sorting Java arrays:

Bubble Sort

  • Algorithm: Bubble sort is a simple sorting algorithm that works by repeatedly iterating through the array and swapping adjacent elements if they are in the wrong order.
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)
  • Example Code:

    public class BubbleSort {
    public static void sort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
    if (array[j] > array[j + 1]) {
    // Swap elements
    int temp = array[j];
    array[j] = array[j + 1];
    array[j + 1] = temp;
    }
    }
    }
    }

    public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Before sorting:");
    printArray(array);
    sort(array);
    System.out.println("After sorting:");
    printArray(array);
    }

    public static void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
    }
    System.out.println();
    }
    }

Selection Sort

  • Algorithm: Selection sort is a simple sorting algorithm that works by selecting the smallest (or largest) element from the unsorted portion of the array and swapping it with the first element of the unsorted portion.
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)
  • Example Code:

    public class SelectionSort {
    public static void sort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
    if (array[j] < array[minIndex]) {
    minIndex = j;
    }
    }
    // Swap elements
    int temp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = temp;
    }
    }

    public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Before sorting:");
    printArray(array);
    sort(array);
    System.out.println("After sorting:");
    printArray(array);
    }

    public static void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
    }
    System.out.println();
    }
    }

Insertion Sort

  • Algorithm: Insertion sort is a simple sorting algorithm that works by iterating through the array one element at a time, inserting each element into its proper position in the sorted portion of the array.
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)
  • Example Code:

    public class InsertionSort {
    public static void sort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; i++) {
    int key = array[i];
    int j = i - 1;
    while (j >= 0 && array[j] > key) {
    array[j + 1] = array[j];
    j--;
    }
    array[j + 1] = key;
    }
    }

    public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Before sorting:");
    printArray(array);
    sort(array);
    System.out.println("After sorting:");
    printArray(array);
    }

    public static void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
    }
    System.out.println();
    }
    }

Merge Sort

  • Algorithm: Merge sort is a divide-and-conquer algorithm that works by splitting the array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together.
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)
  • Example Code:

    public class MergeSort {
    public static void sort(int[] array) {
    mergeSort(array, 0, array.length - 1);
    }

    public static void mergeSort(int[] array, int low, int high) {
    if (low < high) {
    int mid = low + (high - low) / 2;
    mergeSort(array, low, mid);
    mergeSort(array, mid + 1, high);
    merge(array, low, mid, high);
    }
    }

    public static void merge(int[] array, int low, int mid, int high) {
    int[] left = new int[mid - low + 1];
    int[] right = new int[high - mid];
    System.arraycopy(array, low, left, 0, mid - low + 1);
    System.arraycopy(array, mid + 1, right, 0, high - mid);
    int i = 0, j = 0, k = low;
    while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
    array[k] = left[i];
    i++;
    } else {
    array[k] = right[j];
    j++;
    }
    k++;
    }
    while (i < left.length) {
    array[k] = left[i];
    i++;
    k++;
    }
    while (j < right.length) {
    array[k] = right[j];
    j++;
    k++;
    }
    }

    public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Before sorting:");
    printArray(array);
    sort(array);
    System.out.println("After sorting:");
    printArray(array);
    }

    public static void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
    }
    System.out.println();
    }
    }

Quick Sort

  • Algorithm: Quick sort is a divide-and-conquer algorithm that works by selecting a pivot element, partitioning the array around the pivot, and recursively sorting the subarrays.
  • Time Complexity: O(n log n)
  • Space Complexity: O(log n)
  • Example Code:

    public class QuickSort {
    public static void sort(int[] array) {
    quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
    int pivotIndex = partition(array, low, high);
    quickSort(array, low, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, high);
    }
    }

    public static int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
    if (array[j] < pivot) {
    i++;
    // Swap elements
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    }
    }
    // Swap pivot element
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
    }

    public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Before sorting:");
    printArray(array);
    sort(array);
    System.out.println("After sorting:");
    printArray(array);
    }

    public static void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
    }
    System.out.println();
    }
    }

Conclusion

Sorting a Java array is an essential operation that can be performed to organize the elements in a specific order

Unlock the Future: Watch Our Essential Tech Videos!


Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top