Question

Você pode me dar exemplos de métodos de ordenação de sequências em Python?

Answer 1

Quicksort

Algoritmo [1, p. 171], [2, p. 176]:

def QuickSort(A, l=None, r=None):

    if (l is None):
        l = 0
    if (r is None):
        r = len(A)-1

    if (l < r):
        s = Partition(A, l, r)
        QuickSort(A, l, s-1) 
        QuickSort(A, s+1, r)

Para a seleção do pivô / partição (método "Partition"), mostraremos 2 possibilidades:
1) Hoare Partition [2, p. 178]:

def Partition(A, l, r):
    p = A[l]

    (i, j) = (l, r+1)

    i_greater_or_equal_j = False
    while not i_greater_or_equal_j:

        i_condition = False
        while not i_condition:
            i = i + 1
            i_condition = (A[i] >= p)

        j_condition = False
        while not j_condition:
            j = j - 1
            j_condition = (A[j] <= p)

        (A[i], A[j]) = (A[j], A[i])

        i_greater_or_equal_j = (i >= j)

    (A[i], A[j]) = (A[j], A[i])
    (A[l], A[j]) = (A[j], A[l])
    return j

2) [1, p. 171]

def Partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if (A[j] <= x):
            i = i + 1
            (A[i], A[j]) = (A[j], A[i])
    (A[i+1], A[r]) = (A[r], A[i+1])
    return i+1

Exemplo:

if __name__ == '__main__':
    x=[5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7]
    QuickSort(x)
    print x

Referências:
[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R.; Stein, C. "Introduction to Algorithms". MIT Press, 2009. 3 ed.
[2] Levitin, A. "Introduction to the design and analysis of algorithms". Pearson, 2011. 3 ed.

Answer 2

Dois exemplos com complexidade \(O(n^2)\):

Bubble sort em python

    import math
    import numpy as np

def bubbleSort(x):
    n=len(x)
    for i in range(0,n-1):
        for j in range(0,n-1-i):
            if(x[j+1]<x[j]):
                x[j],x[j+1]=x[j+1],x[j]
                print("i=",i," ","j=",j," ",x)
    return x




if __name__ == '__main__':

    x=[5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7]
    print(x)
    bubbleSort(x)

Selection sort

import math
import numpy as np


# Scan the entire list to find the smallest element    
def selectionSort(x):
    n=len(x)

    for i in range(0,n-1):
        minIndex=i
        for j in range(i+1,n):
            if(x[j]<x[minIndex]):
                minIndex=j
        x[i],x[minIndex]=x[minIndex],x[i]
        print( "i=",i," ",x)                
    return x 

if __name__ == '__main__':

    x=[5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7]
    print(x)
    selectionSort(x)

Answer 3

Insertion sort

import numpy as np

# It supposes the initial part of the vector is already sorted    
def insertion_sort(a):
    n=a.size
    for i in range(1,n):
        v=a[i]
        j=i-1
        while ((j>=0)and(a[j]>=v)):
            a[j+1]=a[j]
            j=j-1
        a[j+1]=v
        print(a)
    return a    

if __name__ == '__main__':

    x=np.array([5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7])
    print(x)
    print(insertion_sort(x))

Answer 4

Merge Sort

import numpy as np

def merge(x,y):
    nx=x.size
    ny=y.size
    z=np.empty([nx+ny],int)    
    i=0
    j=0
    cont=-1;
    while((i<=nx-1)and(j<=ny-1)):
        cont=cont+1    
        if(x[i]<y[j]):
            z[cont]=x[i]
            i=i+1
        else:
            z[cont]=y[j]  
            j=j+1

    if(cont<nx+ny-1):
        if(i<=nx-1):
            for k in range(cont+1,nx+ny):
                z[k]=x[i]
                i=i+1
        else:
            for k in range(cont+1,nx+ny):
                z[k]=y[j]
                j=j+1
    return z       

def merge_sort(a):
    n=a.size
    if(n>1):
        b=a[0:n//2]
        print("b before",b)
        c=a[n//2:n]
        print("c before",c)
        b=merge_sort(b)
        print("b",b)
        c=merge_sort(c)
        print("c",c)
        a=merge(b,c)
        print("a",a)
    return a      

if __name__ == '__main__':

    x=np.array([5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7])

    print("Merge sort:")
    print(merge_sort(x))     

Answer 5

Considere dois algoritmos de ordenação baseados em contagem.

1) Sem a informação da faixa de elementos que aparece na sequência com complexidade \(O(n^2)\):

import numpy as np

def comparison_counting_sort(a):
    n=len(a)
    count=np.zeros([n])
    sortedSequence=np.empty([n])
    for i in range(n-1):
        for j in range(i+1,n):
            if(a[i]<a[j]):
                count[j]=count[j]+1
            else:
                count[i]=count[i]+1
    for i in range(n):            
        sortedSequence[count[i]]=a[i]
    return sortedSequence    



if __name__ == '__main__':

    x=np.array([5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7])

    print ("comparison_counting_sort")
    print (comparison_counting_sort(x))

2) Com a informação da faixa de elementos que aparece na sequência com complexidade \(O(n)\):

import numpy as np

def distribution_counting_sort(a):
    n=len(a)
    l=np.min(a)
    u=np.max(a)
    distribution=np.zeros([u-l+1])
    sortedSequence=np.empty([n])
    for i in range(n):
        distribution[a[i]-l]=distribution[a[i]-l]+1
    for i in range(1,u-l+1):
        distribution[i]=distribution[i-1]+distribution[i]
    for i in range(n-1,-1,-1):
        j=a[i]-l
        sortedSequence[distribution[j]-1]=a[i]
        distribution[j]=distribution[j]-1
    return sortedSequence   

if __name__ == '__main__':

    x=np.array([5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7])



    print ("distribution_counting_sort")
    print (distribution_counting_sort(x))