(**************************************************)
          (*                                                *)
          (*           ALGORITMOS DE ORDENAMIENTO           *)
          (*           ========== == ============           *)
          (*                                                *)
          (**************************************************)

program Ordenamientos;

const
    MAX = 15;

type
    Dato = Integer;
    Vector = array [1..MAX] of Dato;


(****************************************************
 *
 * BUBBLE SORT.
 *
 ****************************************************)

 procedure bubbleSort(var v: Vector;      { Vector a ordenar }
                          min,            { Valor de donde se comienza a ordenar }
                          max: Integer);  { Valor en donde se termina de ordenar }

   var
      i, j, aux: integer;

   begin
        if min < max then
           for i := max - 1 downto min do
               for j := min to i do
                   if v[j] > v[j+1] then begin
                      aux := v[j];
                      v[j] := v[j+1];
                      v[j+1] := aux;
                   end;
   end; { bubbleSort }

(****************************************************
 *
 * BUBBLE SORT MEJORADO.
 *
 ****************************************************)

 procedure bubbleSortMejor(var v: Vector;      { Vector a ordenar }
                               min,            { Valor de donde se comienza a ordenar }
                               max: Integer);  { Valor en donde se termina de ordenar }

   var
      i, j, aux: integer;
      huboInt: Boolean;

   begin
        huboInt := false;
        i := max - 1;
        if min < max then
           repeat
               for j := min to i do
                   if v[j] > v[j+1] then begin
                      aux := v[j];
                      v[j] := v[j+1];
                      v[j+1] := aux;
                      huboInt := true;
                   end;
               i := i - 1;
           until not huboInt;
   end; { bubbleSortMejor }

(****************************************************
 *
 * SHAKE SORT (o Bubble Sort Bidireccional).
 *
 ****************************************************)

 procedure shakeSort(var v: Vector;      { Vector a ordenar }
                         min,            { Valor de donde se comienza a ordenar }
                         max: Integer);  { Valor en donde se termina de ordenar }

   var
      i, fin, ini, aux, tmp: integer;

   begin
        fin := max - 1;
        ini := min;
        if min < max then
           repeat
               tmp := ini;
               for i := ini to fin do
                   if v[i] > v[i+1] then begin
                      aux := v[i];
                      v[i] := v[i+1];
                      v[i+1] := aux;
                      tmp := i;
                   end;
               fin := tmp;
               for i := fin downto ini do
                   if v[i] > v[i+1] then begin
                      aux := v[i];
                      v[i] := v[i+1];
                      v[i+1] := aux;
                      tmp := i;
                   end;
               ini := tmp;
           until ini >= fin;
   end; { shakeSort }

(****************************************************
 *
 * INSERTION SORT.
 *
 ****************************************************)

 procedure insertionSort(var v: Vector;  { Vector a ordenar }
                         min,            { Valor de donde se comienza a ordenar }
                         max: Integer);  { Valor en donde se termina de ordenar }

   var
      i, j: integer;
      tmp: Dato;
      huboInt: Boolean;

   begin
        if min < max then
           for i := min + 1 to max do begin
             tmp := v[i];
             j := i - 1;
             huboInt := true;
             while (j >= 1) and huboInt do
                if v[j] > tmp then begin
                   v[j+1] := v[j];
                   j := j - 1;
                end else
                   huboInt := false;
             v[j+1] := tmp;
           end;
   end; { insertionSort }

(****************************************************
 *
 * QUICK SORT.
 *
 ****************************************************)

 procedure quickSort(var v: Vector;      { Vector a ordenar }
                         min,            { Valor de donde se comienza a ordenar }
                         max: Integer);  { Valor en donde se termina de ordenar }

   var
      ini, fin, medio: integer;
      aux, tmp: Dato;

   begin
        if min >= max then
           exit;
        ini := min;
        fin := max;
        medio := (min + max) div 2;
        tmp := v[medio];
        repeat
           while v[ini] < tmp do
                 ini := ini + 1;
           while v[fin] > tmp do
                 fin := fin - 1;
           if ini <= fin then begin
              if ini < fin then begin
                 aux := v[ini];
                 v[ini] := v[fin];
                 v[fin] := aux;
              end;
              ini := ini + 1;
              fin := fin - 1;
           end;
        until ini > fin;
        if min < fin then
           quickSort(v, min, fin);
        if max > ini then
           quickSort(v, ini, max);
   end; { quickSort }

(****************************************************
 *
 * SHELL'S SORT.
 *
 ****************************************************)

 procedure Shellsort( var v : Vector;       { Vector a ordenar }
                          min,              { Valor de donde se comienza a ordenar }
                          max : Integer );  { Valor en donde se termina de ordenar }

   var
      i, j, medio : Integer;
      tmp : Dato;

   begin
        medio := max - min + 1;
        while medio > 1 do begin
           if medio < 5 then
              medio := 1
           else
              medio := trunc( 0.45454 * medio );
          {*** Do linear insertion sort in steps size d ***}
          for i := max - medio downto min do begin
              tmp := v[i];
              j := i + medio;
              while j <= max do
                 if tmp > v[j] then begin
                    v[j-medio] := v[j];
                    j := j + medio
                 end else
                    break;
              v[j-medio] := tmp
          end;
        end;
   end; { Shellsort }


(************************************************************************)

 procedure verVector(var v: Vector; s: String);

   var
      i: Integer;

   begin
        (** MUESTRA VECTOR **)
        writeln(s);
        for i := 1 to MAX do
            write(' | ', v[i]);
        writeln(' | ');
        writeln;
   end; { verVector }


(************************************************************************)

 procedure cargarVector(var v: Vector);

   var
      i: Integer;

   begin
        (** INICIALIZA VECTOR **)
        for i := 1 to MAX do
            v[i] := round(random * 100);
   end; { cargarVector }


(************************************************************************)
(************************************************************************)
(*                       PROGRAMA PRINCIPAL                             *)

var
   i: Integer;
   v, w: Vector;

begin
     cargarVector(w);
     v := w;
     verVector(v, 'Desordenado:');
     bubbleSort(v, 1, MAX);
     verVector(v, 'Bubble Sort:');
     bubbleSortMejor(v, 1, MAX);
     verVector(v, 'Bubble Sort Mejorado:');
     v := w;
     shakeSort(v, 1, MAX);
     verVector(v, 'Shake Sort (Bubble Sort Bidireccional):');
     v := w;
     insertionSort(v, 1, MAX);
     verVector(v, 'Insertion Sort:');
     v := w;
     quickSort(v, 1, MAX);
     verVector(v, 'Quick Sort:');
     v := w;
     shellSort(v, 1, MAX);
     verVector(v, 'Shell''s Sort:');
end.