CODIGOS PYTHON : PROGRAMACION CON HILOS.

#SUMA SECUENCIAL (con threading)


import math
from threading import Thread

def hilo(j,i):
    if((2*i%2**j) == 0):
        c[int(2*i)] = c[int(2*i)]+c[int(2*i-2**(j-1))]

c = [0,1,1,1,1,1,1,1,1]
n = len(c)
lg = int(math.log(n,2))
print c
j = 1
while(j<=lg):
    i=1
    while(i<=n/2):
        t = Thread(target=hilo, args=(j,i))
        t.start()
        i = i+1
    print c
    j=j+1

_________________________________________________________________________

#SUMA CREW

import math

from threading import Thread

def hilo(j,i):

    if((2*i % 2**j) == 0):

        c[i]=c[i]+c[((i)-(int(pow(2,j-1))))];

        print c

c = [24,2,11,5,32,8,15,9]

n = len(c)

lg = int(math.log(n,2))

print c

j = 1

while(j<=lg):

    i=1

    while(i<=n):

        t = Thread(target=hilo, args=(j,i))

        t.start()

        t.join()

        i = i+1

    print c

    j=j+1

_________________________________________________________________________

#Estefanía Romero.

#BUSQUEDA EREW

import math

from threading import Thread

def Broadcast(vec,a,j):

    vec[1]=a

    j=1

    while(j<=lg):

        vec[i]=vec[i-2**j-1]

        j=j+1

        i=i+1

def minPRAM(l):

    j=1

    while(j<=lg):

        i=1

        while(i<=(n/2**i) and i>=1):

            if(l[(2**j)-1]>l[2*j]):

                l[j]=l[(2**1)-1]

            else:

                l[j]=l[(2**j)-1]

            i=i+1

        j=j+1

        return l[1]

def SearchPram(l,a):

    Broadcast(temp,a)

    j=1

    while(j>=1 and j<=n):

        if(l[j]==temp[j]):

            temp[j]=j

        else:

            temp[j]=0

        j=j+1

        return minPRAM(temp)

    

            

#main

b=[]

temp=[]

l=[0,2,-1,23,-4,2,5,-2,5,-2,0,5,1,5,-5,8,5,3,-2]

n=len(l)

lg=int(math.log(n,2))

a=5

SearchPram(l,a)

print temp

_________________________________________________________________________

#MinCRCW

import math

from threading import Thread

def hilo1(Win,j):

    Win[j]=0

    

def hilo2(L,Win,j,i):

    if(L[j]>L[i]):

        Win[j]=1

    else:

        Win[i]=1

    

def hilo3(Win,j,ind):

    if(Win[j]==0):

        ind[0]=j

L=[45,30,24,60]

Win=[1,1,1,1]

ind=[10000000]

j=0

n=len(L)

while(j<n):

    if(j>=0):

        t = Thread(target=hilo1, args = (Win,j))

        t.start()

        t.join()

    j=j+1

j=0

i=j+1

print "PASO 1"

print "Vector original:----->", L

print Win

while(i<n):

    if(j<i):

        if(j>=0):

            t = Thread(target=hilo2, args = (L,Win,j,i))

            t.start()

            t.join()

    j=j+1

    i=i+1

j=0

print "\nPASO 2"

print Win

while(j<n):

    if(j>=0):

        t = Thread(target=hilo3, args = (Win,j,ind))

        t.start()

        t.join()

        j=j+1

print "\nPASO 3"

print "Poniendo un 0 en el valor minimo\n", Win 

        

print " \nvalor minimo:", L[ind[0]]

_________________________________________________________________________

#Alumna: Estefanía Romero.

#Sort CRCW

import math

from threading import Thread

def hilo1(Win,j):

    Win.insert(j,0)

    

def hilo2(Win,j,i):

    if(W[j]>W[i]):

        Win[j]=Win[j]+1

    else:

        Win[i]=Win[i]+1

    

def hilo3(j,Win):

    W2.insert(Win[j],W[j])

    W2.pop(Win[j]+1)

    

#main

W=[]

W2=[]

Win=[]

indexMin=[]

