orden.pas

   1           (**************************************************)\r
   2           (*                                                *)\r
   3           (*           ALGORITMOS DE ORDENAMIENTO           *)\r
   4           (*           ========== == ============           *)\r
   5           (*                                                *)\r
   6           (**************************************************)\r
   7 \r
   8 program Ordenamientos;\r
   9 \r
  10 const\r
  11     MAX = 15;\r
  12 \r
  13 type\r
  14     Dato = Integer;\r
  15     Vector = array [1..MAX] of Dato;\r
  16 \r
  17 \r
  18 (****************************************************\r
  19  *\r
  20  * BUBBLE SORT.\r
  21  *\r
  22  ****************************************************)\r
  23 \r
  24  procedure bubbleSort(var v: Vector;      { Vector a ordenar }\r
  25                           min,            { Valor de donde se comienza a ordenar }\r
  26                           max: Integer);  { Valor en donde se termina de ordenar }\r
  27 \r
  28    var\r
  29       i, j, aux: integer;\r
  30 \r
  31    begin\r
  32         if min < max then\r
  33            for i := max - 1 downto min do\r
  34                for j := min to i do\r
  35                    if v[j] > v[j+1] then begin\r
  36                       aux := v[j];\r
  37                       v[j] := v[j+1];\r
  38                       v[j+1] := aux;\r
  39                    end;\r
  40    end; { bubbleSort }\r
  41 \r
  42 (****************************************************\r
  43  *\r
  44  * BUBBLE SORT MEJORADO.\r
  45  *\r
  46  ****************************************************)\r
  47 \r
  48  procedure bubbleSortMejor(var v: Vector;      { Vector a ordenar }\r
  49                                min,            { Valor de donde se comienza a ordenar }\r
  50                                max: Integer);  { Valor en donde se termina de ordenar }\r
  51 \r
  52    var\r
  53       i, j, aux: integer;\r
  54       huboInt: Boolean;\r
  55 \r
  56    begin\r
  57         huboInt := false;\r
  58         i := max - 1;\r
  59         if min < max then\r
  60            repeat\r
  61                for j := min to i do\r
  62                    if v[j] > v[j+1] then begin\r
  63                       aux := v[j];\r
  64                       v[j] := v[j+1];\r
  65                       v[j+1] := aux;\r
  66                       huboInt := true;\r
  67                    end;\r
  68                i := i - 1;\r
  69            until not huboInt;\r
  70    end; { bubbleSortMejor }\r
  71 \r
  72 (****************************************************\r
  73  *\r
  74  * SHAKE SORT (o Bubble Sort Bidireccional).\r
  75  *\r
  76  ****************************************************)\r
  77 \r
  78  procedure shakeSort(var v: Vector;      { Vector a ordenar }\r
  79                          min,            { Valor de donde se comienza a ordenar }\r
  80                          max: Integer);  { Valor en donde se termina de ordenar }\r
  81 \r
  82    var\r
  83       i, fin, ini, aux, tmp: integer;\r
  84 \r
  85    begin\r
  86         fin := max - 1;\r
  87         ini := min;\r
  88         if min < max then\r
  89            repeat\r
  90                tmp := ini;\r
  91                for i := ini to fin do\r
  92                    if v[i] > v[i+1] then begin\r
  93                       aux := v[i];\r
  94                       v[i] := v[i+1];\r
  95                       v[i+1] := aux;\r
  96                       tmp := i;\r
  97                    end;\r
  98                fin := tmp;\r
  99                for i := fin downto ini do\r
 100                    if v[i] > v[i+1] then begin\r
 101                       aux := v[i];\r
 102                       v[i] := v[i+1];\r
 103                       v[i+1] := aux;\r
 104                       tmp := i;\r
 105                    end;\r
 106                ini := tmp;\r
 107            until ini >= fin;\r
 108    end; { shakeSort }\r
 109 \r
 110 (****************************************************\r
 111  *\r
 112  * INSERTION SORT.\r
 113  *\r
 114  ****************************************************)\r
 115 \r
 116  procedure insertionSort(var v: Vector;  { Vector a ordenar }\r
 117                          min,            { Valor de donde se comienza a ordenar }\r
 118                          max: Integer);  { Valor en donde se termina de ordenar }\r
 119 \r
 120    var\r
 121       i, j: integer;\r
 122       tmp: Dato;\r
 123       huboInt: Boolean;\r
 124 \r
 125    begin\r
 126         if min < max then\r
 127            for i := min + 1 to max do begin\r
 128              tmp := v[i];\r
 129              j := i - 1;\r
 130              huboInt := true;\r
 131              while (j >= 1) and huboInt do\r
 132                 if v[j] > tmp then begin\r
 133                    v[j+1] := v[j];\r
 134                    j := j - 1;\r
 135                 end else\r
 136                    huboInt := false;\r
 137              v[j+1] := tmp;\r
 138            end;\r
 139    end; { insertionSort }\r
 140 \r
 141 (****************************************************\r
 142  *\r
 143  * QUICK SORT.\r
 144  *\r
 145  ****************************************************)\r
 146 \r
 147  procedure quickSort(var v: Vector;      { Vector a ordenar }\r
 148                          min,            { Valor de donde se comienza a ordenar }\r
 149                          max: Integer);  { Valor en donde se termina de ordenar }\r
 150 \r
 151    var\r
 152       ini, fin, medio: integer;\r
 153       aux, tmp: Dato;\r
 154 \r
 155    begin\r
 156         if min >= max then\r
 157            exit;\r
 158         ini := min;\r
 159         fin := max;\r
 160         medio := (min + max) div 2;\r
 161         tmp := v[medio];\r
 162         repeat\r
 163            while v[ini] < tmp do\r
 164                  ini := ini + 1;\r
 165            while v[fin] > tmp do\r
 166                  fin := fin - 1;\r
 167            if ini <= fin then begin\r
 168               if ini < fin then begin\r
 169                  aux := v[ini];\r
 170                  v[ini] := v[fin];\r
 171                  v[fin] := aux;\r
 172               end;\r
 173               ini := ini + 1;\r
 174               fin := fin - 1;\r
 175            end;\r
 176         until ini > fin;\r
 177         if min < fin then\r
 178            quickSort(v, min, fin);\r
 179         if max > ini then\r
 180            quickSort(v, ini, max);\r
 181    end; { quickSort }\r
 182 \r
 183 (****************************************************\r
 184  *\r
 185  * SHELL'S SORT.\r
 186  *\r
 187  ****************************************************)\r
 188 \r
 189  procedure Shellsort( var v : Vector;       { Vector a ordenar }\r
 190                           min,              { Valor de donde se comienza a ordenar }\r
 191                           max : Integer );  { Valor en donde se termina de ordenar }\r
 192 \r
 193    var\r
 194       i, j, medio : Integer;\r
 195       tmp : Dato;\r
 196 \r
 197    begin\r
 198         medio := max - min + 1;\r
 199         while medio > 1 do begin\r
 200            if medio < 5 then\r
 201               medio := 1\r
 202            else\r
 203               medio := trunc( 0.45454 * medio );\r
 204           {*** Do linear insertion sort in steps size d ***}\r
 205           for i := max - medio downto min do begin\r
 206               tmp := v[i];\r
 207               j := i + medio;\r
 208               while j <= max do\r
 209                  if tmp > v[j] then begin\r
 210                     v[j-medio] := v[j];\r
 211                     j := j + medio\r
 212                  end else\r
 213                     break;\r
 214               v[j-medio] := tmp\r
 215           end;\r
 216         end;\r
 217    end; { Shellsort }\r
 218 \r
 219 \r
 220 (************************************************************************)\r
 221 \r
 222  procedure verVector(var v: Vector; s: String);\r
 223 \r
 224    var\r
 225       i: Integer;\r
 226 \r
 227    begin\r
 228         (** MUESTRA VECTOR **)\r
 229         writeln(s);\r
 230         for i := 1 to MAX do\r
 231             write(' | ', v[i]);\r
 232         writeln(' | ');\r
 233         writeln;\r
 234    end; { verVector }\r
 235 \r
 236 \r
 237 (************************************************************************)\r
 238 \r
 239  procedure cargarVector(var v: Vector);\r
 240 \r
 241    var\r
 242       i: Integer;\r
 243 \r
 244    begin\r
 245         (** INICIALIZA VECTOR **)\r
 246         for i := 1 to MAX do\r
 247             v[i] := round(random * 100);\r
 248    end; { cargarVector }\r
 249 \r
 250 \r
 251 (************************************************************************)\r
 252 (************************************************************************)\r
 253 (*                       PROGRAMA PRINCIPAL                             *)\r
 254 \r
 255 var\r
 256    i: Integer;\r
 257    v, w: Vector;\r
 258 \r
 259 begin\r
 260      cargarVector(w);\r
 261      v := w;\r
 262      verVector(v, 'Desordenado:');\r
 263      bubbleSort(v, 1, MAX);\r
 264      verVector(v, 'Bubble Sort:');\r
 265      bubbleSortMejor(v, 1, MAX);\r
 266      verVector(v, 'Bubble Sort Mejorado:');\r
 267      v := w;\r
 268      shakeSort(v, 1, MAX);\r
 269      verVector(v, 'Shake Sort (Bubble Sort Bidireccional):');\r
 270      v := w;\r
 271      insertionSort(v, 1, MAX);\r
 272      verVector(v, 'Insertion Sort:');\r
 273      v := w;\r
 274      quickSort(v, 1, MAX);\r
 275      verVector(v, 'Quick Sort:');\r
 276      v := w;\r
 277      shellSort(v, 1, MAX);\r
 278      verVector(v, 'Shell''s Sort:');\r
 279 end.\r
 280 \r