How to Sort an Array in Java Without Using the Sort() Method

1. Sort Array in Java Without sort Method
2. Sort Array in Java Without Using the sort() Method - Bubble Sort
3. Sort Array in Java Without Using the sort() Method - Selection Sort
4. Sort Array in Java Without Using the sort() Method - Insertion Sort
5. Sort Array in Java Without Using the sort() Method - Merge Sort
6. Sort Array in Java Without Using the sort() Method - Quicksort
7. Conclusion

Sorting arrays is a fundamental operation in programming, providing a structured arrangement of elements for efficient data retrieval and analysis.

While Java’s built-in method Arrays.sort() offers convenience, understanding manual sorting algorithms is crucial for a comprehensive grasp of programming principles.

Sort Array in Java Without sort Method

In this article, we explore how to sort arrays in Java without using the sort function and delve into five distinct methods—Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quicksort.

Each of these methods showcases diverse approaches to array sorting, shedding light on their unique characteristics and helping developers build a solid foundation in algorithmic understanding.

Sort Array in Java Without Using the sort() Method - Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The algorithm systematically compares and swaps adjacent elements until the entire array is sorted. The use of a boolean variable, swapped, ensures efficient termination when the array is already sorted.

Example:

import java.util.Arrays;

public class BubbleSortExample {
  public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};

    System.out.println("Original Array: " + Arrays.toString(array));

    bubbleSort(array);

    System.out.println("Sorted Array: " + Arrays.toString(array));
  }

  public static void bubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    do {
      swapped = false;
      for (int i = 1; i < n; i++) {
        if (array[i - 1] > array[i]) {
          // Swap elements
          int temp = array[i - 1];
          array[i - 1] = array[i];
          array[i] = temp;
          swapped = true;
        }
      }
    } while (swapped);
  }
}

In the above program, we start with an unsorted array, e.g., array = {64, 34, 25, 12, 22, 11, 90}, and then call the bubbleSort method. The algorithm employs a do-while loop, which continues until no swaps occur in a pass, indicating a sorted array.

In this loop, a boolean variable, swapped, is initialized as false. The inner loop, controlled by a for loop, iterates through the array elements.

If the current element exceeds the next, a swap occurs, and swapped is set to true. This process repeats until a pass through the array is completed without any swaps, signifying the array’s sorted state.

Output:

This output verifies that the bubble sort algorithm successfully sorted the array in ascending order.

In summary, the bubble sort algorithm systematically compares and swaps adjacent elements until the entire array is sorted.

Sort Array in Java Without Using the sort() Method - Selection Sort

Selection Sort is an in-place comparison sorting algorithm that divides the input array into a sorted and an unsorted region. It repeatedly selects the smallest (or largest, depending on the ordering) element from the unsorted region and swaps it with the first element in the unsorted region.

The algorithm systematically identifies the minimum element and swaps it with the current element during each iteration, gradually achieving a sorted array.

Example:

import java.util.Arrays;

public class SelectionSortExample {
  public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};

    System.out.println("Original Array: " + Arrays.toString(array));

    selectionSort(array);

    System.out.println("Sorted Array: " + Arrays.toString(array));
  }

  public static void selectionSort(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[minIndex];
      array[minIndex] = array[i];
      array[i] = temp;
    }
  }
}

In the above program, we begin with an unsorted array, e.g., array = {64, 34, 25, 12, 22, 11, 90}, and then call the selectionSort method. The algorithm utilizes an outer for loop to iterate through each array element.

Within this loop, minIndex is set to the current index i. In the inner loop (ranging from i + 1 to the array’s end), the algorithm identifies the minimum element.

If an element smaller than the one at minIndex is found, minIndex is updated, and a swap occurs between the current element (array[i]) and the minimum element (array[minIndex]). This entire process repeats until the array is sorted.

Output:

This output confirms that the selection sort algorithm successfully sorted the array in ascending order.

In essence, the selection sort algorithm systematically identifies the minimum element and swaps it with the current element during each iteration, gradually achieving a sorted array.

Sort Array in Java Without Using the sort() Method - Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It takes each element from the input array and inserts it into its correct position in the already sorted part of the array.

The algorithm systematically inserts each element into its correct position within the sorted segment of the array.

Example:

import java.util.Arrays;

public class InsertionSortExample {
  public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};

    System.out.println("Original Array: " + Arrays.toString(array));

    insertionSort(array);

    System.out.println("Sorted Array: " + Arrays.toString(array));
  }

  public static void insertionSort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; ++i) {
      int key = array[i];
      int j = i - 1;

      // Move elements of array[0..i-1] that are greater than key
      // to one position ahead of their current position
      while (j >= 0 && array[j] > key) {
        array[j + 1] = array[j];
        j = j - 1;
      }
      array[j + 1] = key;
    }
  }
}

In the above program, we start with an unsorted array, e.g., array = {64, 34, 25, 12, 22, 11, 90}, and invoke the insertionSort method. The algorithm employs an outer for loop starting from the second element (i = 1) since a single element is initially considered sorted.

Within this loop, the value of the current element (array[i]) is assigned to key, and j is set to the previous index (i - 1). The next step involves a while loop to compare the key with elements in the sorted portion of the array (array[0..i-1]).

If an element is greater than the key, it shifts to the right, creating space for the key. Once the correct position for the key is determined, it seamlessly integrates into the sorted sequence.

This entire process repeats until the entire array is sorted.

Output:

This output confirms that the insertion sort algorithm successfully sorted the array in ascending order.

Essentially, insertion sort systematically inserts each element into its correct position within the sorted segment of the array.

Sort Array in Java Without Using the sort() Method - Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted array.

The algorithm uses a divide-and-conquer approach, recursively dividing the array until each sub-array has one element. The merging process ensures elements are placed in order.

Example:

import java.util.Arrays;

public class MergeSortExample {
  public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};

    System.out.println("Original Array: " + Arrays.toString(array));

    mergeSort(array);

    System.out.println("Sorted Array: " + Arrays.toString(array));
  }

  public static void mergeSort(int[] array) {
    if (array.length > 1) {
      int mid = array.length / 2;
      int[] left = Arrays.copyOfRange(array, 0, mid);
      int[] right = Arrays.copyOfRange(array, mid, array.length);

      mergeSort(left);
      mergeSort(right);

      merge(array, left, right);
    }
  }

  private static void merge(int[] array, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        array[k++] = left[i++];
      } else {
        array[k++] = right[j++];
      }
    }

    while (i < left.length) {
      array[k++] = left[i++];
    }

    while (j < right.length) {
      array[k++] = right[j++];
    }
  }
}

In the above program, we start with an unsorted array, e.g., array = {64, 34, 25, 12, 22, 11, 90}, and call mergeSort. The algorithm uses a divide-and-conquer approach, recursively dividing the array until each sub-array has one element.

The merging process in the merge method compares and combines sorted sub-arrays, ensuring elements are placed in order. This process repeats until the entire array is sorted.

Output:

The output confirms that the merge sort algorithm successfully sorted the array in ascending order.

In essence, merge sort systematically divides, sorts, and merges the array elements to achieve a fully sorted array.

Sort Array in Java Without Using the sort() Method - Quicksort

Quicksort is another divide-and-conquer algorithm that partitions the input array into smaller subarrays, recursively sorts each subarray, and combines them to form a sorted array.

Quicksort efficiently partitions and sorts the array through recursive calls and strategic element swaps.

Example:

import java.util.Arrays;

public class QuicksortExample {
  public static void main(String[] args) {
    int[] array = {64, 34, 25, 12, 22, 11, 90};

    System.out.println("Original Array: " + Arrays.toString(array));

    quicksort(array, 0, array.length - 1);

    System.out.println("Sorted Array: " + Arrays.toString(array));
  }

  public static void quicksort(int[] array, int low, int high) {
    if (low < high) {
      int partitionIndex = partition(array, low, high);

      quicksort(array, low, partitionIndex - 1);
      quicksort(array, partitionIndex + 1, high);
    }
  }

  private 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++;

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }

    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    return i + 1;
  }
}

In the above program, we start with an unsorted array, e.g., array = {64, 34, 25, 12, 22, 11, 90}, and invoke quicksort on the entire array (bounds: 0 to array.length - 1). The quicksort algorithm, checking if low < high, partitions the array.

The pivot is chosen (typically the last element), and elements are rearranged so that those less than the pivot are on the left, and those greater are on the right. Recursive quicksort calls are made on both partitions, completing the sorting process.

Output:

The output confirms that the quicksort algorithm successfully sorting arrays in ascending order.

In summary, quicksort efficiently partitions and sorts the array through recursive calls and strategic element swaps.

Conclusion

Various methods of sorting arrays in Java discussed—Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quicksort—offer varying levels of simplicity and efficiency in Java.

Each algorithm has its strengths and use cases, providing a diverse toolkit for developers. Mastering these sorting concepts not only enhances your understanding of fundamental programming principles but also equips you with valuable skills to tackle different sorting challenges in Java.

Whether opting for simplicity, efficiency, or a balance of both, the knowledge gained from these examples lays a solid foundation for navigating and implementing sorting algorithms in real-world scenarios.