Skip to content

Instantly share code, notes, and snippets.

@eirture
Created November 16, 2018 02:57
Show Gist options
  • Save eirture/6d87a6fd32d1f9577057327c6c9e9f3b to your computer and use it in GitHub Desktop.
Save eirture/6d87a6fd32d1f9577057327c6c9e9f3b to your computer and use it in GitHub Desktop.
quicksort by Python
#!/usr/bin/env python
# coding=utf-8
import random
def sort(a, low, height):
i = a[height]
while low < height:
while low < height and a[low] <= i:
low += 1
a[height] = a[low]
while low < height and a[height] >= i:
height -= 1
a[low] = a[height]
a[height] = i
return height
def do_sort(a, low, height):
if low < height:
p = sort(a, low, height)
do_sort(a, low, p - 1)
do_sort(a, p + 1, height)
def b_find(a, l, h, value):
if l > h:
return -1
i = (l + h) / 2
if a[i] == value:
return i
if a[i] < value:
return b_find(a, i + 1, h, value)
return b_find(a, l, i - 1, value)
def main():
a = [random.randint(0, 100) for _ in range(0, 20)]
print(a)
v = a[3]
do_sort(a, 0, len(a) - 1)
print(a)
print(b_find(a, 0, len(a) - 1, v))
print(v, a.index(v))
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment