Preparing for Java Interview?

My books Grokking the Java Interview and Grokking the Spring Boot Interview can help

Download PDF

Sunday, September 24, 2023

3 ways to sort an ArrayList in Java without using sort() method - Example Tutorial

Hello guys, you can sort an ArrayList in Java without using the sort() method from the Collections class or the List interfaces' sort() method by implementing your own sorting algorithm. You can use any sorting algorithm like bubble sort, insertion sort, selection sort, quicksort, or merge sort to sort your ArrayList without using sort() method from Collection API. In the past, I have even showed multiple examples of sorting List in Java in both increasing and decreasing order. We have even seen example of sorting List in custom order using Comparator and in this article I will show you multiple way to sort an ArrayList without using Java Collection API. 

Sorting is a fundamental operation in computer science and programming, allowing us to organize data in a meaningful and efficient way. 

In Java, the ArrayList is a versatile and commonly used data structure, but you might wonder how to sort its elements without relying on the convenient sort() methods provided by the Collections class or the List interface. 

In this article, I will show you alternative approaches to sort an ArrayList in Java, demonstrating the use of sorting algorithms like bubble sort, quicksort, and merge sort. 

By understanding these techniques, you'll not only gain insight into how sorting works under the hood but also be better equipped to handle custom sorting requirements in your Java programs.


3 ways to sort an ArrayList in Java without using List.sort() or Collections.sort() method

Now coming back to the question of sorting a List without using List.sort() method of JDK 8, one of the simplest sorting algorithms you can use is the bubble sort. 

1. Using Bubble Sort Algorithm

Here's an example of how to sort an ArrayList using the bubble sort algorithm:

import java.util.ArrayList;

public class ArrayListSortWithoutCollectionsSort {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(5);
        arrayList.add(2);
        arrayList.add(9);
        arrayList.add(1);
        arrayList.add(5);
        
        // Call the custom sort method
        bubbleSort(arrayList);

        // Print the sorted ArrayList
        System.out.println(arrayList);
    }

    public static void bubbleSort(ArrayList<Integer> list) {
        int n = list.size();
        boolean swapped;
        
        do {
            swapped = false;
            for (int i = 1; i < n; i++) {
                if (list.get(i - 1) > list.get(i)) {
                    // Swap elements
                    int temp = list.get(i - 1);
                    list.set(i - 1, list.get(i));
                    list.set(i, temp);
                    swapped = true;
                }
            }
        } while (swapped);
    }
}

In this example, I have defined a custom bubbleSort method that takes an ArrayList of integers as an argument. The method iteratively compares adjacent elements and swaps them if they are out of order. The process continues until no more swaps are needed, indicating that the list is sorted.

Keep in mind that bubble sort is not the most efficient sorting algorithm for large lists, as it has a time complexity of O(n^2)

For larger lists, more efficient sorting algorithms like quicksort or mergesort are preferred. However, this example demonstrates how to sort an ArrayList without using the built-in sort() methods from Lists and Collections classes. 

Now, let's see an example of sorting ArrayList using quicksort algorithm

2. Using QuickSort Algorithm

Quicksort is a more efficient sorting algorithm compared to bubble sort. Here's an example of how to sort an ArrayList using the quicksort algorithm in Java:

import java.util.ArrayList;

public class ArrayListSortWithQuicksort {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(5);
        arrayList.add(2);
        arrayList.add(9);
        arrayList.add(1);
        arrayList.add(5);

        // Call the custom sort method
        quickSort(arrayList, 0, arrayList.size() - 1);

        // Print the sorted ArrayList
        System.out.println(arrayList);
    }

    public static void quickSort(ArrayList<Integer> list, int low, int high) {
        if (low < high) {
            // Partition the list into two sublists
            int pivotIndex = partition(list, low, high);

            // Recursively sort each sublist
            quickSort(list, low, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, high);
        }
    }

    public static int partition(ArrayList<Integer> list, int low, int high) {
        int pivot = list.get(high);
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (list.get(j) < pivot) {
                i++;
                // Swap elements at i and j
                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }

        // Swap the pivot element with the element at (i + 1)
        int temp = list.get(i + 1);
        list.set(i + 1, list.get(high));
        list.set(high, temp);

        return i + 1;
    }
}

In this example, I have defined a custom quickSort method that takes an ArrayList of integers, along with the indices representing the range of elements to sort (low and high). The partition method is used to divide the list into two sublists and returns the index where the pivot element ends up.

The quickSort method recursively sorts each sublist until the entire list is sorted. Quicksort has an average time complexity of O(n log n), making it more efficient than bubble sort for larger lists.

If you are thinking is there any other faster way to sort the ArrayList without using sort() method? then answer is Yes, merge sort, which we are going to see next. 

By the way, if you have trouble understanding quicksort algorithm, here is a nice diagram which shows how quicksort works step by step:





3. Using Merge sort algorithm

As I said there are more efficient sorting algorithms then quicksort which you can use to sort an ArrayList in Java without using the sort() method from the Collections class or the List interface's sort() method. 

Two commonly used efficient sorting algorithms are Merge Sort and Tim Sort (a hybrid sorting algorithm that combines elements of Merge Sort and Insertion Sort). 

Here, I'll provide an example using Merge Sort:

import java.util.ArrayList;

public class ArrayListSortWithMergeSort {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(5);
        arrayList.add(2);
        arrayList.add(9);
        arrayList.add(1);
        arrayList.add(5);

        // Call the custom sort method
        mergeSort(arrayList);

        // Print the sorted ArrayList
        System.out.println(arrayList);
    }

    public static void mergeSort(ArrayList<Integer> list) {
        int size = list.size();
        if (size < 2) {
            return; // List is already sorted if it contains 0 or 1 element
        }

        int mid = size / 2;
        ArrayList<Integer> left = new ArrayList<>(list.subList(0, mid));
        ArrayList<Integer> right = new ArrayList<>(list.subList(mid, size));

        // Recursively sort the left and right sublists
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted sublists
        merge(list, left, right);
    }

    public static void merge(ArrayList<Integer> list, ArrayList<Integer> left, 
            ArrayList<Integer> right) {
        int leftSize = left.size();
        int rightSize = right.size();
        int i = 0, j = 0, k = 0;

        while (i < leftSize && j < rightSize) {
            if (left.get(i) <= right.get(j)) {
                list.set(k++, left.get(i++));
            } else {
                list.set(k++, right.get(j++));
            }
        }

        while (i < leftSize) {
            list.set(k++, left.get(i++));
        }

        while (j < rightSize) {
            list.set(k++, right.get(j++));
        }
    }
}

That's all about how to sort an ArrayList in Java without using the sort() method of Collection API. In this article you have learned three ways to sort ArrayList using primary sorting algorithm like bubble sort, quick sort, and merge sort which also doesn't use List.sort() or Collections.sort() method from Java's collection API. 

Out of these 3, merge sort is the most efficient and should be used to sort large list of integers

In the world of Java programming, mastering the art of sorting an ArrayList without using  built-in sort() methods of List and Collections class opens up a lot of possibilities. 

Whether you opt for the simplicity of bubble sort, the efficiency of quicksort, or the elegance of merge sort, the choice of sorting algorithm depends on the specific needs of your application. 

While Java's standard libraries provide powerful sorting utilities, there's undeniable value in comprehending the inner workings of these algorithms. 

Armed with the knowledge gained from this tutorial, you are better equipped to tackle custom sorting challenges from coding interviews and optimize your Java programs for various scenarios. 

Other Java Articles and Tutorials you may like:
  • How to sort the map by keys in Java 8? (example)
  • How to sort the may by values in Java 8? (example)
  • What is the default method in Java 8? (example)
  • Top 5 Courses to learn Java 8 in depth (courses)
  • How to join String in Java 8 (example)
  • Top 5 Courses to become a full-stack Java developer (courses)
  • How to use filter() method in Java 8 (tutorial)
  • How to format/parse the date with LocalDateTime in Java 8? (tutorial)
  • How to use Stream class in Java 8 (tutorial)
  • 10 Free Courses to learn Spring Framework for Beginners (courses)
  • How to convert List to Map in Java 8 (solution)
  • Difference between abstract class and interface in Java 8? (answer)
  • 20 Examples of Date and Time in Java 8 (tutorial)
  • How to use peek() method in Java 8 (example)
  • 10 examples of Options in Java 8? (example)
  • 5 Courses to learn Functional Programming in Java (courses)

Thanks for reading this article so far and let me know if you have any questions or request. If you face any problem running this program do let me know in comments and I will help you with the setup. 

And, lastly one question for you? How may List implementations are available in Java Collection API except ArrayList? Let me know your answers in comments. 

2 comments :

Anonymous said...

I follow a simple rule - just use merge sort and you will be ok with most of the input list.

Vivek said...

Thank you so much for this awesome information.

Post a Comment