Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def quick_sort(line, l, r):
- if r - l > 50:
- pivot = find_median(line, l, r)
- i, j = l+1, r-2
- while True:
- while line[i] < pivot:
- i += 1
- while line[j] > pivot:
- j -= 1
- if i < j:
- line[i], line[j] = line[j], line[i]
- i += 1
- j -= 1
- else:
- break
- line[i], line[r-1] = line[r-1], line[i]
- quick_sort(line, l, i-1)
- quick_sort(line, i+1, r)
- else:
- if r == l + 1:
- if line[l] > line[r]:
- line[l], line[r] = line[r], line[l]
- def find_median(line, l, r):
- center = (l + r) / 2
- if line[l] > line[r]:
- line[l], line[r] = line[r], line[l]
- if line[l] > line[center]:
- line[l], line[center] = line[center], line[l]
- if line[center] > line[r]:
- line[center], line[r] = line[r], line[center]
- line[center], line[r-1] = line[r-1], line[center]
- return line[r-1]
- def insert_sort_index(line, l, r):
- if l < r:
- for idi in range(l+1, r+1):
- data = line[idi]
- for idj in range(idi+1)[::-1]:
- if idj >= l+1 and line[idj-1] > data:
- line[idj] = line[idj-1]
- else:
- break
- line[idj] = data
- def quick_sort(line, l, r):
- if r - l > 1:
- pivot = find_median(line, l, r)
- i, j = l+1, r-2
- while True:
- while line[i] < pivot:
- i += 1
- while line[j] > pivot:
- j -= 1
- if i < j:
- line[i], line[j] = line[j], line[i]
- i += 1
- j -= 1
- else:
- break
- line[i], line[r-1] = line[r-1], line[i]
- quick_sort(line, l, i-1)
- quick_sort(line, i+1, r)
- else:
- insert_sort_index(line, l, r)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement