Given a collection of 1 million integers, all ranging between 1 to 9, sort them in Big O(n) time

Carvia Tech | November 22, 2020 | 2 min read | 669 views | Java Coding Challenges algorithm-datastructures


This is a typical Integer Sorting problem with a constraint that the number range to sort is very limited in spite 1 million total entries. Integer Sorting with limited range is achieved efficiently with Bucket Sorting.

Bucket Sorting Algorithm

Bucket sort, counting sort, radix sort, and van Emde Boas tree sorting all work best when the key size is small; for large enough keys, they become slower than comparison sorting algorithm.

Algorithm Steps

  1. Create a array of size 9

  2. At each index store the occurrence count of the respective integers. Doing this will achieve this sorting with time complexity of Big O(n) and even the memory requirements are minimized.

  3. In Order to print the output just traverse the above created array.

Bucket Sort 0-9
public class BucketSort {
    public int[] sort(int[] array, int min, int max) {
        int range = max - min + 1;
        int[] result = new int[range];
        for (int i: array) {
            result[i]++;    (1)
        }
        return result;
    }
}

public class BucketSortTest {

    @Test
    public void testBucketSortFor1To9() {
        int[] array = {
            2, 1, 5, 1, 2, 3, 4, 3, 5, 6, 7, 8, 5, 6, 7, 0
        };
        int[] sort = new BucketSort().sort(array, 0, 8);

        for (int i = 0; i < sort.length; i++) {
            for (int j = 0; j < sort[i]; j++) {
                System.out.println(i);
            }
        }
    }
}
1 Storing the count of occurrences for each number
Program output:
0,1,1,2,2,3,3,4,5,5,5,6,6,7,7,8
Time Complexity
Big O(n)

Notes

In a very similar fashion we can sort millions of people with their age (0-130).


Buy my ebook for complete question bank

Most of these questions has been answered in my eBook "Cracking the Core Java Interview" updated on June 2018, that you can buy from this link:

Buy from Shunya (DRM Free PDF download with updates)

Java Coding Challenges:
  1. Reverse position of words in a string using recursion
  2. Check if the given string is palindrome
  3. Find two numbers of which the product is maximum in an array
  4. Check a number is Prime: Java Coding Problem
  5. Create anagram buckets from a given input array of words
  6. Anagrams string checker in Java
  7. Reverse a string using recursion in Java
See all articles in Java Coding Challenges
Top articles in this category:
  1. Factorial of a large number in Java BigInteger
  2. How will you increment each element of an Integer array, using parallel operation
  3. Discuss internals of a ConcurrentHashmap (CHM) in Java
  4. What will happen if we don't synchronize getters/accessors of a shared mutable object in multi-threaded applications
  5. Difference between HashMap, LinkedHashMap and TreeMap
  6. What is difference between Vector and ArrayList, which one shall be preferred
  7. Fail-Safe vs Fail-Fast Iterator in Java Collections Framework


Find more on this topic:
Core Java image
Core Java

Core Java - OOP Concepts, Garbage Collection, Multi-threading, Collections Framework, Java 8 Features, Lambda Functions, Streams.

Last updated 1 week ago


Recommended books for interview preparation:
Buy interview books

Java & Microservices interview refresher for experienced developers.


This website uses cookies to ensure you get the best experience on our website. more info