Code2020/StackSorting.py at master · greatsci/Code2020 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# How to sort numbers with two stacks? (with duplicate values)

def stackSorting(input):
    if not input:
        return None

    a = []
    b = []
    # Build initial stack a from input
    for ele in input:
        a.append(ele)
    value_min = a[-1]
    count_min = 0
    # Find min value in a and use b as buffer + destination
    while a:
        step = len(a)
        for i in range(step):
            item = a.pop()
            if item < value_min:
                value_min = item
                count_min = 1
            elif item == value_min:
                count_min += 1
            b.append(item)
        for j in range(step):
            item = b.pop()
            if item != value_min:
                a.append(item)
        for k in range(count_min):
            b.append(value_min)
        if a:
            value_min = a[-1]
            count_min = 0
    return b
# T:O(n^2) S:O(n)

print(stackSorting([5, 1, 1, 2]))


# Ref: https://www.geeksforgeeks.org/sort-stack-using-temporary-stack/
#
# # Python program to sort a
# # stack using auxiliary stack.
#
# # This function return the sorted stack
# def sortStack(stack):
#     tmpStack = createStack()
#     while (isEmpty(stack) == False):
#
#         # pop out the first element
#         tmp = top(stack)
#         pop(stack)
#
#         # while temporary stack is not
#         # empty and top of stack is
#         # greater than temp
#         while (isEmpty(tmpStack) == False and
#                int(top(tmpStack)) < int(tmp)):
#             # pop from temporary stack and
#             # push it to the input stack
#             push(stack, top(tmpStack))
#             pop(tmpStack)
#
#             # push temp in tempory of stack
#         push(tmpStack, tmp)
#
#     return tmpStack
#
#
# # Below is a complete running
# # program for testing above
# # function.
#
# # Function to create a stack.
# # It initializes size of stack
# # as 0
# def createStack():
#     stack = []
#     return stack
#
#
# # Function to check if
# # the stack is empty
# def isEmpty(stack):
#     return len(stack) == 0
#
#
# # Function to push an
# # item to stack
# def push(stack, item):
#     stack.append(item)
#
#
# # Function to get top
# # item of stack
# def top(stack):
#     p = len(stack)
#     return stack[p - 1]
#
#
# # Function to pop an
# # item from stack
# def pop(stack):
#     # If stack is empty
#     # then error
#     if (isEmpty(stack)):
#         print("Stack Underflow ")
#         exit(1)
#
#     return stack.pop()
#
# # Function to print the stack
# def prints(stack):
#     for i in range(len(stack) - 1, -1, -1):
#         print(stack[i], end=' ')
#     print()
#
#
# # Driver Code
# stack = createStack()
# push(stack, str(34))
# push(stack, str(3))
# push(stack, str(31))
# push(stack, str(98))
# push(stack, str(92))
# push(stack, str(23))
#
# print("Sorted numbers are: ")
# sortedst = sortStack(stack)
# prints(sortedst)
#
# # This code is contributed by
# # Prasad Kshirsagar