Funciones de ordenamiento

Algunos algoritmos están explicados en el Blog.
Algoritmo de ordenamiento – Insertion Sort
Algoritmo de ordenamiento – Quick Sort
Algoritmo de ordenamiento – Merge Sort

Existen muchas facilidades al usar C++, una es el ordenamiento ya que tenemos funciones para ordenar rápidamente vectores o arrays.

Heap sort O(Nlog(N)):

void ordenar(int a[5]){
    make_heap(a, a+5);
    sort_heap(a, a+5);
}

StableSort O(N*log(N^2)):

void ordenar(int a[5]){
    stable_sort(a, a+5);
}

Como se ve C++ nos brinda lo necesario para realizar un ordenamiento, ahora que es mejor utilizar vector de la STL, ej:

vector<int> a(5);
a[0] = 1, a[1] = 10, ..........
sort(a.begin(), a.end());

No olviden incluir <algorithm> para utilizar las funciones en su codigo.

Sorting algorithm – Merge Sort

This algorithm is fast but consumes much memory as you can think of no use to sort arrays of more than 40000 items.
Here is my implementation in C + +, using recursion.

#include <time.h>
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
const int MAX = 30000;
int data[MAX+1];
void mergeSort(int desde, int hasta) {
    if (hasta-desde <= 1) return;
    int middle = (desde+hasta)/2;
    mergeSort(desde, middle);
    mergeSort(middle, hasta);
    int dPtr, lPtr, rPtr, result[hasta];
    dPtr = lPtr = desde;
    rPtr = middle;
    while (dPtr < hasta) {
        if (lPtr == middle)
            result[dPtr++] = data[rPtr++];
        else if(rPtr == hasta)
            result[dPtr++] = data[lPtr++];
        else if (data[lPtr] < data[rPtr])
            result[dPtr++] = data[lPtr++];
        else
            result[dPtr++] = data[rPtr++];
    }
    while(desde < hasta)
        data[desde++] = result[desde];
}

int main() {
    int n;
    printf("Ingresar cuandos datos se ordenarann");
    scanf("%d", &n);
    for(int i=0; i<n ;i++)
        data[i] = rand()%1000000000;
    mergeSort(0, n); //aqui ordena el array de enteros
    for(int i=0; i<n ;i++)
    cout<<data[i]<<" ";
}

As you can see the algorithm is simple, separate all components of the array, then the mixture neatly as the name implies, this separation makes the algorithm does not need to compare all the elements.

         {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}
       {18, 6, 9, 1, 4}     {15, 12, 5, 6, 7, 11}
     {18, 6}   {9, 1, 4}   {15, 12, 5}  {6, 7, 11}
    {18} {6}  {9} {1, 4}   {15} {12, 5} {6} {7, 11}
    {18} {6}  {9} {1}{4}   {15} {12} {5} {6} {7} {11} //end of split section.
    {18} {6}  {9} {1, 4}   {15} {5, 12} {6} {7, 11}
     {6, 18}  {1, 4, 9}     {5, 12, 15} {6, 7, 11}
       {1, 4, 6, 9, 18}     {5, 6, 7, 11, 12, 15}
         {1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18}