Problemas sencillos de programación para resolver

[rivale]

creo que ese es el que hice (el de burbuja), creo que el mas eficiente era uno que se llama "rápido".

aca viene explicado:

http://blog.zerial.org/ficheros/Informe_Ordenamiento.pdf

[PalitroqueZ]

para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer sin importar si se lleva 10 lineas o 100 lineas, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

[rivale]

para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

Eso sería dentro de un micro, pero si estas realizando un programa para PC o para algún teléfono, a veces si es necesario optimizar el código para tratar de reducir el consumo del procesador

[PalitroqueZ]

para mi, el mejor código programado es aquel que haga exactamente lo que debe hacer, la eficiencia es algo dificil de conseguir estos dias con tanto framework y capas de portabilidad. si quiero velocidad me voy por ensamblador

Eso sería dentro de un micro, pero si estas realizando un programa para PC o para algún teléfono, a veces si es necesario optimizar el código para tratar de reducir el consumo del procesador

mas bien lo decía precisamente por eso, podremos reducir el código hasta el mínimo ideal, pero tendriamos que tomar en cuenta, el consumo de recursos que utiliza el net framework (para el visual studio) o el JVM (para el caso de java).

en el caso de los microcontroladores, la unica razón valida que veo para optimizar el código, es la limitación de hardware

[rivale]

mas bien lo decía precisamente por eso, podremos reducir el código hasta el mínimo ideal, pero tendriamos que tomar en cuenta, el consumo de recursos que utiliza el net framework (para el visual studio) o el JVM (para el caso de java).

en el caso de los microcontroladores, la unica razón valida que veo para optimizar el código, es la limitación de hardware

++;
 

[Picuino]

Los algoritmos que he puesto hasta ahora son algoritmos lentos.
Los algoritmos lentos tienen una complejidad O(n^2), que significa que el número de operaciones que necesitan para ordenar la lista depende del cuadrado del número de elementos de la lista.
Para una lista de 500 elementos, los algoritmos lentos necesitan un número de operaciones proporcional a 500^2 = 250000.

ALGORITMOS LENTOS:

Método de burbuja:  
Como rivale ha comprobado, es mejor no utilizarlo nunca. Es demasiado lento.

Selección directa:
Busco el elemento más pequeño dentro de la lista de elementos no ordenados y lo coloco en otro montón.
Repito el primer paso hasta que todos los elementos estén ordenados.

Inserción directa:
Tomo el primer elemento de la lista. Busco cual es su lugar dentro de los elementos que ya están ordenados y lo coloco ahí.
Repito el primer paso hasta que todos los elementos estén ordenados.

Inserción binaria:
Es una variación del método anterior que mejora su velocidad. A la hora de buscar el sitio que le corresponde a un elemento dentro de la lista de elementos ordenados, puedo ir mirando uno a uno o hacerlo de forma binaria:
Miro en el medio de la lista de elementos ordenados. Si el elemento es mayor, descarto la mitad más pequeña y me quedo con la otra. Repito el proceso hasta encontrar su sitio. Como la lista se divide por la mitad en cada búsqueda, es mucho más rápido que buscar uno a uno su puesto.

Saludos.

[Picuino]

La ventaja del método de selección es que siempre tarda lo mismo, independientemente de cómo estén ordenados los elementos en la lista. De hecho en ocasiones puede ser más lento que el algoritmo de burbuja (en el caso de elementos casi ordenados).

Por su parte el método de inserción es muy rápido cuando la lista está ya ordenada, pero lento cuando la lista está desordenada (igual que el método de burbuja).

Algoritmo Shell o Shellsort:
Este algoritmo que está a medio camino entre los lentos y los rápidos. Es una mejora del algoritmo de inserción que pretende darle más velocidad en el caso de que los elementos estén desordenados.
Al igual que el algoritmo de inserción, su tiempo de ejecución depende de la ordenación de los elementos de la lista.

La desventaja que tiene es que resulta más difícil de implementar que los métodos anteriores.

Saludos.

[Picuino]

