Algoritmo Quicksort e Insersort de ordenación

  • 0 Respuestas
  • 2974 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) You are not allowed to view links. Register or Login
#include <stdio.h>
#include <stdlib.h>
#define MAX_ITM 500000
void qsort (int*,int,int);
void swap(int&,int&);
int rdtsc();
int main() {
        int arr[MAX_ITM];
        for (int i=0;i < MAX_ITM;i++) {
            srand(rdtsc());
            arr[i] = rand();
    }
    printf("List initialized. Press enter to sort it...");getchar();
        qsort(arr,0,MAX_ITM-1);
        printf("List sorted. Press enter to print it...");getchar();
        for (int i=0;i < MAX_ITM;i++)
            printf ("%d\t",arr[i]);
    getchar();
    return 0;
}
int rdtsc() {__asm__ __volatile__("rdtsc");}
void swap(int &n, int &m) {int t=n;n=m;m=t;}
void qsort (int arr[],int p,int q) {
        if(q <= p)
             return;
    int piv = arr[p];
    int i=p+1, j=q;
    while(true) {
                while( (i < q) && (arr[i] <= piv) ) i++;
                while( (j > p) && (arr[j] >  piv) ) j--;
                if(j <= i)
                     break;
                           else
                                swap(arr[i],arr[j]);
    }
    swap(arr[p],arr[j]);
    qsort(arr,p,j-1);
    qsort(arr,j+1,q);
   
 
}


Ahora el Insertsort:

Código: (C) You are not allowed to view links. Register or Login
#include <stdio.h>
#include <stdlib.h>
#define MAX_ITM 500000
void isort(int*,int);
int rdtsc();
int main() {
int arr[MAX_ITM];
for (int i=0;i < MAX_ITM;i++) {
    srand(rdtsc());
    arr[i] = rand();
    }
    printf("List initialized. Press enter to sort it...");getchar();
isort(arr,MAX_ITM);
printf("List sorted. Press enter to print it...");getchar();
for (int i=0;i < MAX_ITM;i++)
    printf ("%d\t",arr[i]);
    getchar();
    return 0;
}
int rdtsc() {__asm__ __volatile__("rdtsc");}
void isort(int array[], int n) {
     for(int i = 1; i < n; i++) {
             int v = array[i], j = i - 1;
             while(j >=0 && array[j] > v)
                     array[j + 1] = array[j--];
             array[j + 1] = v;
     }
 
}
« Última modificación: Septiembre 01, 2013, 02:16:22 pm por binary_death »