Better way to sort a stack / algorithm improvement + space & time reasoning

Question

I am trying to figure out an optimal solution for the following problem:

Given a stack of 20 integers, sort the stack so that only values in range from 1 to 4 would remain in ascending order. You may only move one value at a time.

I have implemented an iterative & a recursive quick sort & now I'm looking for more optimal solutions. I have come up with the following so far, which runs on average approx 10x faster over 10k iterations. I am struggling to reason about space & time complexity & I'm sure there's plenty of room for a better solution.

Which sorts should I be considering? Which data types should I be considering? What's the best possible worse case time complexity O(?) for the given problem?

Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(3);
stack.push(2);
stack.push(1);
stack.push(3);
stack.push(5);
stack.push(3);
stack.push(1);
stack.push(4);
stack.push(7);
        
HashMap<Integer, Integer> map = new HashMap<>();
map.put(1, 0);
map.put(2, 0);
map.put(3, 0);
map.put(4, 0);
        
int popped;
        
while (!stack.isEmpty()) {
    popped = stack.pop();
            
    if (map.containsKey(popped)) {
        map.put(popped, map.get(popped) + 1);
    }
}
        
while (map.get(4) > 0) {
    stack.push(4);
    map.put(4, map.get(4) - 1);
}
        
while (map.get(3) > 0) {
    stack.push(3);
    map.put(3, map.get(3) - 1);
}
        
while (map.get(2) > 0) {
    stack.push(2);
    map.put(2, map.get(2) - 1);
}
        
while (map.get(1) > 0) {
    stack.push(1);
    map.put(1, map.get(1) - 1);
}

Answer 1

You're reinventing the Counting sort algorithm, which runs in linear time O(n).

Instead of a HashMap you can use a plain array. And you definitely don't need this swarm of redundant while-loops.

Here's the description of the algorithm in pseudocode:

function CountingSort(input, k)

count ← array of k + 1 zeros
output ← array of same length as input

for i = 0 to length(input) - 1 do      // STEP 1
    j = key(input[i])
    count[j] = count[j] + 1

for i = 1 to k do                      // we don't need this step
    count[i] = count[i] + count[i - 1]

for i = length(input) - 1 down to 0 do // STEP 2
    j = key(input[i])
    count[j] = count[j] - 1
    output[count[j]] = input[i]

return output

For your use-case you don't need the second for-loop where there the cumulative frequency is being calculated.

So to address the problem, we need to take the following step:

• STEP 1 is to generate a histogram of frequencies.

• STEP 2 is to iterate over frequencies backwards (i.e. starting from the very last index of the array) and push the values equal to index + minValue (in this case 1). Each value should be pushed the number of times equal to its frequency.

Here's an implementation:

final int min = 1;
final int max = 4;

int[] freq = new int[max - min + 1]; // histogram, i.e. array of frequencies of values in range [min, max]
        
// STEP 1: generating a histogram

while (!stack.isEmpty()) {
    int next = stack.pop();
    if (next >= min && next <= max) freq[next - min]++; // calculating the frequency of each element
}
    
// STEP 2: populating the stack in sorted order
        
for (int i = freq.length - 1; i >= 0; i--) {
    while (freq[i] > 0) {
        stack.push(i + min);
        freq[i]--;
    }
}

return stack;

If you want to use the HashMap, fine, you can apply the same algorithm, just don't create redundant loops.

Regarding the time complexity in both cases it would be linear as I've said before. Array would perform slightly better, but more importantly it gives you a better feeling of the internal mechanics of the algorithm.

final int min = 1;
final int max = 4;
        
Map<Integer, Integer> freq = new HashMap<>(); // histogram, i.e. array of frequencies of values in range [min, max]

// STEP 1: generating a histogram
        
while (!stack.isEmpty()) {
    int next = stack.pop();
    if (next >= min && next <= max) 
        freq.merge(next, 1, Integer::sum); // calculating the frequency of each element
}
    
// STEP 2: populating the stack in sorted order
    
for (int i = max; i >= min; i--) {
    int count = freq.get(i);
    while (count > 0) {
        stack.push(i + min);
        count--;
    }
}
        
return stack;

Sidenote: class java.util.Stack is legacy and not encouraged to be used. When you need an implementation of Stack data structure in Java, use classes that implement Deque interface.