Algoritmo de ordenación Shellsort
Este algoritmo empieza de verdad a mejorar las cosas. No es tan bueno como los algoritmos rápidos, pero mejora bastante los algoritmos lentos en el caso de datos desordenados:

Comparaciones = 5936
Movimientos = 8984
Tics = 14920


Código del programa en Python:

Código: Python

1. """Algoritmo de ordenacion de datos Shellsort"""
2. def shellsort(datos):
3.    comps = 0
4.    moves = 0
5.  
6.    p = len(datos) // 2
7.    while(p>0):
8.       for i in range(p, len(datos)):
9.          moves += 1
10.          temp = datos[i]
11.          j = i
12.  
13.          while (j >= p and temp < datos[j-p]):
14.             comps += 1
15.             moves += 1
16.             datos[j] = datos[j - p]
17.             j -= p
18.          comps += 1
19.          moves += 1
20.          datos[j] = temp
21.          
22.       if (p == 2):
23.          p = 1
24.       else:
25.          p = int(p / 2.2)
26.  
27.    return comps, moves
28.  
29.  
30. datos = [
31.    1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
32.    3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
33.    6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
34.    3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798,
35.    8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964,
36.    9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264,
37.    1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844,
38.    7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009,
39.    5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580,
40.    7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811,
41.    5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533,
42.    6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869,
43.    4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931,
44.    7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286,
45.    9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176,
46.    0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674,
47.    6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167,
48.    9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348,
49.    8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242,
50.    7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455,
51.    9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608,
52.    5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799,
53.     932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770,
54.    3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508,
55.      94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572,
56.    9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741,
57.    3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179,
58.    8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315,
59.    7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258,
60.    6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259,
61.    4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075,
62.    3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627,
63.    9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174,
64.    8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559,
65.    3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903,
66.    7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724,
67.    6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297,
68.    8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375,
69.    7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444,
70.    5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705,
71.    4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307,
72.    4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466,
73.    3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345,
74.    3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726,
75.    6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298,
76.    5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345,
77.    3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007,
78.     685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377,
79.    4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081,
80.    8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
81. ]
82.  
83.  
84. #main program
85. comps, moves = shellsort(datos)
86. print "Comparaciones =", comps
87. print "Movimientos =", moves
88. print "Tics =", comps + moves
89. print "Datos = [\n  ",
90. print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
91. print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 5936
Movimientos = 8984
Tics = 14920
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199,
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320,
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489,
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691,
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952,
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123,
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337,
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723,
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963,
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174,
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447,
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642,
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895,
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051,
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266,
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430,
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572,
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737,
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105,
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348,
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519,
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677,
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869,
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059,
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306,
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463,
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659,
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903,
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990,
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185,
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301,
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505,
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700,
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863,
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016,
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148,
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310,
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542,
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741,
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978,
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158,
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284,
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504,
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780,
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984,
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133,
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358,
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594,
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792,
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956,
    ]

Saludos.

[Picuino]

Métodos rápidos de ordenación

Estos métodos tienen una complejidad computacional O(n·Log n). Esto significa que el número de operaciones necesarias para ordenar los elementos de la lista, es proporcional al número de elementos de la lista multiplicado por el logaritmo del número de elementos.
Para nuestro caso n=500 y el número de operaciones necesarias para ordenar la lista será proporcional a  500·Log 500 = 3107 operaciones.


Método HeapSort
Este método es bastante rápido y tiene una velocidad de ordenación constante, independientemente de cómo estén desordenados los datos.
Se basa en realizar dos tipos de operaciones. Primero se ordenan los datos en una estructura de montículo. A continuación se ordena la estructura en montículo en una lista ordenada.
Este método no es recursivo.


Método QuickSort
Este es el que se considera método más rápido de ordenación de datos en memoria (sin necesidad de utilizar una memoria externa)
Para datos aleatorios tiene la mayor velocidad. Como inconveniente se puede comentar que la velocidad puede bajar mucho en ciertos casos particulares.
Por otro lado este es un algoritmo recursivo, por lo que será necesario guardar información extra sobre el punto en el que estamos trabajando. En microcontroladores con poca memoria esto puede ser una desventaja.

