GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — algorithms/algorithms/sort/bitonic_sort.py at master · oldmonad/algorithms Expand file tree/ Copy pathbitonic_sort.pyMore file actions 43 lines (34 loc) · 1.37 KB / Copy pathbitonic_sort.pyFile metadata and controls43 lines (34 loc) · 1.37 KB 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 def bitonic_sort(arr, reverse=False): """ bitonic sort is sorting algorithm to use multiple process, but this code not containing parallel process It can sort only array that sizes power of 2 It can sort array in both increasing order and decreasing order by giving argument true(increasing) and false(decreasing) Worst-case in parallel: O(log(n)^2) Worst-case in non-parallel: O(nlog(n)^2) reference: https://en.wikipedia.org/wiki/Bitonic_sorter """ def compare(arr, reverse): n = len(arr)//2 for i in range(n): if reverse != (arr[i] > arr[i+n]): arr[i], arr[i+n] = arr[i+n], arr[i] return arr def bitonic_merge(arr, reverse): n = len(arr) if n <= 1: return arr arr = compare(arr, reverse) left = bitonic_merge(arr[:n // 2], reverse) right = bitonic_merge(arr[n // 2:], reverse) return left + right #end of function(compare and bitionic_merge) definition n = len(arr) if n <= 1: return arr # checks if n is power of two if not (n and (not(n & (n - 1))) ): raise ValueError("the size of input should be power of two") left = bitonic_sort(arr[:n // 2], True) right = bitonic_sort(arr[n // 2:], False) arr = bitonic_merge(left + right, reverse) return arr |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |