Problema ordenando array usando funcion qsort

[jhozate]

Hola a todos, resulta que requiero ordenar un array de numeros tipo int, he buscado y encuentro que  stdlib.h trae la funcion qsort() , miro en la ayuda de ccs(V5.026) y veo un ejemplo, trato de compilarlo y da problemas en la compilación que no tengo idea de que pueda ser, el ejemplo de la ayuda es como sigue:
Nota:El  return –1  es en realidad return -1   . No se porque sale como esta posteado

Código: C++

1. int nums[5]={ 2,3,1,5,4};
2. int compar(void *arg1,void *arg2);
3.  
4. void main()  {
5.    qsort ( nums, 5, sizeof(int), compar);
6. }
7.    
8. int compar(void *arg1,void *arg2)  {
9.    if ( * (int *) arg1 < ( * (int *) arg2) return –1
10.    else if ( * (int *) arg1 == ( * (int *) arg2) return 0
11.    else return 1;
12. }

El codigo que estoy implementando

Código: C++

1. #INCLUDE <24FJ64GA002.h>
2. //!#INCLUDE <MATH.H>
3. #INCLUDE <STDLIB.H>
4. #INCLUDE <STRING.H>
5. #FUSES ICSP1, NOWDT, NODEBUG, NOPROTECT, NOJTAG, FRC, NOWINDIS, NOPR, IOL1WAY, OSCIO, NOCKSFSM, NOIESO
6. #USE DELAY(INTERNAL=8000000)
7.  
8. int nums[5]={ 2,3,1,5,4};
9. int compar(void *arg1,void *arg2);
10.  
11.  
12. VOID MAIN()
13. {
14.  
15.  
16. WHILE (TRUE)
17. {
18.  
19. qsort ( nums, 5, sizeof(int), compar);
20. WHILE(TRUE);
21. }
22. }
23.  
24.  
25.  
26. int compar(void *arg1,void *arg2)  {
27.  
28.    if ( * (int *) arg1 < ( * (int *) arg2) return –1
29.  
30.    else if ( * (int *) arg1 == ( * (int *) arg2) return 0
31.  
32.    else return 1;
33.  
34. }

En la linea 28 del código que pongo aqui aparecen los errores
*** Error 58 "ORDENAMIENTO.c" Line 42(44,50): Expecting a close paren
*** Error 1 "ORDENAMIENTO.c" Line 42(51,52): Illegal C character in input file  0x96



soluciono los parentesis que faltan en los if  y los ";" de return, el error de caracter ilegal se soluciono borrandolo y poniendolo de nuevo, parece que el signo que trae en el ejemplo es un guion y No un signo menos.
Cuando compilo de nuevo aparece el error
*** Error 144 "C:\Program Files (x86)\PICC\Drivers\STDLIB.H" Line 1304(1,1): No valid assignment made to function pointer  1052  from=MAIN 79 SCR=2717

Este error me lleva a stdlib, la linea 1304 de stdlib, adjunto la imagen
He probado los codigos de estas paginas
http://codigoprogramacion.com/cursos/tutoriales-c/quicksort-en-c-algoritmo-de-ordenamiento.html#.U_pde_l5NZ4
http://ibmcaripito.mforos.com/1555603/7920637-metodo-de-ordenamiento-quicksort-en-lenguaje-c/
sin embargo me sale un error de recursividad.

Que se les ocurre que pueda ser?

[RedPic]

Respondo para suscribirme al hilo, me interesa mucho su solución 

[Picuino]

Si tienes muchos problemas puedes programar tú mismo un algotitmo de ordenación que te convenga.
http://www.todopic.com.ar/foros/index.php?PHPSESSID=9h725c46npi9eo5ck3kabd8vr4&topic=42523.0

Saludos

[jhozate]

gracias picuino, tu post fue el primero que vi, según como entendí tus pruebas y lo que he leido el algoritmo quicksort es de los mas rápidos y mi tamaño de array puede ser superior a 100, el compilador que uso implementa qsort que según veo en la ayuda obedece al algoritmo quicksort, pero tengo problemas en la implementación del ejemplo del compilador

Esta es la seccion de codigo para quicksort que deberia migrar al compilador que uso?

Código: C++

1. def quicksort(datos):
2.    """Algoritmo de ordenacion de datos Quicksort"""
3.    global n_comps, n_moves
4.    n_comps = n_moves = 0
5.    quicksort_2(datos, 0, len(datos)-1)
6.    return n_comps, n_moves
7.  
8.  
9. def quicksort_2(datos, min_pos, max_pos):
10.    """Funcion auxiliar del algoritmo de ordenacion Quicksort"""
11.    global n_comps, 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_comps += 1
24.          imin_pos += 1
25.       n_comps += 1
26.  
27.       while datos[imax_pos] > mid:
28.          n_comps += 1
29.          imax_pos -=1
30.       n_comps += 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)

En alguno de los codigos que he probado sale el error de la imagen adjunta

[Picuino]

Es que Quicksort, a pesar de ser un algoritmo muy bueno, tiene varias desventajas.

Una de ellas es que es un algoritmo recursivo. En los pequeños micros con una pila de programa limitada, esto hay que solucionarlo con un array que sirva de pila para almacenar la información recursiva. Esto consume tiempo, memoria y espacio de programa además de hacer el método más complicado que otros.

Si me cuentas las circunstancias igual puedo aconsejarte:
   ¿Cuánto tiempo dispones para ordenar el array?
   ¿Están siempre los elementos desordenados, o la mayoría de las veces están casi ordenados?
   ¿El micro es grande o pequeño en memoria y velocidad?
   ¿Cuántos datos son? ¿Siempre serán 100 o puede que lleguen a 1000?

Un saludo.

[jhozate]

la situación es la siguiente, mediante pulsador o boton de emergencia obtengo coordenadas de gps y debo evaluar el punto mas cercano a ese lugar (los lugares son fijos y ahora que reviso la documentación son aproximadamente 70 lugares). Por eso necesitaría hallar las distancias y guardarlas en un array y elegir la menor distancia para enviar un mensaje de texto a un teléfono presente en ese lugar.  
por lo tanto, el tiempo no es crítico si hablamos unos cuantos segundos.
Siempre estarían en desorden en este caso.
Microcontrolador PIC24FJ64GA002, 64K memoria, actualmente a 8Mhz internos , posibilidad de hasta 32Mhz usando PLL
saludos

[Picuino]

El micro es potente, son pocos datos y tienes bastante tiempo para responder.
Yo no me preocuparía mucho del método de ordenación.

Por otra parte, no parece que necesites ordenar todo el array... sólo buscar el elemento más pequeño y enviarle.

Si quieres ordenar todos, puedes utilizar el método de selección directa. Es lento, pero se ajusta a tu objetivo:
La ventaja de este método es que primero busca el elemento más pequeño (lo que tu quieres) y lo coloca en primer lugar.
Luego busca el siguiente elemento más pequeño y lo coloca en segundo lugar (ya puedes enviar el segundo lugar más cercano)
así hasta terminar.

Es sencillo y el más rápido para lo que tú quieres.

Saludos.

P.D.: Además no es recursivo.

[jhozate]

Bien , muchas gracias picuino, retomo a leer tu post  y sigo investigando    , ahora que lo dices , seria mucho mas útil ya que quicksort ordena en el array, si el de selección directa busca el elemento mas pequeño , incluso supongo, me facilita mas la tarea de saber a que numero debo enviar el sms.
Sigo leyendo y comento
gracias

[Picuino]

Si de todas formas te interesa implementar el método Quicksort por tu cuenta, aquí tienes una implementación en Basic, que evita la recursividad:

http://microhobby.speccy.cz/mhf/031/MH031_22.jpg

Microhobby 31: Método Quicksort


Saludos.

[Picuino]

Otra implementación no recursiva. Elimina las llamadas a funciones y eso la hace muy eficiente:

http://alienryderflex.com/quicksort/

Código: [Seleccionar]

//  quickSort
//
//  This public-domain C implementation by Darel Rex Finley.
//
//  * Returns YES if sort was successful, or NO if the nested
//    pivots went too deep, in which case your array will have
//    been re-ordered, but probably not sorted correctly.
//
//  * This function assumes it is called with valid parameters.
//
//  * Example calls:
//    quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
//    quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7

bool quickSort(int *arr, int elements) {

  #define  MAX_LEVELS  1000

  int  i, piv;
  int  beg[MAX_LEVELS], end[MAX_LEVELS];
  int  L, R;

  i = 0;
  beg[0]=0;
  end[0]=elements;
  while (i>=0) {
    L=beg[i];
    R=end[i]-1;
    if (L<R) {
      piv=arr[L];
      if (i==MAX_LEVELS-1) return NO;
      while (L<R) {
        while (arr[R]>=piv && L<R) R--;
        if (L<R) arr[L++]=arr[R];
        while (arr[L]<=piv && L<R) L++;
        if (L<R) arr[R--]=arr[L];
      }
      arr[L]=piv;
      beg[i+1]=L+1;
      end[i+1]=end[i];
      end[i++]=L;
    }
    else {
      i--;
    }
  }
  return YES;
}

Saludos.

[jhozate]

gracias 

[Picuino]

Si implementas la selección directa, es mejor no ordenar todo el array.
Primero ordenas el primer elemento (el más pequeño) y retornas. Ya puedes enviarlo.

A partir de aquí puedes llamar otra vez a la función para seguir ordenando más elementos, sólo si te interesa.

Saludos.

[jhozate]

Como bien me ha aterrizado picuino en la idea, en mi caso no es necesario ordenar todo el array sino mas bien conocer el dato mas pequeño y también conocer su posición. Sin embargo pues quise probar que tal va eso de organizar el array usando el algoritmo de selección.
Busque rapidamente    un array de numeros aleatorios, desconozco el porcentaje de "desordenamiento", el cual es el siguiente:

Código: C++

1. int array[150] ={35,42,95,84,75,46,33,152,198,45,244,203,1,25,76,35,15,75,95,85,45,6,26,25,51,
2. 110,145,175,185,195,196,163,121,141,245,217,238,32,55,54,58,57,26,62,42,24,84,48,68,86,95,97,94,
3. 29,39,69,134,154,164,187,184,195,192,162,163,147,145,126,183,184,186,152,150,180,170,140,190,160,
4. 130,120,12,22,13,23,14,24,34,15,25,35,17,27,37,18,28,38,63,65,62,41,52,59,58,57,54,52,152,154,148,
5. 175,169,189,198,163,125,148,176,214,225,248,249,243,247,240,251,255,1,6,84,5,95,6,37,6,84,5,249,
6. 1,236,2,187,65,189,52,147,32,95,6,99,69};

El algoritmo de ordenamiento por seleccion:

Código: C++

1. void ordsel(int * x, int n)
2. {
3.   int minimo=0,i,j;
4.   int swap_;
5.   for(i=0 ; i<n-1 ; i++)
6.   {
7.      minimo=i;
8.      for(j=i+1 ; j<n ; j++)
9.         if (x[minimo] > x[j])
10.            minimo=j;
11.      swap_=x[minimo];
12.      x[minimo]=x[i];
13.      x[i]=swap_;
14.   }
15. }

Donde el primer argumento es el nombre del array, y el segundo el numero de elementos del array

Adjunto una imagen de la simulación, el breakpoint indica aproximadamente 67mS, y como ven, el array se encuentra ordenado, en la captura no se ven los 150 datos, pero estan debidamente organizados 

Para mi proposito, implementare una busqueda del dato mas pequeño, que es mucho mas sencillo.
Saludos y gracias