diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/sorting.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/sorting.py | 60 |
1 files changed, 60 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/sorting.py b/AlgoDesignAndTechniqueEdxPython/sources/sorting.py new file mode 100644 index 0000000..5608c03 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/sorting.py @@ -0,0 +1,60 @@ +# Uses python3 +import sys +import random + + +def partition3(a, l, r): + x = a[l] + j = l + dupCount = 0 + biggerNumCount = 0 + + for i in range(l + 1, r + 1): + if a[i] < x: + t = a[i] + a[j] = t + t = a[i - biggerNumCount] + a[i] = t + a[i - biggerNumCount] = x + j = j + 1 + continue + if a[i] == x: + t = a[j + dupCount + 1] + a[i] = t + a[j + dupCount + 1] = x + dupCount = dupCount + 1 + continue + biggerNumCount = biggerNumCount + 1 + return (j, j + dupCount) + + +def partition2(a, l, r): + x = a[l] + j = l; + for i in range(l + 1, r + 1): + if a[i] <= x: + j += 1 + a[i], a[j] = a[j], a[i] + a[l], a[j] = a[j], a[l] + return j + + +def randomized_quick_sort(a, l, r): + if l >= r: + return + k = random.randint(l, r) + a[l], a[k] = a[k], a[l] + # use partition3 +# m = partition2(a, l, r) + (m1, m2) = partition3(a, l, r) + randomized_quick_sort(a, l, m1 - 1); + randomized_quick_sort(a, m2 + 1, r); + + +if __name__ == '__main__': + input = sys.stdin.read() + n, *a = list(map(int, input.split())) + randomized_quick_sort(a, 0, n - 1) + for x in a: + print(x, end=' ') + |