n=int(raw_input("Cuantos numeros deseas ingresar? : "))

j=0

while(j<n):

    print "Escriba el numero de la posición ",j+1,":"

    x=int(raw_input())

    W.append(x)

    W2.append(0)

    j=j+1

n=len(W)

print "\nVector inicial:      ",W

j=1

while(j<=n):

    t = Thread(target=hilo1,args=(Win,j))

    t.start()

    t.join()

    j=j+1

print "win inicial: ",Win

j=0

while(j<=n):

    i=j+1

    while(i<n and j<i):

        t=Thread(target=hilo2, args = (Win,j,i))

        t.start()

        t.join()

        i=i+1

    j=j+1

#WIN

print "Win:            ",Win

j=0

while(j<n):

    t =Thread(target=hilo3,args=(j,Win))

    t.start()

    t.join()

    j=j+1

       

print "Vector final:     ",W2

_________________________________________________________________________

#Sort PRAM EREW Merge Secuencial

def merge_sort(array): 

  if len(array) == 1: 

    return array 

  else: 

    result = [] 

    first_sorted = merge_sort(array[:len(array)//2]) 

    second_sorted = merge_sort(array[len(array)//2:]) 

    while (len(first_sorted) and len(second_sorted)):

        if (first_sorted[0] <= second_sorted[0]):

            result.append(first_sorted.pop(0))

        else:

            result.append(second_sorted.pop(0))

    return result + first_sorted + second_sorted

  

#main

print "Ordenamiento Mergesort secuencial"

a=int(raw_input("Dame tamño del arreglo:  "))

x=[]

i=0

while (i<a): 

    x.append(int(raw_input("Dame numero: ")))

    i=i+1

b=merge_sort(x)

print "El arreglo ordenado es: ",b

    

_________________________________________________________________________

#Estefanía Romero.

#Sort PRAM EREW  ODD-EVEN MERGE Paralelo

from threading import Thread

def OddEvenMerge(L2,ini,fin):

    oddEvenMerge(L2,ini,fin)

    print "procesando: ",L2[1:fin+1]

    

def oddEvenMerge(L2,ini,fin):

    m=(fin-ini)+1

    odd=[0 for _ in range((m/2)+1)]

    even=[0 for _ in range((m/2)+1)]

    if(m==2):

        if(L2[ini]>L2[fin]):

            interchange(L2,ini,fin)

    else:

        oddEvenSplit(L2,odd,even,ini,m)

        t=Thread(target=ordena,args=(odd,(m/2)))

        t.start()

        t.join()

        t2=Thread(target=ordena,args=(even,(m/2)))

        t2.start()

        t2.join()

        

        i=1

        while(i<=(m/2)):

            t=Thread(target=mezclar,args=(L2,odd,even,i,1))

            t.start()

            t.join()

            i=i+1

            

        i=1

        while(i<int(m/2)):

            t=Thread(target=hiloOddEven,args=(L2,i))

            t.start()

            t.join()

            i=i+1

        i=1

        while(i<=int(m/2)):

            t=Thread(target=hiloOddEvenCent,args=(L2,i))

            t.start()

            t.join()

            i=i+1

        

def interchange(L2,ini,fin):

    aux=L2[ini]

    L2[ini]=L2[fin]

    L2[fin]=aux

def oddEvenSplit(L2,odd,even,ini,fin):

    od=1

    ev=1

    x=ini

    while(x<=fin):

        if((x%2)==0):

            even[ev]=L2[x]

            ev=ev+1

        else:

            odd[od]=L2[x]

            od=od+1

        x=x+1

    print "valor de odd: ",odd[1:fin+1]

    print "\nvalor de even: ",even[1:fin+1]

    

def ordena(L2,fin):

    L3=L2

    num2=fin

    OddEvenMerge(L3,1,num2)

def mezclar(L2,odd,even,j,aux):

    m=L2

    impar=odd

    par=even

    m[(2*j)-1]=impar[j]

    m[2*j]=par[j]

def hiloOddEven(num,i):

    num2=num

    j=i

    a=(2*j)

    b=(2*j)+1

    if(num2[a]>num2[b]):

        interchange(num2,a,b)

def hiloOddEvenCent(num,i):

    num2=num

    j=i

    a=(2*j)-1

    b=(2*j)

    if(num2[a]>num2[b]):

        interchange(num2,a,b)

#main

print "          ORDENAMIENTO DE LISTAS DE DIMENSION MULTIPLO DE 2"

print "\n cantidad de numeros a ordenar:  "

n=int(raw_input())

while((n%2)!=0):

    print "La dimension de la lista no es multiplo de 2!"

    print "Ingrese una dimension valida: "

    n=int(raw_input())

L=[0 for _ in range(n+1)]

    

i=0

while(i<n):

    print "Ingrese numero ",i+1

    x=int(raw_input())

    L[i+1]=x

    i=i+1

    

print "Lista de Entrada: ",L[1:n+1]

OddEvenMerge(L,1,n)

print "\nLista ordenado: ",L[1:n+1]

_________________________________________________________________________

#Multiplicacion de matrices

from threading import Thread

import math

def hilo1(j,i,l):

    Z[l][j][i]=int(X[j][l])* int(Y[l][i])

def hilo2(j,i,l,k):

    if(((2*l) % (2 **k))==0):

        Z2[2*l][j][i]=int(Z[2*l][j][i]+Z[2*l-(2**(k))][j][i])

print "             MULTIPLICACION DE MATRICES DE 2x2"

X=[[0 for   _ in range(2)] for _ in range(2)]

Y=[[0 for _ in range(2)] for _ in range(2)]

Z=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]

Z2=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]

    

lg=int(math.log(2,2))

print "\n\n      Matriz X:"

j=0

while(j<2):

    i=0

    while(i<2):

        print "Valor de la posicion [",j+1 ,", ",i+1," ]: "

        a=int(raw_input())

        X[j][i]=a

        i=i+1

    j=j+1

print "\n\n      Matriz Y:"

j=0

while(j<2):

    i=0

    while(i<2):

        print "Valor de la posicion [",j+1 ,", ",i+1," ]: "

        a=int(raw_input())

        Y[i][j]=a

        i=i+1

    j=j+1

print "\nMultiplicar : \n"

print "[ ",X[0][0],"  ",X[0][1]," ]      X      [ ",Y[0][0],"  ",Y[0][1]," ]"

print "[ ",X[1][0],"  ",X[1][1]," ]      X      [ ",Y[1][0],"  ",Y[1][1]," ]"

l=0

while(l<2):

    j=0

    while(j<2):

        i=0

        while(i<2):

            t=Thread(target=hilo1,args=(j,i,l))

            t.start()

            t.join()

            i=i+1

        j=j+1

    l=l+1

print "\n\nPaso 1: ",Z

k=0

while(k<lg):

    j=0

    while(j<2):

        i=0

        while(i<2):

            l=0

            while(l<1):

                t=Thread(target=hilo2,args=(j,i,l,k))

                t.start()

                t.join()

                l=l+1

            i=i+1

        j=j+1

    k=k+1

print "\nResultado de X  X  Y: \n"

print "          [ ",Z2[0][0][0],"  ",Z2[0][0][1]," ]"

print "          [ ",Z2[0][1][0],"  ",Z2[0][1][1]," ]"

    

Tercer y Cuarto enfoques para programar compiladores paralelos.

En 1988 McGraw y Axelrod identificaron cuatro formas distintas de desarrollar software (aplicaciones) para las computadoras paralelas:

1. Extender o enriquecer un compilador existente para que traduzca programas secuenciales en programas paralelos.
2. Extender o enriquecer un lenguaje existente con nuevas operaciones que permita a los usuarios expresar el paralelismo.
3. Agregar una nueva capa de lenguaje paralelo encima de un lenguaje secuencial existente.
4. Definir totalmente un nuevo lenguaje paralelo así como su compilador.

Tercer enfoque: AGREGAR UNA CAPA DE PROGRAMACIÓN PARALELA

Se puede pensar en la programación paralela como tener dos capas. La capa inferior contiene el núcleo (core) del cómputo, en donde un proceso manipula su parte de los datos para producir su parte del resultado. Un lenguaje de programación secuencial existente se adaptaría para expresar esta parte de la actividad. La capa superior controla la creación y sincronización de los procesos y la partición de los datos entre los procesos. Estas acciones podrían ser programadas usando un lenguaje paralelo (quizá un lenguaje de programación visual). El compilador sería responsable de traducir estas dos capas del programa paralelo en código listo para su ejecución sobre una computadora paralela.

Dos ejemplos de este enfoque son el ambiente CODE (Computationally Oriented Display Environment) y el ambiente HENCE (Heterogeneous Network Computing Environment). Estos sistemas permiten al usuario representar un programa paralelo como un grafo dirigido, donde los nodos representan procedimientos secuenciales y los arcos representan dependencias de datos entre los procedimientos.

Este enfoque requiere que el programador aprenda y use un nuevo sistema de programación paralelo, lo cual puede ser la razón por la que no ha captado mucha atención en la comunidad de programación paralela. Mientras que los prototipos de investigación están siendo distribuidos, no se conoce ningún sistema comercial basado en esta filosofía.

Cuarto enfoque: CREAR UN LENGUAJE PARALELO

El cuarto enfoque es darle al programador la habilidad de expresar explícitamente operaciones paralelas.

Una forma de soportar la programación paralela explícita es desarrollar un lenguaje paralelo desde cero. El lenguaje de programación OCCAM es un ejemplo famoso de este enfoque. Con una sintaxis sorprendentemente diferente de los lenguajes tradicionales imperativos, este lenguaje soporta tanto la ejecución de procesos en paralelo como secuenciales, así como la comunicación y la sincronización entre ellos.

Otra forma de soportar el paralelismo explícito es agregar construcciones paralelas a un lenguaje ya existente. Ejemplos de este enfoque son los lenguajes FORTRAN 90, HIGH PERFORMANCE FORTRAN y C*.

Anteriormente se mencionó la ironía de un programador codificando un algoritmo inherentemente paralelo en lenguaje de programación secuencial y un compilador trabajando para redescubrir el paralelismo. Un lenguaje que soporte el paralelismo explícito cambia la relación entre el programador y el compilador de adversarios a aliados.

Agregar construcciones paralelas a un lenguaje de programación existente o crear por completo un nuevo lenguaje de programación paralelo requiere el desarrollo de nuevos compiladores. Aún y cuando se adopte un lenguaje estándar, típicamente les lleva años a los vendedores desarrollar compiladores de alta calidad para sus sistemas paralelos.

Algunos lenguajes paralelos, tales como C*, no fueron adoptados como estándar. En esta situación muchos vendedores en competencia decidieron no proporcionar compiladores para el lenguaje en sus máquinas. Cuando esto pasa, la portabilidad de códigos se encuentra severamente en peligro.

Otra barrera para la adopción de nuevos lenguajes de programación es la resistencia del usuario. Cuando nuevas construcciones paralelas se agregan a un lenguaje de programación, los programadores deben aprender cómo usar estas nuevas construcciones. Muchos programadores están renuentes a tomar esta transición.

Más Ejemplos:

*Concurrent Pascal: diseñado por Brinch Hansen en 1975.

*Chapel: desarrollado en el 2010

*X10: basado en java y desarrollado en el 2004 por la IBM.

* NESL

*Cilk

*ZPL

*Linda

*Parlog

Referencias

-http://es.slideshare.net/neztooor7/presentacin-lenguajes-paralelos

-Elfego Gutierrez. "Programación Paralela y Distribuida".

Algoritmos de Búsqueda.

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

BUSQUEDA BINARIA

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado. Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

Código Python

def busqueda_binaria(lista, x):
    Precondición: lista está ordenada

    Devuelve -1 si x no está en lista;

    Devuelve p tal que lista[p] == x, si x está en lista

   

    # Busca en toda la lista dividiéndola en segmentos y considerando

    # a la lista completa como el segmento que empieza en 0 y termina

    # en len(lista) - 1.

    izq = 0 # izq guarda el índice inicio del segmento

    der = len(lista) -1 # der guarda el índice fin del segmento

    # un segmento es vacío cuando izq > der:

    while izq <= der:

        # el punto medio del segmento

        medio = (izq+der)/2

        print "DEBUG:", "izq:", izq, "der:", der, "medio:", medio

        # si el medio es igual al valor buscado, lo devuelve

        if lista[medio] == x:

            return medio

        # si el valor del punto medio es mayor que x, sigue buscando

        # en el segmento de la izquierda: [izq, medio-1], descartando la

        # derecha

        elif lista[medio] > x:

            der = medio-1

        # sino, sigue buscando en el segmento de la derecha:

        # [medio+1, der], descartando la izquierda

        else:

            izq = medio+1

        # si no salió del ciclo, vuelve a iterar con el nuevo segmento

    # salió del ciclo de manera no exitosa: el valor no fue encontrado

    return -1

# Código para probar la búsqueda binaria

def main():

    lista = input ("Dame una lista ordenada ([[]] para terminar): ")

    while lista != [[]]:

        x = input("¿Valor buscado?: ")

        resultado = busqueda_binaria(lista, x)

        print "Resultado:", resultado

        lista = input ("Dame una lista ordenada ([[]] para terminar): ")

BÚSQUEDA SECUENCIAL

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Código Python

def sequentialSearch(alist, item):
   pos = 0
   found = "El valor no está en la lista"

   while pos < len(alist) and not found:
       if alist[pos] == item:
           found = "Se encontró el valor!"
       else:
           pos = pos+1

   return found



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

for i in range(0,cn):
    lista.append(int(raw_input("Ingrese numero %d : " % i)))


n=int(raw_input("Dame el numero a buscar:  "))

print(sequentialSearch(lista, n))

Referencias

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSequentialSearch.html http://macabremoon0.tripod.com/id2.html
https://ronnyml.wordpress.com/2009/07/09/busqueda-lineal-y-busqueda-binaria/
http://librosweb.es/libro/algoritmos_python/capitulo_8/busqueda_binaria.html

Procesamiento Pipeline

Procesador Pipeline

Un solo computador el cual puede realizar simultáneamente operaciones de cálculos en determinadas secciones, con diferentes estadios de completitud. Los procesadores pipeline se basan en el principio de dividir los cálculos entre una cantidad de unidades funcionales que operan simultáneamente existiendo superposición.

 COMPUTADORES PIPELINE

Veamos el ejemplo de un pipeline de cuatro etapas: el proceso de ejecución de una instrucción en un computador digital envuelve cuatro pasos principales: levantar la instrucción de memoria (Instruction Fetch - IF); identificar la operación que debe efectuarse (Instruction Decoding - ID); levantar los operandos si son necesarios en la ejecución (Operand Fetch - OF); y ejecutar la operación aritmético lógica que ha sido decodificada. Antes de comenzar a ejecutar una nueva instrucción deben completarse estos cuatro pasos. La idea de un computador pipeline la vemos en la figura 4.9 : hay cuatro etapas

 IF, ID, OF y EX ordenadas de forma de una "cascada lineal".

 Las instrucciones sucesivas se ejecutan de forma superpuesta. La diferencia entre la ejecución superpuesta de instrucciones y la ejecución no superpuesta secuencial se muestra en los diagramas de espacio/tiempo de las Fig. 4.10

CLASIFICACIONES DE PROCESADORES PIPELINE. 

De acuerdo a los niveles de procesamiento, Händler (1977) ha propuesto el siguiente esquema de clasificación para los procesadores pipeline:

 Pipelines aritméticos La ALU de un computador puede dividirse para hacer operaciones de pipeline en varios formatos. Hay ejemplos bien claros en los pipelines usados en la Star-100, TI-ASC, Cray-1 y Cyber 205 (Fig. 4.14). 4.6.2. - Pipelines de instrucción La ejecución de un flujo de instrucciones puede hacerse en forma de pipeline, como vimos en la primer parte del capítulo, superponiendo la ejecución de la instrucción actual con las acciones de levantar, decodificar instrucciones y levantar operandos. Esta técnica también es conocida con el nombre de lookahead de instrucciones. Casi todos los computadores de alta performance actuales tienen pipelines de instrucción.

 Pipelines de procesador Se refiere al procesamiento del mismo flujo de datos por una cascada de procesadores, cada uno de los cuales procesa una tarea específica. El flujo de datos pasa el primer procesador, cuyo resultado se almacena en un bloque de memoria intermedia, que también es accesible por el segundo procesador. Este pasa el resultado refinado al tercero, y así siguiendo. En el momento en que Händler escribió su clasificación de los pipelines aún no existían implementaciones de pipelines de procesador (Fig. 4.16).

Referencias

http://msanchez.usach.cl/lcc/Arquitectura-Pipeline.pdf

Algoritmo de Ordenamiento

¿Qué es ordenamiento?

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.

El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.

A continuación se mostrarán los algoritmos de ordenamiento de los elementos de un vector.

QUICKSORT

Es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición.

Recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

Código en Python:

def partition(list2, first, last):
    sred = (first + last)/2
    if list2[first] > list2 [sred]:
        list2[first], list2[sred] = list2[sred], list2[first] 
    if list2[first] > list2 [last]:
        list2[first], list2[last] = list2[last], list2[first]  
    if list2[sred] > list2[last]:
        list2[sred], list2[last] = list2[last], list2[sred]    
    list2 [sred], list2 [first] = list2[first], list2[sred]    
    pivot = first
    i = first + 1
    j = last
  
    while True:
        while i <= last and list2[i] <= list2[pivot]:
            i += 1
        while j >= first and list2[j] > list2[pivot]:
            j -= 1
        if i >= j:
            break
        else:
            list2[i], list2[j] = list2[j], list2[i]  # swap
    list2[j], list2[pivot] = list2[pivot], list2[j]  # swap
    return j



def quick_sort(list2):
    quick_sort_r(list2, 0, len(list2) - 1)

    

def quick_sort_r(list2 , first, last):
    if last > first:
        pivot = partition(list2, first, last)
        quick_sort_r(list2, first, pivot - 1)
        quick_sort_r(list2, pivot + 1, last)




def imprimeLista(lista,tam):
    for i in range(0,tam):
        print lista[i]
        

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

for i in range(0,cn):
    lista.append(int(raw_input("Ingrese numero %d : " % i)))


quick_sort(lista)

imprimeLista(lista,len(lista))

 MÉTODO DE LA BURBUJA

    Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar  y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. 

Código en Python

def ordenamientoBurbuja(lista,tam):

    for i in range(1,tam):

        for j in range(0,tam-i):

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

                k = lista[j+1]

                lista[j+1] = lista[j]

                lista[j] = k;

def imprimeLista(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("Ingrese numero %d : " % i)))

    return lista

A=leeLista()

ordenamientoBurbuja(A,len(A))

imprimeLista(A,len(A))

SELECTION SORT

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el siguiente mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

Código en Python

def print_lista(lista,tam):

    for i in range(0,tam):

        print lista[i]

# Ordenamiento por selección

def ordenamiento_porseleccion(lista):

    # Itera por todo el array

    for posActual in range( len(lista) ):

        # Encuentra la posición del valor más pequeño

        # Empieza por la posición actual

        posMin = posActual

        # Escanea de izquierda a derecha (hasta el final de la lista)

        for escanPos in range(posActual+1, len(lista) ):

            # Es ésta la posición más pequeña?

            if lista[escanPos] < lista[posMin]:

                # Si lo es, la marcamos como la más pequeña

                posMin = escanPos

        # intercambia los dos valores

        temp = lista[posMin]

        lista[posMin] = lista[posActual]

        lista[posActual] = temp

    

# Creamos una lista con números aleatorios

lista=[]

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

for i in range(0,cn):

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

    

ordenamiento_porseleccion(lista)

print_lista(lista,len(lista))

INSERTION SORT

La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada. Para explicarlo mejor nos basaremos en el siguiente enunciado:

“Para cada elemento de la lista después del primero, comparar los elementos con los anteriores desplazando una posición a la derecha a todos los elementos anteriores que cumplan con la comparación y luego colocar el elemento en la posición del último elemento anterior desplazado.”

Ahora veamos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:

7, 3, 10, 1, 9

La lista tiene 5 elementos, con lo cual tendremos que recorrer la lista 4 veces. Ya que la comparación se hará desde el segundo elemento de la lista, es decir recorremos la lista después del primer elemento hasta el último.

1er. recorrido: Se toma 3 para comparar con los elementos anteriores. Los elementos anteriores son: 7

	3
7		10	1	9

La comparación 3<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.

	3
	7	10	1	9

Al no haber más elementos a comparar colocamos el 3 en la posición del último elemento desplazado.

3	7	10	1	9

2do. recorrido: Se toma 10 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7

		10
3	7		1	9

La comparación 10<7, es falsa, entonces no desplazamos nada y se termina este recorrido.

3	7	10	1	9

3er. recorrido: Se toma 1 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7, 10

			1
3	7	10		9

La comparación 1<10, es verdadera, entonces desplazamos el 10 una posición a la derecha.

			1
3	7		10	9

La comparación 1<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.

			1
3		7	10	9

La comparación 1<3, es verdadera, entonces desplazamos el 3 una posición a la derecha.

			1
	3	7	10	9

Al no haber más elementos a comparar colocamos el 1 en la posición del último elemento desplazado.

1	3	7	10	9

4to. recorrido: Se toma 9 para comparar con los elementos anteriores. Los elementos anteriores son: 1, 3, 7, 10

				9
1	3	7	10

La comparación 9<10 es verdadera, entonces desplazamos el 10 una posición a la derecha.

				9
1	3	7		10

La comparación 9<7 es falsa, entonces no desplazamos nada y se termina este recorrido, colocando el 9 en la posición del último elemento desplazado.

1	3	7	9	10

Código Python

def insertion_sort(list2):

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

        save = list2[i]

        j = i

        while j > 0 and list2[j - 1] > save:

            list2[j] = list2[j - 1]

            j -= 1

        list2[j] = save

def imprimeLista(lista,tam):

    for i in range(0,tam):

        print lista[i]

        

lista=[]

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

for i in range(0,cn):

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

insertion_sort(lista)

imprimeLista(lista,len(lista))

Merge Sort

El algoritmo de ordenamiento por mezcla  es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás

 Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas.

Código Python:

def merge_sort(list2):

    merge_sort_r(list2, 0, len(list2) -1)

    

# merge sort recursive (used by merge_sort)

def merge_sort_r(list2, first, last):

    if first < last:

        sred = (first + last)/2

        merge_sort_r(list2, first, sred)

        merge_sort_r(list2, sred + 1, last)

        merge(list2, first, last, sred)

        

# merge (used by merge_sort_r)

def merge(list2, first, last, sred):

    helper_list = []

    i = first

    j = sred + 1

    while i <= sred and j <= last:

        if list2 [i] <= list2 [j]:

            helper_list.append(list2[i])

            i += 1

        else:

            helper_list.append(list2 [j])

            j += 1

    while i <= sred:

        helper_list.append(list2[i])

        i +=1

    while j <= last:

        helper_list.append(list2[j])

        j += 1

    for k in range(0, last - first + 1):

        list2[first + k] = helper_list [k]

        

def imprimeLista(lista,tam):

    for i in range(0,tam):

        print lista[i]

        

lista=[]

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

for i in range(0,cn):

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

merge_sort(lista)

imprimeLista(lista,len(lista))

Referencias


http://adrorodri.blogspot.mx/2012/09/metodo-de-ordenacion-merge-sort.html
http://www.conoce3000.com/html/espaniol/Libros/PascalConFreePascal/Cap08-02-Ordenamiento%20por%20insercion%20%28Insertion%20sort%29.php
http://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n
http://www.estructuradedatos.galeon.com/burbujatext.htm
http://www.angelfire.com/wy2/est_info/quicksort.html
https://www.daniweb.com/software-development/python/code/216689/sorting-algorithms-in-python

https://saforas.wordpress.com/2011/01/24/codigo-python-ordenamiento-burbuja/

http://www.monografias.com/trabajos/algordenam/algordenam.shtml#ixzz3Sd09L7N6