# quickSort.py

import random, time
from arrUtils import *


def quickSort(elems):
  qsort(elems, 0, len(elems)-1)

def qsort(elems, left, right):
  if left < right:
    pivot = partition(elems, left, right)
    qsort(elems, left, pivot-1)
    qsort(elems, pivot+1, right)


def partition(elems, left, right):
  i = left;
  j = right + 1;
  pivot = elems[left]; # use left-most
  while True:
    i += 1  # move right
    while elems[i] < pivot:
      if i == right:  # at end
        break
      i += 1
  
    j -= 1  # move left
    while pivot < elems[j]:
      if j == left:  # at start
        break
      j -= 1

    if i >= j: # crossed each other?
      break
    # swap 
    elems[i], elems[j] = elems[j], elems[i]
  
  # put pivot in final pos at elems[j]
  elems[left], elems[j] = elems[j], elems[left]
  return j


def quickSortL(elems):
  if len(elems) <= 1:
    return elems
  else:
    pivot = elems[0]  # use left-most
    left = [x for x in elems[1:] if x < pivot]
    right = [x for x in elems[1:] if x >= pivot]
    return quickSortL(left) + [pivot] + quickSortL(right)


if __name__ == "__main__":
  n = int(input("n? "))
  elems = genArr(n)
  start = time.time()
  quickSort(elems)
  printPartArr(elems)
  print(f"Time: {(time.time()-start):.4f} secs")