Métodos de Ordenamiento. Explication básica de Quicksort

Métodos de Ordenamiento

Paucar Criollo Isaias Moisés

Facultad de Ingeniería en Ciencias Aplicadas, Electricidad, Universidad Técnica del Norte, Ibarra, Ecuador.

Impaucarc@utn.edu.ec

Abstract— El tema a realizar fue el de indagar respecto a temas de ordenamiento, específicamente sobre los tipos de ordenamiento que existen, pero esencialmente a escoger 3 de los cuales se has llamado más la atención para procederlos a realizar y a ejecutarse

 I. INTRODUCCION

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.Ej. de ordenamientos: ir. telefónico, tablas de contenido, bibliotecas y diccionarios, etc. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.

II. DESAROLLO

Explication básica de Quicksort

Este algoritmo selecciona un pivote, y después establece dos apuntadores en los extremos del arreglo. Va acercando entre sí los índices (es decir, disminuye el de la derecha y aumenta el de la izquierda) hasta que encuentra un elemento que se puede intercambiar.

Un elemento intercambiable es aquel que es más pequeño que el pivote, pero está a su derecha, o que es más grande que el pivote, pero está a su izquierda. En otras palabras, un elemento que no está ordenado. Si encuentra el elemento intercambiable, lo intercambia y sigue acercando los punteros hasta que los mismos se cruzan o izquierda es mayor o igual que derecha.

Ejemplo:

/*

UNIVERSIDAD TECNICA DEL NORTE

CARRERA DE ELECTRICIDAD

PROGRAMACION

Isaias Moises Puacar Criollo

la función QUICKSORT

*/

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

int compara_enteros(const void *p, const void *q);

int compara_flotantes(const void *p, const void *q);

int main()

{

    int i, ta, tb;

    int a[] = {10, 6, -23, 48, 1, 2, 3, 7, 6, 5};

    float b[] = {1.79f, 5.34f, 2.67f, -12.456};

    ta = sizeof(a) / sizeof(int);

    tb = sizeof(b) / sizeof(float);

    qsort(a, ta, sizeof(int),compara_enteros);

    qsort(b, tb, sizeof(float),compara_flotantes);

    for(i = 0; i < ta;i++)

        printf("%d\t",a[i]);

    printf("\n");

    for(i = 0; i < tb;i++)

        printf("%f\t",b[i]);

    printf("\n");

    getch();

    return 0;

}

int compara_enteros(const void *p, const void *q)

{

    int x, y;

    x = *(int *)p;

    y = *(int *)q;

    if(x > y)

        return -1;

    if(x == y)

        return 0;

    return 1;

}

int compara_flotantes(const void *p, const void *q)

{

    float x, y;

    x = *(float *)p;

    y = *(float *)q;

    if(x > y)

        return -1;

    if(x == y)

        return 0;

    return 1;

}

[pic 1]   

El ordenamiento por selección

El ordenamiento por selección mejora el ordenamiento burbuja haciendo un sólo intercambio por cada pasada a través de la lista. Para hacer esto, un ordenamiento por selección busca el valor mayor a medida que hace una pasada y, después de completar la pasada, lo pone en la ubicación correcta. Al igual que con un ordenamiento burbuja, después de la primera pasada, el ítem mayor está en la ubicación correcta. Después de la segunda pasada, el siguiente mayor está en su ubicación. Este proceso continúa y requiere n−1n−1 pasadas para ordenar los n ítems, ya que el ítem final debe estar en su lugar después de la (n−1)(n−1)-ésima pasada.                                                           

...