Mercurial > lbo > hg > juliaplay
view python/sorting.py @ 40:5e3662b65004 default tip
Land/water find peak problem
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 03 Apr 2023 22:04:42 +0200 |
parents | 00f57653128a |
children |
line wrap: on
line source
import copy def partition(a, fro, to): if fro >= to: return fro # Hoare partitioning scheme mid = (fro+to) // 2 piv = a[mid] lo, hi = fro-1, to+1 while True: lo += 1 while a[lo] < piv: lo += 1 hi -= 1 while a[hi] > piv: hi -= 1 if lo >= hi: return hi a[lo], a[hi] = a[hi], a[lo] def quicksort(a, fro=0, to=-1): if to < 0: to = len(a) - 1 if to-fro <= 0: return mid = partition(a, fro, to) quicksort(a, fro, mid) quicksort(a, mid+1, to) def mergehalves(a, lo, mid, hi, aux): i, l, r = 0, lo, mid while i <= hi-lo: if l >= mid: aux[i] = a[r] r += 1 elif r > hi: aux[i] = a[l] l += 1 else: if a[l] < a[r]: aux[i] = a[l] l += 1 else: aux[i] = a[r] r += 1 i += 1 a[lo:hi+1] = aux[0:i] def mergesort(a, lo=0, hi=-1, aux=None): aux = aux or copy.copy(a) hi = hi if hi > 0 else len(a)-1 if hi == lo: return elif hi-lo == 1: if a[lo] > a[hi]: a[lo], a[hi] = a[hi], a[lo] return else: mid = (lo+hi)//2 mergesort(a, lo, mid, aux) mergesort(a, mid, hi, aux) mergehalves(a, lo, mid, hi, aux) def children(i): return (2*i, 2*i+1) def swap(a, i, j): a[i], a[j] = a[j], a[i] def sink(a, i, N=-1): N = N if N >= 0 else len(a) while 2*i < N: c1, c2 = children(i) if c2 >= N: if a[i] < a[c1]: swap(a, i, c1) i = c1 else: sm, la = (c1, c2) if a[c1] < a[c2] else (c2, c1) if a[i] < a[la]: swap(a, i, la) i = la def buildheap(a): i = len(a) // 2 while i > 0: sink(a, i) i -= 1 def heapsort(a): a = [0] + a buildheap(a) i = len(a)-1 while i > 0: swap(a, 1, i) i -= 1 sink(a, 1, i) return a