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

Carvia Tech | May 19, 2019 | 2 min read | 218 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 algorithms…

  1. Integer Sorting Techniques : Integer Sorting

  2. Sorting Algorithms : Sorting Algorithms

Algorithm Implementation

Create a array of size 9 and 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. In Order to print the output just traverse the above created array.

/src/main/java/foo/BucketSort.java
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]++;
        }
        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 & lt; sort.length; i++) {
            for (int j = 0; j & lt; sort[i]; j++) {
                System.out.println(i);
            }
        }
    }
}
Output
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).


Java Coding Challenges:
  1. How to check if the given number is palindrome in Java
  2. Check if the given number is Armstrong Number in Java
  3. How will you check if a given sentence is a pangram
  4. Calculate factorial of a number in Java using recursion
  5. Java program to check if two strings are anagrams
  6. Create anagram buckets from a given input array of words
  7. Find two numbers of which the product is maximum in an array
See all articles in Java Coding Challenges
Top articles in this category:
  1. How will you increment each element of an Integer array, using parallel operation
  2. Fail-Safe vs Fail-Fast Iterator in Java Collections Framework
  3. What is AtomicInteger class and how it works internally
  4. What is ThreadLocal in Java, where will you use this class
  5. What is Immutable Class. Why would you choose it? How would you make a class immutable?
  6. Difference between Comparable and Comparator in Java
  7. Removing elements while iterating over a Java Collection



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 month ago


Recommended books for interview preparation:

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