Saludos.

[Picuino]

Algoritmo de ordenación Heapsort:

Este algoritmo tiene la ventaja de presentar siempre un comportamiento rápido, independientemente de la ordenación de los datos de entrada:

Comparaciones = 7431
Movimientos = 6554
Tics = 13985



Código del programa en Python:

Código: Python

1. """Algoritmo de ordenacion de datos Heapsort"""
2. def heapsort(datos):
3.    global n_comp, n_moves
4.    n_comp = n_moves  = 0
5.  
6.    # Crea la estructura de monticulo
7.    tam = len(datos)
8.    puntero = int((len(datos)-1)/2)
9.    while puntero>=0:
10.       cribar(datos, puntero, tam-1)
11.       puntero -= 1
12.  
13.    # Ordena monticulo
14.    puntero = len(datos)-1
15.    while puntero>0:
16.       n_moves += 3
17.       temp = datos[puntero]
18.       datos[puntero] = datos[0]
19.       datos[0] = temp
20.       puntero -= 1
21.       cribar(datos, 0, puntero)
22.    return n_comp, n_moves
23.    
24.  
25. def cribar(datos, datos_min, datos_max):
26.    global n_comp, n_moves
27.    down = datos_min * 2 + 1
28.    if (down > datos_max):
29.       return
30.    n_moves += 1
31.    temp = datos[datos_min]
32.    while down <= datos_max:
33.       if down < datos_max:
34.          n_comp += 1
35.          if datos[down+1] > datos[down]:
36.             down += 1
37.       n_comp += 1
38.       if temp > datos[down]:
39.          break
40.       n_moves += 1
41.       datos[datos_min] = datos[down]
42.       datos_min = down
43.       down = down * 2 + 1
44.    n_moves += 1
45.    datos[datos_min] = temp
46.  
47.  
48. datos = [
49.    1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
50.    3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
51.    6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
52.    3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798,
53.    8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964,
54.    9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264,
55.    1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844,
56.    7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009,
57.    5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580,
58.    7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811,
59.    5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533,
60.    6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869,
61.    4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931,
62.    7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286,
63.    9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176,
64.    0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674,
65.    6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167,
66.    9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348,
67.    8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242,
68.    7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455,
69.    9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608,
70.    5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799,
71.     932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770,
72.    3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508,
73.      94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572,
74.    9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741,
75.    3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179,
76.    8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315,
77.    7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258,
78.    6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259,
79.    4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075,
80.    3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627,
81.    9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174,
82.    8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559,
83.    3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903,
84.    7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724,
85.    6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297,
86.    8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375,
87.    7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444,
88.    5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705,
89.    4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307,
90.    4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466,
91.    3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345,
92.    3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726,
93.    6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298,
94.    5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345,
95.    3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007,
96.     685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377,
97.    4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081,
98.    8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
99. ]
100.  
101.  
102. #main program
103. n_comp, n_moves = heapsort(datos)
104. print "Comparaciones =", n_comp
105. print "Movimientos =", n_moves
106. print "Tics =", n_comp + n_moves
107. print "Datos = [\n  ",
108. print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
109. print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 7431
Movimientos = 6554
Tics = 13985
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199,
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320,
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489,
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691,
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952,
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123,
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337,
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723,
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963,
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174,
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447,
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642,
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895,
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051,
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266,
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430,
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572,
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737,
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105,
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348,
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519,
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677,
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869,
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059,
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306,
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463,
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659,
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903,
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990,
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185,
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301,
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505,
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700,
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863,
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016,
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148,
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310,
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542,
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741,
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978,
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158,
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284,
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504,
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780,
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984,
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133,
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358,
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594,
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792,
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956,
    ]

Saludos.

[Picuino]

Algoritmo de ordenación Quicksort:

