#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      elio
#
# Created:     02/10/2014
# Copyright:   (c) elio 2014
# Licence:     <your licence>
#-------------------------------------------------------------------------------
import random

# ordinamento veloce di Hoare (quicksort) con list comprehension
def qsort(list):
  if len(list) == 0 or len(list) == 1: return list
  else:
    pivot = list[0]
    minori = qsort([x for x in list[1:] if x < pivot])
    maggiori = qsort([x for x in list[1:] if x >= pivot])
    return minori + [pivot] + maggiori

# quicksort con list comprehension con pivot scelto a caso
def qsortRand(list):
  random.seed()
  return qsRand(list)

def qsRand(list):
  n = len(list)
  if n == 0 or n == 1: return list
  else:
    iPivot = random.randint(0, n-1)
    pivot = list[iPivot]
    list[iPivot] = list[0]
    minori = qsRand([x for x in list[1:] if x < pivot])
    maggiori = qsRand([x for x in list[1:] if x >= pivot])
    return minori + [pivot] + maggiori

# quicksort: versione standard sul posto
def qsortSulPosto(lis):
  qs(lis, 0, len(lis)-1)

def qs(lis, iniz, fine):
  if fine <= iniz: return
  pivot = lis[iniz] # scelgo come pivot l'elem. iniziale
  i = iniz+1   # escludo il pivot dalla sequenza da partizionare
  j = fine
  while i <= j:
    if lis[i] <= pivot: i = i+1
    else:
      lis[i], lis[j] = lis[j], lis[i] # scambia lis[i] con lis[j]
      j = j-1
  lis[iniz], lis[j] = lis[j], lis[iniz] # metto il pivot in mezzo
  qs(lis, iniz, j-1)
  qs(lis, j+1, fine)

#versione con pivot scelto a caso
def qsortSulPostoRand(lis):
  random.seed()
  qsr(lis, 0, len(lis)-1)

def qsr(lis, iniz, fine):
  if fine <= iniz: return
  iPivot = random.randint(iniz, fine) # scelgo un indice a caso 
  pivot = lis[iPivot] # prendo come pivot il contenuto di quella cella
  lis[iPivot], lis[iniz] = lis[iniz], lis[iPivot] # scambio il pivot col primo
  i = iniz+1; j = fine  # così mi riporto alla situazione della versione prec.
  while i <= j:
    if lis[i] <= pivot: i += 1
    else:
      lis[i], lis[j] = lis[j], lis[i] # scambia lis[i] con lis[j]
      j -= 1
  lis[iniz] = lis[j]
  lis[j] = pivot
  qsr(lis, iniz, j-1)
  qsr(lis, j+1, fine)  

"""
miaLis = [12, 3, 51, 7 ,15, 43, 21, 22, 18, 11, 34, 26, 11, 83]
tuaLis = qsortRand(miaLis)
miaLis = [12, 3, 51, 7 ,15, 43, 21, 22, 18, 11, 34, 26, 11, 83]
suaLis = qsort(miaLis)
print(tuaLis)
print(suaLis)
print(miaLis)
qsortSulPostoRand(miaLis)
qsort(miaLis)
print(miaLis)
"""