Métodos de Ordenamiento en Python

Practica #1 

Métodos de Ordenamiento en  Python

Introducción

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos servirán para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, presentando el código escrito en Python, de cada algoritmo

Bubble  Sort

#Implementación - Bubble_Sort

#Algoritmo que Ordena una Lista por el Metodo de la Burbuja...

print"\t-Ordenamiento por el metodo de la Burbuja-"

a=[51,21,67,13,43,3,16,11]

print '\n\tLista original\n'

print a

print "\n\tOrdenamiento\n"

for i in range(0,len(a)-1):

    for j in range(0,len(a)-1):

        if(a[j]>a[j+1]):

            aux=a[j]

            a[j]=a[j+1]

            a[j+1]=aux

    print "Paso->",i+1

    print a

print '\n\tLista Ordenada\n'

print a

Insertion Sort

#Algoritmo que Ordena una Lista por el Metodo de Insertion Sort...

import math

#Definicion de Funciones

def insertionsort(a):

    for i in range(1, len(a)):

        v = a[i]

        j = i

        while a[j-1] > v and j>=1:

            a[j] = a[j-1]

            j -= 1

            a[j] = v

    return a

a=[]

x=int(raw_input("Teclea el numero de datos a ingresar"))

i=1

while (i<=x):

    n=int(raw_input("Teclealo"))

    a.append(n)   

    i+=1

a=insertionsort(a)

print "Lista Ordenada",  a

Merge Sort

#Programa que ordena una lista por el Metodo de Ordenamiente Mergesort...

def mergeSort (numbers):

     def merge (first, second):

         mergedList = []

         while len(first) > 0 and len(second) > 0:

             if (first[0] < second[0]):

                 mergedList.append(first.pop(0))

             else:

                 mergedList.append(second.pop(0))

         mergedList += first

         mergedList += second        

         return mergedList

     if (len(numbers) == 1): return numbers

     middle = len(numbers) // 2

     first = mergeSort(numbers[0:middle])

     second = mergeSort(numbers[middle:])

     return merge(first, second)

#Mergesort.

n=int(raw_input("Inserta el numero de elementos de la lista:"))

a=[]

for i in range(0,n):

    x=raw_input("Inserta numero:")

    a.append(x)

n1=mergeSort(a)

print n1

Quick Sort

def Qsort(lista,izq,der):

    i=izq

    j=der

    x=lista[(izq + der)/2]

    while( i <= j ):

        while lista[i]<x and j<=der:

            i=i+1

        while x<lista[j] and j>izq:

            j=j-1

        if i<=j:

            aux = lista[i]; lista[i] = lista[j]; lista[j] = aux;

            i=i+1;  j=j-1;

        if izq < j:

                               Qsort( lista, izq, j );

                if i < der:

                               Qsort( lista, i, der );

def Lista(lista,tam):

    for i in range(0,tam):

        print lista[i]

def leelista():

    lista=[]

    cn=int(raw_input("Cantidad de numeros a ingresar: "))

    for i in range(0,cn):

        lista.append(int(raw_input("Teclea numero %d : " % i)))

    return lista

A=leelista()

Qsort(A,0,len(A)-1)

Lista(A,len(A))

Selection Sort

#Implementacion - Selection_Sort

print'\t-Ordenamiento por Selección-\n'

a=[85,24,63,45,17,31,96,50]

print '\tLista sin ordenar:'

print a

print '\n\tOrdenamiento\n'

for i in range(0,len(a)-1):

        min=i

        for j in range(i+1,len(a)):

            if (a[min] > a[j]):

                min=j

        aux=a[min]

        a[min]=a[i]

        a[i]=aux

        print'Paso->',i+1

        print a

print '\n\tLista Ordenada\n'

print a

Búsqueda Secuencial

Busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector se exploran (se examinan) en secuencia, uno después de otro. La búsqueda secuencial es necesaria, por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad.

La búsqueda secuencial se utiliza normalmente cuando el array no está ordenado. Comienza en el principio del array y busca hasta que se encuentra el dato buscado y se llega al final de la lista.

#Implementacion en Python

vector=['1','33','23','45','12','78','99','21','31']

valor_a_buscar='21'

posicion=0

encontrado='No'

posicion_del_valor_a_buscar=0

longuitud_del_vector=len(vector)

while posicion< longuitud_del_vector:

 if vector[posicion]==valor_a_buscar :

  posicion_del_valor_a_buscar=posicion

  encontrado='Si'

 posicion=posicion+1

if encontrado=='Si':

 print 'Valor '+valor_a_buscar+' encontrado en posicion '+str(posicion)

else:

 print 'Valor no encontrado'