# kselect.py

import random
from quickSort import *

MAX = 15


def genList(n):
  elems = []
  for _ in range(n):
    elems.append( random.randint(10, 99)) # 2-digit
  return elems


def kselect(elems, k):
  left = 0
  right = len(elems)-1
  while left < right: 
    pivot = elems[k] # use kth element
    i = left
    j = right
    while (i <= k) and (k <= j): 
      while elems[i] < pivot:
        i += 1   # move right
      while pivot < elems[j]:
        j -= 1   # move left
      elems[i], elems[j] = elems[j], elems[i]
      i += 1     # swap and move
      j -= 1
    
    if k < i:
      right = j  # focus on left half
    if j < k:
      left = i   # focus on right half
  return elems[k]



def kselectL(elems, k):
  xs = elems
  idx = 0
  while xs != []:
    pivot = xs[0]  # use left-most
    left = [x for x in xs[1:] if x < pivot]
    right = [x for x in xs[1:] if x >= pivot]
    pos = len(left)
    # print(left, pivot, right)
    # print("  ", idx, pos, k)
    if idx+pos > k:
      xs = left
    elif idx+pos == k:
      return pivot
    else:
      idx += pos+1
      xs = right
  return -1


def kselectP(elems, k):
  left = 0
  right = len(elems)-1
  while left <= right:
    pivot = partition(elems, left, right)
    if pivot == k:
      return elems[pivot]
    elif pivot < k:
      left = pivot+1   # focus on right half
    else:  # pivot > k
      right = pivot-1  # focus on left half
  return -1


k = int(input("k? "))
if k >= MAX:
  print("Too long")
else:
  elems = genList(MAX)
  print(elems)
  print( kselectP(elems, k))
  elems.sort()
  print(elems)
  print(" " + "    "*k + "^^")  # 4 spaces