text: import random
  import time
  from collections import deque
  import threading
  
  
  class Sort:
      # TODO comb sort / radix sort
      def __init__(self):
          self.queue = deque()  # appendleft, pop
          self.data_lock = threading.Lock()
          self.data = []
          self.algorithm = None
          self.run_lock = threading.Lock()
          self.run = False
  
      def clear(self):
          self.run = False
          self.queue.clear()
  
      def set_algorithm(self, name):
          self.algorithm = name
  
      def get_data(self):
          with self.data_lock:
              if len(self.queue) > 0:
                  return self.queue.pop()
              else:
                  return None, None, None
  
      def put_data(self, finish=False, change=None, highlight=None, data=None):
          with self.run_lock:
              if not self.run:
                  return 'close'
          with self.data_lock:
              if finish:
                  # check
                  for i in range(len(self.data)):
                      self.queue.appendleft((None, [(i, 'g')], None))
                  self.queue.appendleft((None, None, 'stay'))
                  self.queue.appendleft('finish')
              else:
                  self.queue.appendleft((change, highlight, data))
              return True
  
      def sort(self, array):
          print(f'sort_exp.py; sort; algorithm : {self.algorithm}')
          self.data = array.copy()
          self.run = True
          thr = threading.Thread(target=getattr(self, self.algorithm + '_sort'))
          thr.daemon = True
          thr.start()
  
      def bubble_sort(self):
          for i in range(len(self.data) - 1):
              for j in range(len(self.data) - i - 1):
                  opt = {'highlight': [(len(self.data) - i, 'b')]}
                  if i == 0:
                      opt['highlight'] = []
                  if self.data[j] > self.data[j + 1]:
                      self.data[j], self.data[j + 1] = self.data[j + 1], self.data[j]
                      opt['change'] = [(j, j + 1)]
                  opt['highlight'].append((j+1, 'r'))
                  if self.put_data(**opt) == 'close':
                      return 'close'
          self.put_data(finish=True)
  
      def quick_sort(self):
          def sort(low, high):
              if low < high:
                  middle = partition(low, high)
                  if sort(low, middle - 1) == 'close':
                      return 'close'
                  if sort(middle, high) == 'close':
                      return 'close'
  
          def partition(low, high):
              a, b, c = self.data[low], self.data[(low + high) // 2], self.data[high]
              pivot = a + b + c - min(a, b, c) - max(a, b, c)  # changeable
              while low <= high:
                  opt = {'highlight': [(pivot-1, 'b')]}
                  while self.data[low] < pivot:
                      low += 1
                  while self.data[high] > pivot:
                      high -= 1
                  opt['highlight'].extend([(low, 'r'), (high, 'r')])
                  if low <= high:
                      self.data[low], self.data[high] = self.data[high], self.data[low]
                      opt['change'] = [(low, high)]
                      low, high = low + 1, high - 1
                  if self.put_data(**opt) == 'close':
                      return 'close'
              return low
  
          if sort(0, len(self.data) - 1) == 'close':
              return 'close'
          self.put_data(finish=True)
  
      def heap_sort(self):
          def heapify(head, tail):
              left = head * 2 + 1  # left_index+1 = right_index
              while left < tail:
                  if left + 1 < tail and self.data[left] < self.data[left + 1]:
                      left += 1
                  if self.data[left] <= self.data[head]:
                      break
                  self.data[head], self.data[left] = self.data[left], self.data[head]
                  opt_ = {'change': [(head, left)], 'highlight': [(head, 'b'), (left, 'b')]}
                  head, left = left, left * 2 + 1
                  if self.put_data(**opt_) == 'close':
                      return 'close'
  
          for i in range(len(self.data) // 2 - 1, -1, -1):
              if heapify(i, len(self.data)) == 'close':
                  return 'close'
          for i in range(len(self.data) - 1, 0, -1):
              self.data[i], self.data[0] = self.data[0], self.data[i]
              opt = {'change': [(i, 0)], 'highlight': [(i, 'r'), (0, 'b')]}
              if self.put_data(**opt) == 'close':
                  return 'close'
              if heapify(0, i) == 'close':
                  return 'close'
          self.put_data(finish=True)
  
      def insertion_sort(self):
          for i in range(1, len(self.data)):
              for j in range(i, 0, -1):
                  opt = {'highlight': [(i, 'b')]}
                  if self.data[j] < self.data[j - 1]:
                      self.data[j], self.data[j - 1] = self.data[j - 1], self.data[j]
                      opt['change'] = [(j, j-1)]
                      opt['highlight'].extend([(j, 'r'), (j-1, 'r')])
                      if self.put_data(**opt) == 'close':
                          return 'close'
                  else:
                      break
          self.put_data(finish=True)
  
      def merge_sort(self):  # not in-place
          def sort(arr, start, end):
              if end-start < 2:
                  return
              middle = (start+end) // 2
              sort(arr, start, middle)
              sort(arr, middle, end)
              if merge(arr, start, middle, end) == 'close':
                  return 'close'
  
          def merge(arr, start, middle, end):
              i, j = 0, 0
              arr_1 = arr[start: middle]
              arr_2 = arr[middle: end]
              while i + j < (end-start):
                  if j == (end-middle) or (i < (middle-start) and arr_1[i] < arr_2[j]):
                      arr[start + i + j] = arr_1[i]
                      opt = {'highlight': [(start + i + j, 'r')], 'data': arr.copy()}
                      i += 1
                  else:
                      arr[start + i + j] = arr_2[j]
                      opt = {'highlight': [(start + i + j, 'r')], 'data': arr.copy()}
                      j += 1
                  opt['highlight'].append((end-1, 'b'))
                  if self.put_data(**opt) == 'close':
                      return 'close'
  
          if sort(self.data, 0, len(self.data)) == 'close':
              return 'close'
          self.put_data(finish=True)
  
      def gnome_sort(self):
          pos = 0
          max_ = 0
          while pos < len(self.data):
              opt = {'highlight': [(pos, 'r')]}
              if pos == 0 or self.data[pos] >= self.data[pos - 1]:
                  pos += 1
                  max_ = min(max(max_, pos), len(self.data)-1)
              else:
                  self.data[pos], self.data[pos - 1] = self.data[pos - 1], self.data[pos]
                  opt = {'change': [(pos, pos-1)], 'highlight': [(pos-1, 'r')]}
                  pos -= 1
              opt['highlight'].append((max_, 'b'))
              if self.put_data(**opt) == 'close':
                  return 'close'
          self.put_data(finish=True)
  
      def bogo_sort(self):
          while True:
              time.sleep(0.05)  # data is stuck in queue
              flag = True
              for i in range(len(self.data) - 1):
                  opt = {'highlight': [(i, 'r'), (i+1, 'r')]}
                  if self.put_data(**opt) == 'close':
                      return 'close'
                  if not self.data[i] < self.data[i + 1]:
                      flag = False
                      break
              if flag:
                  break
              random.shuffle(self.data)
              opt = {'data': self.data.copy()}
              if self.put_data(**opt) == 'close':
                  return 'close'
          self.put_data(finish=True)
  
      def selection_sort(self):
          for i in range(0, len(self.data) - 1):
              min_id = i
              for j in range(i + 1, len(self.data)):
                  if self.data[j] < self.data[min_id]:
                      min_id = j
                  opt = {'highlight': [(i, 'b'), (min_id, 'b'), (j, 'r')]}
                  if self.put_data(**opt) == 'close':
                      return 'close'
              if min_id != i:
                  self.data[i], self.data[min_id] = self.data[min_id], self.data[i]
                  opt = {'highlight': [(i, 'b'), (min_id, 'b')], 'change': [(i, min_id)]}
                  if self.put_data(**opt) == 'close':
                      return 'close'
          self.put_data(finish=True)
  
      def shell_sort(self):
          gap = 1
          while gap < len(self.data):  # Robert Sedgewick
              gap = gap*3+1
          gap = gap // 3
          while gap > 0:
              for i in range(gap):
                  for j in range(i, len(self.data), gap):
                      for k in range(j, gap-1, -gap):
                          opt = {'highlight': [(k, 'r')]}
                          if self.data[k] < self.data[k - gap]:
                              self.data[k], self.data[k - gap] = self.data[k - gap], self.data[k]
                              opt['change'] = [(k, k-gap)]
                              if self.put_data(**opt) == 'close':
                                  return 'close'
                          else:
                              break
              gap = gap // 3
          self.put_data(finish=True)
  
  
  '''    def radix_sort(self):
          # assume each data is natural number
          length = len(max(self.data))
  
          def classify(i):
              count = [0] * 10
              for x in self.data:
                  count[int(str(x)[i]) % 10] += 1
  
          for i in range(length-1, -1, -1):
              classify(i)'''
  
  '''if __name__ == '__main__':
      # ['bogo','merge', 'bubble', 'insertion', 'quick', 'selection', 'gnome', 'heap', 'shell'] 'merge', 'radix', 'comb'
      for x in ['bubble']:
          sorting = Sort()
          sorting.set_algorithm(x)
          data = [[13, 745, 35, 86, 24, 42, 123, 56, 75, 34, 7, 95, 53],
                  [137, 7458, 355, 836, 24, 456, 34, 53, 245, 42, 19023, 568, 75, 346, 57, 78, 75, 795, 538]]
          for x in [data[0]]:
              arr = x.copy()
              sorting.sort(arr)
              if arr != sorted(x):
                  print(arr, x)
          while len(sorting.queue):
              print(sorting.queue.pop())
      print('finish')
  '''
  