Shaker Sort

L’algoritmo di bubble sort alternato nei due sensi

  • I numeri sono mescolati a caso oppure disposti in ordine decrescente.
  • La velocità va da 1 a 5

Web VPython

Web VPython 3.2
from random import shuffle
#---------------------------------------------------------------- 
def shaker_sort():
    global STOP
   
    n=len(lista)    
    inizio = 0
    fine   = n-1
    ultimo = n-1
    while(inizio < fine):
       for i in range(inizio, fine):  # PASSATA
           if(STOP): return
           if(lista[i] > lista[i+1]):
               temp       = lista[i]
               lista[i]   = lista[i+1]
               lista[i+1] = temp
               ultimo=i

               g1.data = [(x,y) for (x,y) in enumerate(lista)]
               g2.data = [(i+1, lista[i+1])]
               sleep(RITARDO)
       fine=ultimo
       for i in range(fine, inizio-1, -1):   # PASSATA
           if(STOP): return
           if(lista[i] > lista[i+1]):
               temp       = lista[i]
               lista[i]   = lista[i+1]
               lista[i+1] = temp
               ultimo=i
               
               g1.data = [(x,y) for (x,y) in enumerate(lista)]
               g2.data = [(i, lista[i])]
               sleep(RITARDO)
       inizio=ultimo

    g1.data = [(x,y) for (x,y) in enumerate(lista)]
    g2.data = []
    STOP = True
#----------------------------------------------------------------
def bind_veloc(evt):
    global VELOCIT, RITARDO
    x                = evt.value
    VELOCIT          = x
    wtext_veloc.text = x
    RITARDO          = 0.05 - VELOCIT/100

def bind_casuale(evt):
    global STOP
    STOP = True
    shuffle(lista)
    g2.data = []
    g1.data = [(x,y) for (x,y) in enumerate(lista)]

def bind_decresc(evt):
    global STOP
    STOP = True
    lista.sort(reverse=True)
    g2.data = []
    g1.data = [(x,y) for (x,y) in enumerate(lista)]

def bind_ordina(evt):
    global STOP
    if(STOP):
        STOP = False
        shaker_sort()
#----------------------------------------------------------------                
NUMERO    = 50
VELOCIT_0 = 3
VELOCIT   = VELOCIT_0
RITARDO   = 0.05 - VELOCIT/100
STOP      = True

c = canvas()
c.append_to_caption("Ordine iniziale "); button_casuale = button(bind=bind_casuale, text="Casuale");
c.append_to_caption(" ")               ; button_decresc = button(bind=bind_decresc, text="Decrescente");
c.append_to_caption("\t")              ; button_ordina  = button(bind=bind_ordina , text="ORDINA!");
c.append_to_caption("\n\nVelocità ")   ; slider_veloc   = slider(bind=bind_veloc  , min=1, max=5, step=0.1, value=VELOCIT)
c.append_to_caption("  ")              ; wtext_veloc    = wtext(text=VELOCIT)
c.append_to_caption("\n\n")

g = graph(ymax=NUMERO*1.1)

g1 = gvbars(color = color.gray(.5))  # Barre verticali lista
g2 = gvbars(color = color.blue)      # Barre verticali "scambiati"

lista = list(range(1, NUMERO+1))
shuffle(lista)

g1.data = [(x,y) for (x,y) in enumerate(lista)]
g2.data = []
c.delete()

Lascia un commento