Problem

Sort items using selection sort with stacks.

Examples

Example 1:

Input: stack = [4,2,3,1]
Output: [1, 2, 3, 4]

Solution

Method 1 - Selection Sort

The selection sort algorithm with stacks works similarly to the linked list implementation. It involves finding the largest item from the unsorted section and moving it to the sorted section. By using a temporary stack, we can keep track of the largest item and rearrange the remaining items efficiently.

Similar to the insertion sort algorithm, the original stack holds items in two sections. The items at the bottom of the stack are sorted, while the items at the top are unsorted. Initially, all items are in the unsorted section. The algorithm uses a second temporary stack. For each position in the stack, the algorithm moves all unsorted items to the temporary stack while keeping track of the largest item. After moving all unsorted items to the temporary stack, the program pushes the largest item found onto the original stack. It then moves all unsorted items from the temporary stack back to the original stack.

Code

Java
class Solution {
    public void stackSelectionSort(Stack<Integer> items) {
        Stack<Integer> tempStack = new Stack<>();
        int numItems = items.size();
        
        for (int i = 0; i < numItems; i++) {
            int largestItem = Integer.MIN_VALUE;
            // Move items to tempStack and find the largest item
            for (int j = 0; j < numItems - i; j++) {
                int item = items.pop();
                if (item > largestItem) {
                    largestItem = item;
                }
                tempStack.push(item);
            }
            // Put the largest item back into items stack
            items.push(largestItem);
            // Move other items back to items stack excluding the largest item
            boolean largestMoved = false;
            while (!tempStack.isEmpty()) {
                int item = tempStack.pop();
                if (item == largestItem && !largestMoved) {
                    largestMoved = true;
                    continue;
                }
                items.push(item);
            }
        }
    }
}
Python
class Solution:
    def stackSelectionSort(self, items: List[int]) -> List[int]:
        n = len(items)
        for i in range(n):
            largest_item = float('-inf')
            temp_stack = []
            for _ in range(n - i):
                item = items.pop()
                if item > largest_item:
                    largest_item = item
                temp_stack.append(item)
            items.append(largest_item)
            largest_moved = False
            while temp_stack:
                item = temp_stack.pop()
                if item == largest_item and not largest_moved:
                    largest_moved = True
                    continue
                items.append(item)
        return items

Complexity

  • ⏰ Time complexity: O(n^2), where N is the number of items in the stack. This complexity arises because, for each position in the stack, the unsorted items must be moved twice, and the number of unsorted items decreases with each iteration.
  • 🧺 Space complexity: O(n), due to the use of an additional temporary stack to hold the unsorted items.