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

+1 voto
554 visitas

## 5 Respostas

+3 votos
respondida Abr 30, 2016 por (436 pontos)

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.

+2 votos
respondida Abr 7, 2016 por (5,526 pontos)

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

Bubble sort em python

import math
import numpy as np

# Bubbling up the largest element to the last position
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)

+1 voto
respondida Abr 20, 2016 por (5,526 pontos)

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)

+1 voto
respondida Abr 20, 2016 por (5,526 pontos)

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)

+1 voto
respondida Mai 18, 2016 por (5,526 pontos)

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)