3. Algoritmo Quicksort e Insersort de ordenación
Páginas: [1]   Ir Abajo
« anterior próximo »

Algoritmo Quicksort e Insersort de ordenación

  • 0 Respuestas
  • 2765 Vistas

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado binary_death

  • *
  • Underc0der
  • Mensajes: 18
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil
    • Email

Algoritmo Quicksort e Insersort de ordenación

  • en: Septiembre 01, 2013, 01:53:25 pm
El algoritmo quicksort, con un ejemplo de implementación:

Código: C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX_ITM 500000
  4. void qsort (int*,int,int);
  5. void swap(int&,int&);
  6. int rdtsc();
  7. int main() {
  8.         int arr[MAX_ITM];
  9.         for (int i=0;i < MAX_ITM;i++) {
  10.             srand(rdtsc());
  11.             arr[i] = rand();
  12.     }
  13.     printf("List initialized. Press enter to sort it...");getchar();
  14.         qsort(arr,0,MAX_ITM-1);
  15.         printf("List sorted. Press enter to print it...");getchar();
  16.         for (int i=0;i < MAX_ITM;i++)
  17.             printf ("%d\t",arr[i]);
  18.     getchar();
  19.     return 0;
  20. }
  21. int rdtsc() {__asm__ __volatile__("rdtsc");}
  22. void swap(int &n, int &m) {int t=n;n=m;m=t;}
  23. void qsort (int arr[],int p,int q) {
  24.         if(q <= p)
  25.              return;
  26.     int piv = arr[p];
  27.     int i=p+1, j=q;
  28.     while(true) {
  29.                 while( (i < q) && (arr[i] <= piv) ) i++;
  30.                 while( (j > p) && (arr[j] >  piv) ) j--;
  31.                 if(j <= i)
  32.                      break;
  33.                            else
  34.                                 swap(arr[i],arr[j]);
  35.     }
  36.     swap(arr[p],arr[j]);
  37.     qsort(arr,p,j-1);
  38.     qsort(arr,j+1,q);
  39.    
  40.  
  41. }
  42.  


Ahora el Insertsort:

Código: C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX_ITM 500000
  4. void isort(int*,int);
  5. int rdtsc();
  6. int main() {
  7.    int arr[MAX_ITM];
  8.    for (int i=0;i < MAX_ITM;i++) {
  9.        srand(rdtsc());
  10.        arr[i] = rand();
  11.     }
  12.     printf("List initialized. Press enter to sort it...");getchar();
  13.    isort(arr,MAX_ITM);
  14.    printf("List sorted. Press enter to print it...");getchar();
  15.    for (int i=0;i < MAX_ITM;i++)
  16.        printf ("%d\t",arr[i]);
  17.     getchar();
  18.     return 0;
  19. }
  20. int rdtsc() {__asm__ __volatile__("rdtsc");}
  21. void isort(int array[], int n) {
  22.      for(int i = 1; i < n; i++) {
  23.              int v = array[i], j = i - 1;
  24.              while(j >=0 && array[j] > v)
  25.                      array[j + 1] = array[j--];
  26.              array[j + 1] = v;
  27.      }
  28.  
  29. }
  30.  
« Última modificación: Septiembre 01, 2013, 02:16:22 pm por binary_death »
En línea
Páginas: [1]   Ir Arriba
« anterior próximo »