Algoritmos de Ordenação – Python

Ordenação

Definição: organizar uma sequência de elementos de modo que os mesmos estabeleçam algumarelação de ordem.

Diz-se que os elementos k1, k2 …, kn estarão dispostos de modo que k1 ≤ k2 ≤ … ≤ kn.

Bubble sort

Ideia básica: Percorrer o conjunto várias vezes e a cada iteração, comparar cada elemento com seu sucessor (v[i] com v[i+1]) e trocá-los de lugar caso estejam na ordem incorreta.

def bubble_sort(v):
     for i in range(len(v)-1):
         for j in range(len(v)-i-1):
             if(v[j]>v[j+1]):
                v[j],v[j+1] = v[j+1],v[j]
 
u=[2,4,10,12,6,8,16,14]    # Exemplo
print(u)
bubble_sort(u)
print(u)

Insertion sort

Ideia básica: Ordenar o conjunto inserindo os elementos em um subconjunto já ordenado.

No n-ésimo passo, inserir o n-ésimo elemento na posição correta entre x[0], …, x[n-1], que já estão em ordem (Realocar elementos).

def insertion_sort(v):
     for i in range(1, len(v)):
        aux = v[i]
        j=i-1
        while j>=0 and aux < v[j]:
            v[j+1]=v[j]
            j-=1
        v[j+1]=aux
u=[3,5,11,13,7,9,17,15]    # Exemplo
print(u)
insertion_sort(u)
print(u)

Download: http://valci.com.br/download/notebook/Ordenacao_Bubble-sort_e_Insertion-sort.ipynb

Outros Algoritmos de ordenação

Merge sort

# Merge sort
def merge_sort(alist):
    print("Separando ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        merge_sort(lefthalf)
        merge_sort(righthalf)
        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1
        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1
        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Mesclando ",alist)
alist = [54,26,93,17,77,31,44,55,20]
merge_sort(alist)
print(alist)

Quick sort

# Quick sort
def quick_sort(alist):
    quick_sort_helper(alist,0,len(alist)-1)
def quick_sort_helper(alist,first,last):
    if first<last:
        splitpoint = partition(alist,first,last)
        quick_sort_helper(alist,first,splitpoint-1)
        quick_sort_helper(alist,splitpoint+1,last)
def partition(alist,first,last):
    pivotvalue = alist[first]
    leftmark = first+1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist)
print(alist)