Diseño de la Forma de Interfaz de Usuario

SortMethods.pas
 

unit SortMethods; interface uses   Classes, Graphics, ExtCtrls; type	Unit construida por el programador. Comienzo de bloque de declaraciones. Units que contienen librerías Delphi utilizadas. Comienzo de declaraciones de tipos (tipos de datos y clases)
PSortArray = ^TSortArray;   TSortArray = array[0..MaxInt div SizeOf(Integer) - 1]               of Integer;	Definición de tipo Apuntador (Pointer) al tipo de vector a ordenar, el cual se declara a continuación. Esta definición de vector hace posible ordenar vectores de gran tamaño.
TSort = class(TObject)   private     FBox: TPaintBox;     A: PSortArray;     IMin, IMax: Integer;	Definición de Clase abstracta de ordenación (abstracta porque es una defenición genérica, sólo son instanciables sus descendientes). Contiene referencia a un TPaintBox, una referencia o apuntador (pointer) al vector a ordenar y valores de los índices mínimo y máximo de ese particular vector.
procedure VisualSwap(P, Q, I, J: Integer);	Método privado para intercambiar líneas en el gráfico que se use para visualizar el proceso de ordenación.
public     constructor Create(Box: TPaintBox;                       var SortArray: array of Integer);	Método especial constructor de la clase. Devuelve la referencia o apuntador al objeto creado y ejecuta con los valores de los argumentos asignados a los parámetros, las inicializaciones de atributos de la clase: FBox y referencia al vector a ordenar.
procedure Sort; virtual; abstract;   end;	Método de ordenación. Se declara virtual para que clases descendientes lo puedan redefinir polimórficamente. Se declara abstract para indicar que sólo lo implementan clases descendientes. La definición de al menos un método de la clase como abstracto determina que la clase sea abstracta.
TBubbleSort = class(TSort)   public     procedure Sort; override;   end;   TSelectionSort = class(TSort)   public     procedure Sort; override;   end;   TQuickSort = class(TSort)   public     procedure Sort; override;   end;	Definición de tres subclases de la clase abstracta TSort que implementan cada una su versión polimórfica del método Sort. La primera implementa el método de ordenación conocido como Burbuja (bubble), el segundo el método por Selección y el tercero el método llamado Rápido (QuickSort).  El calificativo override indica que se define la versión polimórfica de un método declarado virtual en una clase antecesora.
procedure PaintLine(Canvas: TCanvas; I, Len: Integer);	Procedimiento independiente para dibujar líneas en un objeto de clase TCanvas.
implementation	Comienzo de bloque de implementación de métodos de las clases definidas y de procedimientos y funciones independientes (no asociados a ninguna clase).
procedure PaintLine(Canvas: TCanvas; I, Len: Integer); begin   Canvas.PolyLine([Point(0, I * 2 + 1),                     Point(Len, I * 2 + 1)]); end;	Implementación del procedimiento PaintLine. Recibe por el primer parámetro la referencia al objeto de clase TCanvas donde se dibuja. En posición vertical relativa al Indice I dado se dibuja en el Canvas una línea horizontal de longitud Len. (Ver clase TCanvas en el Help).
constructor TSort.Create(Box: TPaintBox;                  var SortArray: array of Integer); begin   FBox := Box;   A:= @SortArray;   IMin:= Low(SortArray);   IMax:= High(SortArray); end;	Método constructor para creación de objetos de la clase y sus subclases. Recibe por parámetros la referencia al objeto de clase TPaintBox en el cual se dibuja el gráfico que se use para visualizar el proceso de ordenación (pudiera ser nil si no se quire visualizar) y la referencia al vector a ordenar. Primero copia la referencia al TPaintBox a un atributo interno, guarda también la referencia (apuntador) al vector a ordenar y guarda los índices mínimo y máximo del vector. Observe el uso del operador @ para tomar el valor de una dirección de referencia, en este caso, la del vector a ordenar.
procedure TSort.VisualSwap(P, Q, I, J: Integer); begin   if FBox <> nil then with FBox do begin     Canvas.Pen.Color := clBtnFace;     PaintLine(Canvas, I, P);     PaintLine(Canvas, J, Q);     Canvas.Pen.Color := clRed;     PaintLine(Canvas, I, Q);     PaintLine(Canvas, J, P);     end; end;	Si hay visualización, cada vez que en el proceso de ordenación se intercambian posiciones de valores en el vector que se ordena, también se intercambian las líneas correspondientes en el gráfico en el que se visualiza el proceso de ordenación. Con el color de fondo se redibujan las líneas a intercambiar para efecto de borrado. Con el color de las líneas (Rojo) se redibujan las líneas con las longitudes intercambiadas. Los colores y otras declaraciones para uso de TCanvas se encuentran en la Unit Graphics de Delphi.
procedure TBubbleSort.Sort; var   J, T: Integer;  swapped: boolean; begin    repeat     swapped:=false;     for J := IMin to IMax - 1 do       if A^[J] > A^[J + 1] then       begin  swapped:=true;         VisualSwap(A^[J], A^[J + 1], J, J + 1);         T := A^[J];         A^[J] := A^[J + 1];         A^[J + 1] := T;       end;    until not swapped; end;	Implementación del Algoritmo de Ordenación  "Burbuja" como método de la clase TBubbleSort. La variable swapped se usa para parar el proceso cuando en la última vuelta ya no haya habido ningún intercambio, lo cual indica que ya los datos están ordenados. En cada vuelta se comparan todos los pares sucesivos de datos.Cada vez que se encuentra un par desordenado, se intercambian los valores e igualmente se intercambian las líneas en la representación gráfica. Observe la sintaxis de la referencia al elemento del vector por medio de la variable de tipo Apuntador a (Pointer). La estimación del tiempo promedio de ordenación en función del número n de datos y del número de operaciones de comparación requeridas es del orden O(n2).
procedure TSelectionSort.Sort; var   I, J, T: Integer; begin   for I := IMin to IMax - 1 do     for J := IMax downto I + 1 do       if A^[I] > A^[J] then       begin         VisualSwap(A^[I], A^[J], I, J);         T := A^[I];         A^[I] := A^[J];         A^[J] := T;       end; end;	Implementación del Algoritmo de Ordenación  "Selección" como método de la clase TSelectionSort. En cada vuelta controlada por la variable I se intercambian valores entre la posición I y cada elemento menor que se encuentre en cada posición posterior. Así, en cada vuelta se logra que en la posición I quede el valor final del vector ordenado en forma ascendente. Como en cada vuelta disminuye en 1 el número de comparaciones que hay que realizar, el número total de comparaciones para ordenar un vector de n datos es la suma de (n-1) +(n-2)+...+1=(n-1).n/2. O sea, también la estimación del tiempo de ordenación es del orden O(n2).
procedure TQuickSort.Sort;   procedure QuickSort(var A: array of Integer;                        iLo, iHi: Integer);   var     Lo, Hi, Mid, T: Integer;   begin     Lo := iLo;     Hi := iHi;     Mid := A[(Lo + Hi) div 2];     repeat       while A[Lo] < Mid do Inc(Lo);       while A[Hi] > Mid do Dec(Hi);       if Lo <= Hi then       begin         VisualSwap(A[Lo], A[Hi], Lo, Hi);         T := A[Lo];         A[Lo] := A[Hi];         A[Hi] := T;         Inc(Lo);         Dec(Hi);       end;     until Lo > Hi;     if Hi > iLo then QuickSort(A, iLo, Hi);     if Lo < iHi then QuickSort(A, Lo, iHi);   end; begin   QuickSort(A^, 0, Imax); end;	Implementación del Algoritmo de Ordenación  "Rápido" como método de la clase TQuickSort. Declaración del procedimiento embebido dentro del método-procedimiento, y que por lo tanto le es interno, o sea, sólo es utilizable dentro del mismo (esta es una modalidad de definición exclusiva de Pascal).  Este procedimiento embebido está progrmado en forma recursiva. Un procedimiento o función es recursivo cuando se puede invocar a sí mismo. OP soporta la recursividad, encargándose de preservar el estado de las variables y parçametros locales en cada ejecución recursiva. Para que la recursión no entre en un ciclo infinito -posiblemente antes se agota la capacidad de almacenamiento- es necesario que todo algoritmo recursivo contemple condiciones que permiten retornar o salir de la ejecución recursiva.  Observe la declaración del parámetro modificable (modalidad var) A definido de como tipo Open Array de enteros, es decir, sin especificación de tamaño. Observe también el reuso del nombre A interno al procedimiento. (Si fuera necesario usar el nombre A con el significado del atributo definido para la clase como tipo Apuntador, para distinguirlo del uso local habría que calificarlo con el calificativo Self, palabra reservada en OP que representa al Objeto en el que está activo el método. La sintaxis sería: Self.A En cada llamada recursiva al procedimiento interno QuickSort, se logra llevar un elemento de un trozo del vector que se ordena (delimitado por iLo, iHi) hasta su posición final Mid en el vector ordenado y que todos los elementos que queden a su izquierda (pensando al vector como una hilera horizontal de datos) sean menores o a lo sumo iguales a él mientras que todos los que queden a su derecha sean mayores o al menos iguales a él. Si el trozo considerado en la ejecución recursiva consta de más de 3 elementos, hay que volver a llamar recursivamente al procedimiento para realizar la misma tarea sobre los subtrozos a la izquierda y a la derecha del elemento ordenado. Para estimar el número total de comparaciones, consideremos que el algoritmo lo que hace es construir sucesivas particiones del vector. Inicialmente (nivel 0) se trabaja con el vector completo (1=20 porciones). Después se hace una partición (nivel 1) aproximadamente en 2 mitades (2=21 porciones). La siguiente partición (nivel 2) cada mitad a su vez se particiona por la mitad obteniéndose un total de 4=22 porciones. Así, sucesivamente a nivel 3 se tienen 8=23 porciones, a nivel k habrá 2k porciones. En cada nivel k el tamaño aproximado de cada porción es n/2k. Para k ~ log2n, el tamaño de las porciones será ~ 1 (ya que por definición de log: 2log2n=n. Al llegar a ese nivel el proceso de ordenación ha terminado. Como en cada nivel de partición se realizan aproximadamenten comparaciones (¿por qué?) y el proceso implica log2n niveles, el número total estimado de comparaciones necesarias para la ordenación es n.log2n.  Para n grande ( > 128) n >> log2n. El número estimado de comparaciones es del orden O(n.log2n). Los otros dos métodos son O(n2) » O( n.log2n) para n grande. Por eso el Sort Rápido es mucho más eficiente para ordenar vectores grandes.
end.	Fin de la Unit.

Ordena.pas
 

unit Ordena;  interface uses    Windows, Messages, SysUtils, Classes, Graphics, Controls,    Forms, Dialogs,ExtCtrls, StdCtrls;  type   TThreadSortForm = class(TForm)      StartBtn: TButton;	Declaración de la clase de la forma, generada por Delphi respondiendo a la programación visual.
BubbleSortBox: TPaintBox;      SelectionSortBox: TPaintBox;      QuickSortBox: TPaintBox;	TPaintBox es una clase para definir áres rectangulares dentro de una forma. Posee la propiedad Canvas, de clase TCanvas: área de dibujo. Se usan en este ejemplo como cuadros para graficar los vectores que se ordenan.
Label1: TLabel;      Bevel1: TBevel;      Bevel2: TBevel;      Bevel3: TBevel;      Label2: TLabel;      Label3: TLabel;	TBevel es una clase de control para colocar demarcaciones lineales o rectangulares con efecto de alto relive o de bajo relieve; TLabeles otra clase de control para colocar letreros o leyendas dentro de la forma.
procedure BubbleSortBoxPaint(Sender: TObject);      procedure SelectionSortBoxPaint(Sender: TObject);      procedure QuickSortBoxPaint(Sender: TObject);	Procedimientos para redibujar los TBaintBox'es en respuesta a evento Repaint. Este tipo de evento es generado por Windows para redibujar el contenido del Canvas cuando la ventana a la cual pertenece recupera o cambia su visibilidad, ya sea después de haber estado ocultada o haber cambiado de tamaño.
procedure FormCreate(Sender: TObject);	Al iniciarse la ejecución de la aplicación y crearse la Forma, Windows genera el evento OnCreate. En este procedimiento de respuesta a ese evento, se aprovecha para crear los Objetos de Ordenación.
procedure StartBtnClick(Sender: TObject);	Al pulsar el botón se creaaleatoriament un vector desordenado al que se le aplican los métodos de Ordenación.
private     procedure RandomizeArrays;	Procedimiento privado para crear vector desordenado y copias.
public     procedure PaintArray(Box: TPaintBox;              const A: array of integer);   end;	Procedimiento para hacer la representación gráfica de los vectores denttro de las propiedades Canvas de los controles de clase TPaintBox. Observe la declaración del segundo parámetro como referencia a arreglo (vector) no modificable (por estar precedido del calificativo const) de enteros de tamaño indefinido (no se precisa el tamaño), lo cual permite la asignación como argumento de llamada de vectores de diversos tamaños.
PSortArray = ^TSortArray;   TSortArray = array[0..114] of integer;	Definición de tipo Apuntador (Pointer) al tipo de vector a ordenar, el cual se declara a continuación.
var   ThreadSortForm: TThreadSortForm;  implementation uses SortMethods; {$R *.DFM}	Declaración de la variable de referencia al objeto de la clase de forma definida en la aplicación.  Observe la referencia colocada a la otra Unit creada en este proyecto en una instrucción uses dentro de la sección implementation. Esto hay que hacerlo así para permitir referencias circulares (ambas utilizan recursos (tipos, variables, procedimientos,..) declarados en la otra).
var   ArraysRandom: Boolean;   BubbleSortArray, SelectionSortArray, QuickSortArray:       TSortArray;   BubbleSort: TBubbleSort;   SelectionSort: TSelectionSort;   QuickSort: TQuickSort;	Declaración de variables internas de la Unit. TBubbleSort, TSelectionSort y TQuickSort son clases definidas en la otra Unit, SortMethods.
procedure TThreadSortForm.PaintArray(Box: TPaintBox;           const A: array of integer); var   i: Integer; begin   with Box do   begin     Canvas.Pen.Color := clRed;     for i := Low(A) to High(A) do         PaintLine(Canvas, i, A[i]);   end; end;	Definición del método-procedimiento de acceso público agregado a la forma para dibujar líneas en el Canvas del objeto de clase TPaintBox, cuya referencia se envía como primer parámetro. Cada elemento del vector cuya referencia se envía por el segundo parámetro, se representa por una línea de tamaño en pixeles igual a su valor numérico. Para dibujar las línea se utiliza el procedimiento PaintLine definido en la otra Unit. Las líneas se dibujan en color Rojo (clRed, definido en Unit Graphics).
procedure TThreadSortForm.BubbleSortBoxPaint(Sender:                   TObject);  begin   PaintArray(BubbleSortBox, BubbleSortArray); end; procedure TThreadSortForm.SelectionSortBoxPaint(Sender:                   TObject);  begin   PaintArray(SelectionSortBox, SelectionSortArray); end;  procedure TThreadSortForm.QuickSortBoxPaint(Sender:                   TObject);  begin    PaintArray(QuickSortBox, QuickSortArray); end;	En respuesta al evento OnPaint en cada uno de los objetos TPaintBox asociados a cada uno de los métodos de ordenación probados, se redibuja  vector asociado utilizando el método PaintArray ya definido.
procedure TThreadSortForm.FormCreate(Sender: TObject);  begin   ArraysRandom:=False;   RandomizeArrays;   BubbleSort:=TBubbleSort.Create(BubbleSortBox,                                   BubbleSortArray);   SelectionSort:=TSelectionSort.Create(SelectionSortBox,                                        SelectionSortArray);   QuickSort:=TQuickSort.Create(QuickSortBox,                                 QuickSortArray); end;	Al crear Windows la forma genera el evento OnCreate. En este método de respuesta al evento, las dos primeras instrucciones inicializan una bandera o marca y los vectores asociados a los métodos de ordenación probados.  La bandera es la variable booleana ArraysRandom que sirve para indicar cuando se deben generar datos aleatorios. RandomizeArrays es el método privado definido en la clase de la forma para generar datos aleatorios en los vectores asociados a los métodos de ordenación probados. Luego se crean los objetos asociados a los métodos de Ordenación: BubbleSort para el método de la Burbuja, SelectionSort para el método de Selección y QuickSort para el método Rápido.
procedure TThreadSortForm.StartBtnClick(Sender: TObject);  begin   RandomizeArrays;   StartBtn.Enabled := False;   BubbleSort.Sort;   ShowMessage('End Bubble Sort');   SelectionSort.Sort;   ShowMessage('End Selection Sort');   QuickSort.Sort;   ShowMessage('End Quick Sort');   ArraysRandom:=false;   StartBtn.Enabled := True; end;	Al pulsar el botón, se re-inicializan los vectores, se deshabilita el botón hasta que se hayan realizado las tres ordenaciones y se ejecutan los tres métodos de ordenación en secuencia, invocando al método Sort en cada uno de los tres objetos de Ordenación.  Se intercalan mensajes para que el usuario aprecie las diferencias en los tiempos de ejecución. Al finalizar, se restaura el estado del botón.
procedure TThreadSortForm.RandomizeArrays; var   i: Integer; begin   if not ArraysRandom then   begin     Randomize;     for i := Low(BubbleSortArray) to High(BubbleSortArray)      do BubbleSortArray[I] := Random(88);     SelectionSortArray := BubbleSortArray;     QuickSortArray := BubbleSortArray;     ArraysRandom := True;     Repaint;   end; end;	Método privado de la clase de la forma para generar aleatoriamente valores para los vectores asociados a los tres métodos de ordenación probados. Randomize: Procedimiento nativo de OP para reinicializar semilla de generación de números aleatorios. Se inicializa primero el vector asociado al método de la Burbuja, desde su primer elemento, cuyo índice es obtenido por la función Low de OP, hasta el último, cuyo índice es obtenido por la función High, asignándoles aleatoriamente valores entre 1 y 88. (El rango 1..88 se corresponde con el tamaño de los cuadros de dibujo en los TPaintBox) Los otros dos vectores se inicializan por copia del primero. Se invoca internamente al método Repaint de la forma para que Windows provoque la ocurrencia del evento OnPaint, lo cual a su vez desecandena la ocurrencia de eventos OnPaint en los TPaintBox asociados a los métodos de ordenación para que se muestren los vectores graficados.
end.	Fin de la Unit.

Ordena.dfm
 

object ThreadSortForm: TThreadSortForm    Left = 212    Top = 110    BorderStyle = bsDialog    Caption = 'Ordenación '    ClientHeight = 295    ClientWidth = 297    Color = clBtnFace    Font.Charset = DEFAULT_CHARSET    Font.Color = clWindowText    Font.Height = -11    Font.Name = 'MS Sans Serif'    Font.Style = []    OldCreateOrder = True    Position = poScreenCenter    OnCreate = FormCreate    PixelsPerInch = 96    TextHeight = 13    object Bevel1: TBevel      Left = 8      Top = 24      Width = 89      Height = 233    end    object Bevel3: TBevel      Left = 200      Top = 24      Width = 89      Height = 233    end    object Bevel2: TBevel      Left = 105      Top = 24      Width = 89      Height = 233    end    object BubbleSortBox: TPaintBox      Left = 8      Top = 24      Width = 89      Height = 233      OnPaint = BubbleSortBoxPaint    end    object SelectionSortBox: TPaintBox      Left = 104      Top = 24      Width = 89      Height = 233      OnPaint = SelectionSortBoxPaint    end    object QuickSortBox: TPaintBox      Left = 200      Top = 24      Width = 89      Height = 233      OnPaint = QuickSortBoxPaint    end    object Label1: TLabel      Left = 8      Top = 8      Width = 55      Height = 13      Caption = 'Bubble Sort'    end    object Label2: TLabel      Left = 104      Top = 8      Width = 66      Height = 13      Caption = 'Selection Sort'    end    object Label3: TLabel      Left = 200      Top = 8      Width = 50      Height = 13      Caption = 'Quick Sort'    end    object StartBtn: TButton      Left = 112      Top = 264      Width = 75      Height = 25      Caption = 'Start Sorting'      TabOrder = 0      OnClick = StartBtnClick    end  end

Ordenacion.dpr
 

program Ordenacion;  uses    Forms,    Ordena in 'Ordena.pas' {ThreadSortForm},    SortMethods in 'SortMethods.pas';  {$R *.RES} begin   Application.CreateForm(TThreadSortForm,                          ThreadSortForm);   Application.Run;  end.

A este programa se le agregó una Unit: SortMethods, que no posee  ninguna interfaz gráfica. Contiene definiciones de una clase abstracta para ordenación y tres subclases que implementan tres diferentes métodos de ordenación de vectores de números enteros.