Este algoritmo es el rey de los algoritmos de ordenación.
Tiene dos desventajas:
Es un algoritmo recursivo, por lo que necesita una pila o conjunto de datos para almacenar la posición de los subconjuntos que quedan por ordenar. La pila tiene un tamaño proporcional al logaritmo base dos del número de elementos a ordenar. Por ejemplo para 500 elementos, el logaritmo base 2 es casi 9 (hacen falta 9 bits para almacenar el número 500) y el número de datos a almacenar serán 2*9 = 18 punteros a la lista de datos.

Otra desventaja consiste en que con ciertas ordenaciones particulares de la lista de datos, la velocidad se reduce bastante. Este caso es muy particular y en la práctica es muy difícil que ocurra con datos ordenados de forma aleatoria.

Ahora los resultados  

Comparaciones = 5537
Movimientos = 3219
Tics = 8756


Código del programa en Python:

Código: Python

1. """Algoritmo de ordenacion de datos Quicksort"""
2. def quicksort(datos):
3.    global n_comp, n_moves
4.    n_comp = n_moves = 0
5.    quicksort_2(datos, 0, len(datos)-1)
6.    return n_comp, n_moves
7.  
8.  
9. def quicksort_2(datos, min_pos, max_pos):
10.    """Funcion auxiliar del algoritmo de ordenacion Quicksort"""
11.    global n_comp, n_moves
12.  
13.    # Condicion de salida recusiva
14.    if min_pos >= max_pos:
15.       return
16.  
17.    imin_pos = min_pos
18.    imax_pos = max_pos
19.    mid = datos[int((min_pos+max_pos)/2)]
20.  
21.    while imin_pos <= imax_pos:
22.       while datos[imin_pos] < mid:
23.          n_comp += 1
24.          imin_pos += 1
25.       n_comp += 1
26.  
27.       while datos[imax_pos] > mid:
28.          n_comp += 1
29.          imax_pos -=1
30.       n_comp += 1
31.  
32.       if imin_pos == imax_pos:
33.          imin_pos += 1
34.          imax_pos -= 1
35.          break
36.  
37.       if imin_pos < imax_pos:
38.          n_moves +=3
39.          temp = datos[imin_pos]
40.          datos[imin_pos] = datos[imax_pos]
41.          datos[imax_pos] = temp
42.          imin_pos += 1
43.          imax_pos -=1
44.  
45.    # Ordena primero el subconjunto mas pequenio para ahorrar saltos recursivos
46.    if imax_pos-min_pos < max_pos-imin_pos:
47.       quicksort_2(datos, min_pos, imax_pos)
48.       quicksort_2(datos, imin_pos, max_pos)
49.    else:
50.       quicksort_2(datos, imin_pos, max_pos)
51.       quicksort_2(datos, min_pos, imax_pos)
52.  
53.  
54. datos = [
55.    1497, 2094, 8094, 3331, 1126, 0736, 5999, 9688, 3593, 3353,
56.    3555, 9778, 4371, 2817, 9020, 2504, 6217, 2796, 8904, 0764,
57.    6700, 4105, 4468, 8504, 3201, 7426, 8780, 7518, 8846, 6228,
58.    3026, 2895, 3145, 1950, 4887, 0542, 8124, 3730, 7725, 4798,
59.    8733, 1024, 7326,  669, 5985, 4882, 5867, 2991, 4641, 1964,
60.    9245, 0501, 6406, 9280, 7916, 9477, 7166, 5616, 5183, 6264,
61.    1024, 6136, 1894, 2402, 6529, 9646, 9749, 1208,  909, 6844,
62.    7741, 2101, 8181, 8332, 1594, 9510, 9052, 1812, 1105, 3009,
63.    5306, 4086, 6918, 5059, 6416, 7600, 7700, 4758, 7016, 3580,
64.    7689, 5376, 7879, 1153,  945, 8274,  790, 8415, 9890, 1811,
65.    5117, 5787, 3264, 6903,  555, 1337, 5062, 5881, 3592, 5533,
66.    6056, 9723, 5849, 0352, 7148, 6921, 4568, 2615, 7105, 4869,
67.    4685, 2987,   86, 6671, 8651, 3713, 6700, 5162, 6996, 8931,
68.    7627, 1921, 6782, 2964, 1723, 2496, 6492, 1102, 3194, 6286,
69.    9070, 8809, 8284, 3924, 6185, 6910, 9044, 4132, 0421, 6176,
70.    0003, 4527, 7189,  268, 7978, 3881, 2497, 1252, 2330, 4674,
71.    6657, 3652, 7182, 1810, 2569, 1545, 1963, 3168, 3266, 6167,
72.    9575, 0200, 7064, 3931, 6748, 8158, 4523, 2391, 4649, 4348,
73.    8598, 3430, 4983, 9916, 5575, 2091, 5675, 8954, 0761, 3242,
74.    7649, 3842, 6078, 1123, 8144, 1939, 4487, 6824, 5786, 4455,
75.    9169, 2353, 7104, 0014, 3532, 6235, 3737, 3446, 8497, 1608,
76.    5947, 9078, 0411, 9139, 2823, 3858, 7542, 2447,  629,  799,
77.     932, 2034, 7641, 6301, 9415, 0024, 8822, 4243, 5918, 7770,
78.    3517, 3742, 8472, 9127, 3351, 8108, 6206, 9826, 9462, 3508,
79.      94, 8209, 5372, 9358, 0223, 7268, 9840, 8529,  771, 3572,
80.    9937, 7143, 3051, 8448, 5031, 4636, 8590, 3294, 5210, 5741,
81.    3634, 9242, 8400, 5990, 8113, 1154, 1555, 5658, 9085, 9179,
82.    8736, 4712, 6754, 5967, 6848, 7139, 9501, 6505, 5333, 3315,
83.    7737, 7527, 5977, 6657, 2070, 1140, 5534, 9133, 7690, 5258,
84.    6915,  792, 9924, 9933, 9601, 5346, 9188, 2199, 1091, 7259,
85.    4932,  242, 8314, 8326, 1129, 7811, 1933, 4677, 4867, 3075,
86.    3132,  810, 9029,  727, 9055, 5940, 1442, 5141,  459,  627,
87.    9792, 3026, 8012, 8760, 5954, 2642, 2583, 7230, 3431, 2174,
88.    8984, 4221, 2782, 7529, 6415, 2073, 9761, 5659, 6208,  559,
89.    3602, 6420, 5917,  489, 4267, 0675, 4343, 4515, 3388, 5903,
90.    7493, 3408, 5463, 7913, 7004, 1043, 5956, 8239, 4803, 6724,
91.    6532, 8070,  550, 7118, 2546, 4519, 7225, 7742, 9187, 6297,
92.    8010,  691,   27, 2058, 4568, 5860, 2821, 9680, 5322, 3375,
93.    7767, 2586, 8182, 0500, 2286, 9836, 4814, 5092,  969, 7444,
94.    5085,  487, 8035, 3482, 4246, 0361, 7185, 3827, 6742, 6705,
95.    4416, 2750,  989, 4263, 9161, 7310, 6412, 5782, 1174, 0307,
96.    4382, 0464, 7345, 5385, 5629, 0465, 8815, 2334, 9408, 1466,
97.    3045, 8856, 4975, 5449, 1861, 7048, 9815, 8885, 5492, 5345,
98.    3349, 6925, 6863, 1659, 6273, 8183,  341, 3461,  952, 2726,
99.    6124, 3483, 6073, 1571, 4614, 8278, 3868, 7124, 8762, 8298,
100.    5478, 6643, 7519, 9364, 4932, 2554, 1261, 9594, 7183, 0345,
101.    3712, 6647, 9640,  370, 8654, 4381, 7962, 4694, 2931, 5007,
102.     685, 6414, 5349, 4396, 5994, 7944, 5011, 2190, 3240, 9377,
103.    4256, 8256, 6413, 9956, 2922, 1004, 2709, 0215, 5639, 7081,
104.    8260, 2812, 6636, 2429, 4114, 4715, 6381, 6933, 2137,  378,
105. ]
106.  
107.  
108. #main program
109. n_comp, n_moves = quicksort(datos)
110. print "Comparaciones =", n_comp
111. print "Movimientos =", n_moves
112. print "Tics =", n_comp + n_moves
113. print "Datos = [\n  ",
114. print "".join(["%04d" % datos[i] + ", " + "\n   "*((i+1)%10==0) for i in range(0, len(datos))]),
115. print "]"

Resultado:

Código: [Seleccionar]

Comparaciones = 5537
Movimientos = 3219
Tics = 8756
Datos = [
   0003, 0012, 0020, 0027, 0086, 0094, 0128, 0141, 0147, 0199,
   0229, 0234, 0241, 0242, 0265, 0268, 0273, 0308, 0309, 0320,
   0321, 0341, 0354, 0370, 0378, 0445, 0459, 0478, 0487, 0489,
   0497, 0500, 0550, 0555, 0559, 0627, 0629, 0669, 0685, 0691,
   0727, 0771, 0790, 0792, 0799, 0810, 0909, 0932, 0945, 0952,
   0969, 0989, 1004, 1024, 1024, 1043, 1091, 1102, 1105, 1123,
   1126, 1129, 1140, 1153, 1154, 1174, 1208, 1252, 1261, 1337,
   1442, 1466, 1497, 1545, 1555, 1571, 1594, 1608, 1659, 1723,
   1810, 1811, 1812, 1861, 1894, 1921, 1933, 1939, 1950, 1963,
   1964, 2034, 2058, 2070, 2073, 2091, 2094, 2101, 2137, 2174,
   2190, 2199, 2286, 2330, 2334, 2353, 2391, 2402, 2429, 2447,
   2496, 2497, 2504, 2546, 2554, 2569, 2583, 2586, 2615, 2642,
   2709, 2726, 2750, 2782, 2796, 2812, 2817, 2821, 2823, 2895,
   2922, 2931, 2964, 2987, 2991, 3009, 3026, 3026, 3045, 3051,
   3075, 3132, 3145, 3168, 3194, 3201, 3240, 3242, 3264, 3266,
   3294, 3315, 3331, 3349, 3351, 3353, 3375, 3388, 3408, 3430,
   3431, 3446, 3461, 3482, 3483, 3508, 3517, 3532, 3555, 3572,
   3580, 3592, 3593, 3602, 3634, 3652, 3712, 3713, 3730, 3737,
   3742, 3827, 3842, 3858, 3868, 3881, 3924, 3931, 4086, 4105,
   4114, 4132, 4221, 4243, 4246, 4256, 4263, 4267, 4343, 4348,
   4371, 4381, 4382, 4396, 4416, 4455, 4468, 4487, 4515, 4519,
   4523, 4527, 4568, 4568, 4614, 4636, 4641, 4649, 4674, 4677,
   4685, 4694, 4712, 4715, 4758, 4798, 4803, 4814, 4867, 4869,
   4882, 4887, 4932, 4932, 4975, 4983, 5007, 5011, 5031, 5059,
   5062, 5085, 5092, 5117, 5141, 5162, 5183, 5210, 5258, 5306,
   5322, 5333, 5345, 5346, 5349, 5372, 5376, 5385, 5449, 5463,
   5478, 5492, 5533, 5534, 5575, 5616, 5629, 5639, 5658, 5659,
   5675, 5741, 5782, 5786, 5787, 5849, 5860, 5867, 5881, 5903,
   5917, 5918, 5940, 5947, 5954, 5956, 5967, 5977, 5985, 5990,
   5994, 5999, 6056, 6073, 6078, 6124, 6136, 6167, 6176, 6185,
   6206, 6208, 6217, 6228, 6235, 6264, 6273, 6286, 6297, 6301,
   6381, 6406, 6412, 6413, 6414, 6415, 6416, 6420, 6492, 6505,
   6529, 6532, 6636, 6643, 6647, 6657, 6657, 6671, 6700, 6700,
   6705, 6724, 6742, 6748, 6754, 6782, 6824, 6844, 6848, 6863,
   6903, 6910, 6915, 6918, 6921, 6925, 6933, 6996, 7004, 7016,
   7048, 7064, 7081, 7104, 7105, 7118, 7124, 7139, 7143, 7148,
   7166, 7182, 7183, 7185, 7189, 7225, 7230, 7259, 7268, 7310,
   7326, 7345, 7426, 7444, 7493, 7518, 7519, 7527, 7529, 7542,
   7600, 7627, 7641, 7649, 7689, 7690, 7700, 7725, 7737, 7741,
   7742, 7767, 7770, 7811, 7879, 7913, 7916, 7944, 7962, 7978,
   8010, 8012, 8035, 8070, 8094, 8108, 8113, 8124, 8144, 8158,
   8181, 8182, 8183, 8209, 8239, 8256, 8260, 8274, 8278, 8284,
   8298, 8314, 8326, 8332, 8400, 8415, 8448, 8472, 8497, 8504,
   8529, 8590, 8598, 8651, 8654, 8733, 8736, 8760, 8762, 8780,
   8809, 8815, 8822, 8846, 8856, 8885, 8904, 8931, 8954, 8984,
   9020, 9029, 9044, 9052, 9055, 9070, 9078, 9085, 9127, 9133,
   9139, 9161, 9169, 9179, 9187, 9188, 9242, 9245, 9280, 9358,
   9364, 9377, 9408, 9415, 9462, 9477, 9501, 9510, 9575, 9594,
   9601, 9640, 9646, 9680, 9688, 9723, 9749, 9761, 9778, 9792,
   9815, 9826, 9836, 9840, 9890, 9916, 9924, 9933, 9937, 9956,
    ]

