#------------------------------------------------------------------------------- # Name: module1 # Purpose: # # Author: elio # # Created: 02/10/2014 # Copyright: (c) elio 2014 # Licence: #------------------------------------------------------------------------------- import random def èOrdinata(lista): for i in range(1, len(lista)): if lista[i] < lista[i-1]: return False return True def scambia(a,i,j): a[i], a[j] = a[j], a[i] # assegnaz. simultanea # ordinamento per selezione successiva del minimo def ssort(lista): n = len(lista) for i in range(0, n-1): iMin = i for j in range(i+1, n): if lista[j] < lista[iMin]: iMin = j scambia(lista, i, iMin) # ordinamento per inserimento, con scambi ripetuti def isortx(lista): n = len(lista) for i in range(1, n): for j in range(i, 0, -1): if(lista[j] < lista[j-1]): scambia(lista, j, j-1) else: break; # ordinamento per inserimento, senza scambi ripetuti def isort(lista): n = len(lista) for i in range(1, n): elem = lista[i] j = i while j > 0 and elem < lista[j-1]: if(elem < lista[j-1]):lista[j] = lista[j-1] j = j-1 lista[j] = elem # ordinamento veloce di Hoare (quicksort) def qsort(v): qs(v, 0, len(v)-1) def qs(v, iniz, fine): if fine <= iniz: return pivot = v[iniz] i = iniz+1 j = fine while i <= j: if v[i] <= pivot: i += 1 else: scambia(v, i, j) j = j-1 v[iniz] = v[j] v[j] = pivot qs(v, iniz, j-1) qs(v, j+1, fine) #versione con pivot scelto a caso def qsortRandom(v): random.seed() qs(v, 0, len(v)-1) def qsr(v, iniz, fine): if fine <= iniz: return iPivot = random.randint(iniz, fine) scambia(v, iPivot, iniz) pivot = v[iniz] i = iniz+1 j = fine while i <= j: if v[i] <= pivot: i += 1 else: scambia(v, i, j) j -= 1 v[iniz] = v[j] v[j] = pivot qsr(v, iniz, j-1) qsr(v, j+1, fine) #lis = [12, 3, 51, 7 ,15, 43, 21, 22, 18, 11, 34, 26, 11, 83] #qsortRandom(lis) #print(lis)