code.kerkeslager.com Git - sandbox/blob - sort.py

   1 def swap(xs, a, b):
   2     swap.counter += 1
   3     temp = xs[a]
   4     xs[a] = xs[b]
   5     xs[b] = temp
   6
   7 swap.counter = 1
   8
   9 def merge(xs, start, divide, end):
  10     if divide < end:
  11         while start < divide and xs[start] < xs[divide]:
  12             start += 1
  13
  14         if start == divide:
  15             return
  16
  17     else:
  18         return
  19
  20     # if start < divide is implied by the most recent check
  21     while divide < end and xs[divide - 1] < xs[end - 1]:
  22         end -= 1
  23
  24     if divide == end:
  25         return
  26
  27     swap(xs, start, divide)
  28     start += 1
  29
  30     i = start
  31     j = divide + 1
  32
  33     while i < divide and j < end:
  34         if xs[i] < xs[j]:
  35             i += 1
  36         else:
  37             swap(xs, i, j)
  38             i += 1
  39             j += 1
  40
  41     # 100K
  42     #merge(xs, start, i, divide)
  43     #merge(xs, divide, j, end)
  44     #merge(xs, start, divide, end)
  45
  46     # 100K
  47     #merge(xs, start, i, divide)
  48     #merge(xs, start, divide, j)
  49     #merge(xs, start, j, end)
  50
  51     # 80K
  52     #merge(xs, i, divide, j)
  53     #merge(xs, start, i, j)
  54     #merge(xs, start, j, end)
  55
  56     # 80K
  57     #merge(xs, i, divide, j)
  58     #merge(xs, i, j, end)
  59     #merge(xs, start, i, end)
  60
  61     # 80K
  62     merge(xs, divide, j, end)
  63     merge(xs, i, divide, end)
  64     merge(xs, start, i, end)
  65
  66 def sort(xs):
  67     divisions = [0]
  68
  69     for i in range(len(xs) - 1):
  70         if xs[i] > xs[i + 1]:
  71             divisions.append(i + 1)
  72
  73     divisions.append(len(xs))
  74
  75     while len(divisions) > 2:
  76         new_divisions = divisions[:]
  77
  78         for i in range(1,len(divisions) - 1,2):
  79             merge(xs, divisions[i - 1], divisions[i], divisions[i + 1])
  80             new_divisions.remove(divisions[i])
  81
  82         divisions = new_divisions
  83
  84 xs = [i for i in range(1000)]
  85 import random
  86 random.shuffle(xs)
  87
  88 print(xs)
  89
  90 sort(xs)
  91
  92 print(xs)
  93
  94 print('Swaps:', swap.counter)
  95
  96 def group_swap(xs, start, divide, end):
  97     if start == divide or divide == end:
  98         return
  99
 100     width = divide - start
 101     for i in range(start, end):
 102         swap(xs, i, i + width if i + width < end else start + i + width - end)
 103
 104 print(xs)