Saludos.

[Berto]

Yo para ordenar de menor a mayor utilizo esta burbuja No lo e hecho todo solo utilizo array[33];
pero tiene una cosa BUENA deja al array[nº inferior] en array[0] A LA PRIMERA este donde este y parece rrapida
Eso si necesito operarla una y otra para dejar todo en orden pero del proyecto que difiere lo prioritario es allar al menor

INCONVENIENTE Si los numeros mayores estan al principio le cuesta muchos pasos dejarlos al final

Código: [Seleccionar]

//nu debe corresponder al tamaño del array
//se empieza por el final esto hace que el menor sea arrastrado a array[0] a la primera
void bur(){//Burbuja(0)
for(c1=nu-1;c1>0;c1--){//si nu=5---> 0 1 2 3 4 pasadas
c2=c1-1;///...........
//array[c1];//POSICION actual "superior array +1"
//array[c2];//posicion anterior
if(array[c2]>array[c1]){////si p.anterior es mayor a p.siguiente   invertir de menor a mayor
mayor=array[c2];
array[c2]=array[c1];//distancia menor debe pasar a "inferior array -1"
array[c1]=mayor;//array[+1]
}
}//for(c1)
}
Y Si lo importante es dejar al numero mayor al final del array[maximo] a la primera Empezar desde array[0] Y se consigue que el nº mayor pase a array[final] este donde este. Este es un ejemplo no adaptado a este proyecto

Código: [Seleccionar]

void bu2(){//Burbuja(1)
for(co=0;nu>=co;co++){//si nu=5---> 0 1 2 3 4 pasadas
ca=co+1;
if(ca>=nu){ return; }//se salio del array[nu]
p0=psz[co];//POSICION actual
p1=psz[ca];//posicion siguiente "superior array +1"
d0=dis[p0];
d1=dis[p1];//distancia siguiente "superior array +1"
if(d0>d1){//si d0(actual) esta a + distancia k d1(sigiente) ...d1 tiene prioridad + cercano
psz[co]=p1;//prior //psicion-sigiente pasa aposicion-anterior//es necesario tanto intercanviar posicion y distancia
psz[ca]=p0;
}
}//for(co)
}
No las meti en redundancia while o for porque lo principal son los primeros resultados, pero si es inportante todo el orden si seria necesario algo a si

Saludos.