erick@the net. Bubble, Insert, Select,Quick, Merge, Heap and Bucket sort race!

This is a program written in C++, using BorlandC 5.0´s Object Windows Library (OWL). I did this for Alejandro, a friend of mine, who needed this for a class about algorithms performance. It runs 7 different sort threads concurrently (Bubble Sort, Insert Sort,Select Sort, Quick Sort, Heap Sort, Merge Sort and Bucket Sort, and displays calculation time and number of basic operations.

Download Sort.zip (Win95/NT only. Linux: Forgive me father...)
Back to erick@the net

And if you want to take a peek to the C++ source file:

/*	Sort. Aplicación para Windows 95 o NT. Evalua el desempeño de 7 diferentes
 * algoritmos:
 * - Algoritmo "Burbujas"
 * - Algoritmo "Insertar"
 * - Algoritmo "Seleccionar"
 * - Algoritmo "Quicksort" o "Rápido"
 * - Algoritmo "Heapsort" o "Montículo"
 * - Algoritmo "Mergesort" o "Mezclar"
 * - Algoritmo "Bucket" o "Casillas"

 * Esta aplicación utiliza las librerias de Object Windows Library, de
 	Borland C 5.0. No podr� compilar este programa con otros compiladores
   (Por ejemplo MS Visual C, o con una versión anterior de Borland que no
   soporte OWL. *

*/

//Sección de "includes" para las librerias que necesitamos.

#include "owl/pch.h"
#include "owl/applicat.h"
#include "owl/framewin.h"
#include "owl/inputdia.h"
#include "owl/static.h"
#include "owl/edit.h"
#include "classlib/thread.h"
#include "stdio.h"
#include "stdlib.h"
#include "values.h"
#include "sort.rh"
#include "alloc.h"
#include "time.h"

#define MAX_VALUE		1000	// Máximo entero aleatorio (Toca limitar por culpa de
									// Bucket Sort

// n: Tamaño de la matriz. Default = 1000 números
int n=1000;

// Scramble crea la matriz de enteros con elementos aleatorios.

void Scramble(int *T){
int i;

	randomize();
	for(i=0;iStatusMessage("Pensando...");
   s=clock();
	do{
   	flag=false; ops++;
      for(i=0;iT[i+1]){
         	t=T[i];			ops++;
            T[i]=T[i+1];	ops+=2;
            T[i+1]=t;		ops+=2;
				flag=true;		ops++;
			}
      }	ops++;
   } while(flag);
   e=clock();
   delay=(e-s)/CLK_TCK*1000;
   sprintf(buf,"Hecho!. Tiempo transcurrido: %6d ms. Operaciones básicas: %d"\
   		,delay,ops);
   dad->StatusMessage(buf);
   return 0;
}

// InsertSortAlgorithm es el thread que implementa el algoritmo "Insertar"

class InsertSortAlgorithm:public SortThread{
public:
	InsertSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int Run();
};

// El método Run del thread InsertSortAlgorithm es quien ejecuta el algoritmo

int InsertSortAlgorithm::Run(){
int i,j,t,delay,ops=0;
char buf[256];
clock_t s,e;

   dad->StatusMessage("Pensando...");
   s=clock();
 	for(i=1;i=0 && tStatusMessage(buf);
   return 0;
}

// SelectSortAlgorithm es el thread que implementa el algoritmo "Seleccionar"

class SelectSortAlgorithm:public SortThread{
public:
	SelectSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int Run();
};

// El método Run del thread SelectSortAlgorithm es quien ejecuta el algoritmo

int SelectSortAlgorithm::Run(){
int i,j,minj,minx,delay,ops=0;
char buf[256];
clock_t s,e;

   dad->StatusMessage("Pensando...");
   s=clock();
 	for(i=0;iStatusMessage(buf);
   return 0;
}

// QuickSortAlgorithm es el thread que implementa el algoritmo "Rápido"

class QuickSortAlgorithm:public SortThread{
public:
	QuickSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int ops;
	int Run();
   void QSort(int lo0,int hi0);
   void QSort();
};
void QuickSortAlgorithm::QSort(int lo0,int hi0){
int lo = lo0;
int hi = hi0;

	if(lo >= hi) {	ops++;
	    return;
	}
	int mid = T[(lo + hi) / 2];	ops++;
	while(lo < hi  && T[lo]!=T[hi]) {	ops+=3;
		while(lo mid) {	ops+=3;
			hi--;	ops++;
      }
      ops++;
	   if(lo < hi) {
			int t = T[lo];	ops++;
			T[lo] = T[hi];	ops++;
			T[hi] = t;	ops++;
	   }
	}
   ops++;
	if (hi < lo ) {
	   int t = hi;	ops++;
		hi = lo;	ops++;
		lo = t;	ops++;
	}
	QSort(lo0, lo);
	QSort(lo==lo0 ? lo+1 : lo, hi0);	ops+=2;
}

void QuickSortAlgorithm::QSort(){
	ops=0;
	QSort(0,n-1);
}

// El método Run del thread QuickSortAlgorithm es quien ejecuta el algoritmo

int QuickSortAlgorithm::Run(){
int delay;
char buf[256];
clock_t s,e;

   dad->StatusMessage("Pensando...");
   s=clock();
   QSort();
   e=clock();
   delay=(e-s)/CLK_TCK*1000;
   sprintf(buf,"Hecho!. Tiempo transcurrido: %6d ms. Operaciones básicas: %d",\
   		delay,ops);

   dad->StatusMessage(buf);
   return 0;
}

// HeapSortAlgorithm es el thread que implementa el algoritmo "Montículo"

class HeapSortAlgorithm:public SortThread{
public:
	HeapSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int ops;
	int Run();
   void Heapify();
   void Pushdown(int which,int limit);
};

void HeapSortAlgorithm::Pushdown(int which,int limit){
int t;

  /* we will determine the node's max child */
  int max_child = which * 2;	ops++;

  /* if this is a leaf node (i.e. it has no children) then we're done */
  ops++;
  if (max_child > limit) return;

  /* if it has a second child, make max_child the index of the greater kid */
  ops+=3;
  if (((which * 2) + 1) <= limit){
    ops+=3;
    if (T[max_child] < T[(which * 2) + 1]) { ops+=3;
    	max_child = (which * 2) + 1;
    }
  }

  /* now see if the node in question if greater than its max child... */
  ops++;
  if (T[which] < T[max_child]) {

    /* if it's not, swap them and keep going with the push down */
    t=T[which];T[which]=T[max_child];T[max_child]=t;ops+=3;
    Pushdown(max_child, limit);
  }
}

void HeapSortAlgorithm::Heapify(){

  /* we only have to start at the first node with children */
  int mid = (n-1) / 2;	ops++;
  int i;

  /* work backwards to the top of the heap calling pushdown */
  for (i = mid; i >= 0; i--) { ops+=2;
  	Pushdown(i, n-1);
  }
}

// El método Run del thread HeapSortAlgorithm es quien ejecuta el algoritmo

int HeapSortAlgorithm::Run(){
int i,t,delay;
char buf[256];
clock_t s,e;

   dad->StatusMessage("Pensando...");
   s=clock();
	ops=0;
   Heapify();
   for(i=n-1;i?i--){	ops+=2;
   	t=T[i];	ops++;
      T[i]=T[0];	ops++;
      T[0]=t;	ops++;
      Pushdown(0,i-1);
   }

   e=clock();
   delay=(e-s)/CLK_TCK*1000;
   sprintf(buf,"Hecho!. Tiempo transcurrido: %6d ms. Operaciones básicas: %d",\
   		delay,ops);

   dad->StatusMessage(buf);
   return 0;
}

// MergeSortAlgorithm es el thread que implementa el algoritmo "Seleccionar"

class MergeSortAlgorithm:public SortThread{
public:
	MergeSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int Run();
   int ops;
   void MergeSort(int left,int right);
   void merge(int first1,int last1,int first2,int last2);
   void move (int *list1, int first1, int last1, int *list2, int first2);
};

void MergeSortAlgorithm::MergeSort (int left, int right) {
  ops++;
  if (left < right) {
    MergeSort(left, (left+right)/2); ops+=2;
    MergeSort((left+right)/2 + 1, right); ops+=3;
    merge (left, (left+right)/2, (left+right)/2+1, right); ops+=5;
  }
}

void MergeSortAlgorithm::merge (int first1, int last1, int first2, int last2) {
  int *temp;
  int index, index1, index2;
  int num;

  temp=new int[n];

  index = 0;	ops++;
  index1 = first1;	ops++;
  index2 = first2;	ops++;

  num = last1 - first1 + last2 - first2 + 2; ops+=4;

  /*
   *  Merge the two lists back together until one list runs out of
   *  items...
   *
   */

  while ((index1 <= last1) && (index2 <= last2)) { ops+=3;
    ops++;
    if (T[index1] < T[index2]) {
    	temp[index++] = T[index1++]; ops+=3;
    }
    else {
    	temp[index++] = T[index2++]; ops+=3;
    }
  }

  /*
   *  At which point fill in the merged list with the "rest" of the
   *  non exhausted list.
   *
   */
  ops++;
  if (index1 > last1)
    move (T, index2, last2, temp, index);
  else
    move (T, index1, last1, temp, index);


  /* finally move our merged array in temp space to the real array */
  move(temp, 0, num-1, T, first1); ops++;
  delete[] temp;
}


void MergeSortAlgorithm::move (int *list1, int first1, int last1, int *list2,\
		 int first2) {
  while (first1 <= last1){ ops++;
    list2[first2++] = list1[first1++]; ops+=3;
  }
}

// El método Run del thread MergeSortAlgorithm es quien ejecuta el algoritmo

int MergeSortAlgorithm::Run(){
int delay;
char buf[256];
clock_t s,e;

	ops=0;
   dad->StatusMessage("Pensando...");
   s=clock();
	MergeSort(0,n-1);
   e=clock();
   delay=(e-s)/CLK_TCK*1000;
   sprintf(buf,"Hecho!. Tiempo transcurrido: %6d ms. Operaciones básicas: %d",\
   		delay,ops);

   dad->StatusMessage(buf);
   return 0;
}

// BucketSortAlgorithm es el thread que implementa el algoritmo "Seleccionar"

class BucketSortAlgorithm:public SortThread{
public:
	BucketSortAlgorithm(AlgorithmWindow *c):SortThread(c){};
private:
	int Run();
};

// El método Run del thread BucketSortAlgorithm es quien ejecuta el algoritmo

int BucketSortAlgorithm::Run(){
int i,k,delay,ops=0,U[MAX_VALUE];
char buf[256];
clock_t s,e;

   dad->StatusMessage("Pensando...");
   s=clock();

   for(k=0;kStatusMessage(buf);
   return 0;
}

// Constructor de AlgorithmWindow. Dibuja la ventana, el titulo, y le pone la
// caja de status.

AlgorithmWindow::AlgorithmWindow(TWindow *parent,char *title,int x,int y)
	: TWindow(parent){
	Attr.W=500;
	Attr.H=55;
   Attr.X=x;
   Attr.Y=y;
	Attr.Style|=WS_VISIBLE;
	SetBkgndColor(TColor::Sys3dFace);
   TStatic *f=new TStatic(this,0,"frame",0,0,500,55);
   f->Attr.Style|=SS_ETCHEDFRAME;
	new TStatic(this,0,title,5,5,120,15);
   Status=new TEdit(this,0,"Inactivo",10,25,480,20);
	Status->Attr.Style=Status->Attr.Style&~WS_HSCROLL&~WS_VSCROLL;
}

void AlgorithmWindow::StatusMessage(char *m){
Status->Clear();
Status->Insert(m);
}

// La ventana BubbleSortWindow es una AlgorithmWindow más el objeto particular
// BubbleSortAlgorithm, o sea más el thread con el algoritmo respectivo.

class BubbleSortWindow : public AlgorithmWindow{
public:
	BubbleSortWindow(TWindow *parent,char *title,int x,int y);
	BubbleSortAlgorithm *alg;
};

BubbleSortWindow::BubbleSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class InsertSortWindow : public AlgorithmWindow{
public:
	InsertSortWindow(TWindow *parent,char *title,int x,int y);
	InsertSortAlgorithm *alg;
};

InsertSortWindow::InsertSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class SelectSortWindow : public AlgorithmWindow{
public:
	SelectSortWindow(TWindow *parent,char *title,int x,int y);
	SelectSortAlgorithm *alg;
};

SelectSortWindow::SelectSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class QuickSortWindow : public AlgorithmWindow{
public:
	QuickSortWindow(TWindow *parent,char *title,int x,int y);
	QuickSortAlgorithm *alg;
};

QuickSortWindow::QuickSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class HeapSortWindow : public AlgorithmWindow{
public:
	HeapSortWindow(TWindow *parent,char *title,int x,int y);
	HeapSortAlgorithm *alg;
};

HeapSortWindow::HeapSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class MergeSortWindow : public AlgorithmWindow{
public:
	MergeSortWindow(TWindow *parent,char *title,int x,int y);
	MergeSortAlgorithm *alg;
};

MergeSortWindow::MergeSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}

class BucketSortWindow : public AlgorithmWindow{
public:
	BucketSortWindow(TWindow *parent,char *title,int x,int y);
	BucketSortAlgorithm *alg;
};

BucketSortWindow::BucketSortWindow(TWindow *parent,char *title,int x,int y)
	: AlgorithmWindow(parent,title,x,y){

   alg=NULL;
}
//SortWindow es la ventana principal que contiene a todas las ventanas de
//algoritmos.

class SortWindow : public TWindow{
public:
	SortWindow(TWindow *parent);
   void cmGo();
   void cmSetN();
	BubbleSortWindow *Bubbles;
   InsertSortWindow *Inserts;
   SelectSortWindow *Selections;
   QuickSortWindow *Quickies;
   HeapSortWindow *Heaps;
   MergeSortWindow *Merges;
   BucketSortWindow *Buckets;
   int *T;
   void Paint(TDC& dc,bool erase,TRect& rect);
private:
	TBitmap *b;
   TMemoryDC *memDC;
   TClientDC *mainWinDC;

DECLARE_RESPONSE_TABLE(SortWindow);
};
DEFINE_RESPONSE_TABLE1(SortWindow,TWindow)
	EV_COMMAND(CM_GO,cmGo),
   EV_COMMAND(CM_SETN,cmSetN),
END_RESPONSE_TABLE;

SortWindow::SortWindow(TWindow *parent=0)
	: TWindow(parent){

	T=NULL;
 	SetBkgndColor(TColor::Sys3dFace);
   Attr.W=640;
   Attr.H=480;
   Bubbles=new BubbleSortWindow(this,"Burbujas",5,5);
   Inserts=new InsertSortWindow(this,"Insertar",5,70);
   Selections=new SelectSortWindow(this,"Seleccionar",5,135);
   Quickies=new QuickSortWindow(this,"El Rápido",5,200);
   Heaps=new HeapSortWindow(this,"Montículo",5,265);
   Merges=new MergeSortWindow(this,"Mezclar",5,330);
   Buckets=new BucketSortWindow(this,"Casillas",5,395);
   b=new TBitmap(*GetModule(),IDB_BITMAP);
}

#pragma argsused
void SortWindow::Paint(TDC &dc,bool erase,TRect &rect){
TMemoryDC memDC;

	memDC.SelectObject(*b);
	dc.BitBlt(505, 5, b->Width(),b->He ight(), memDC, 0, 0, SRCCOPY);
}

//cmSetN en respuesta a una selección de menu CM_SETN saca el diálogo para
// introducir N.

void SortWindow::cmSetN() {
char buf[32];
	spri ntf(buf,"%d",n);
	if(TInputDialog(this,"Tamaño de la matriz","Especifique el valor para n:",\
   		buf,sizeof(buf)).Execute()==IDOK)
   	n=atoi(buf);
}

//cmGo en respuesta a la opción de menu Ejecutar (CM_GO) dispara la carrera.

void SortWindow::cmGo(){

	if(Bubbles->alg)
   	delete Bubbles->alg;
	Bubbles->alg=new BubbleSortAlgorithm(Bubbles);
   if(Inserts->alg)
   	delete Inserts->alg;
 	Inserts->alg=new InsertSortAlgorithm(Inserts);
   if(Selections->alg)
   	delete Selections->alg;
   Selections->alg=new SelectSortAlgorithm(Selections);
   if(Quickies->alg)
   	delete Quickies->alg;
   Quickies->alg=new QuickSortAlgorithm(Quickies);
	if(Heaps->alg)
   	delete Heaps->alg;
   Heaps->alg=new HeapSortAlgorithm(Heaps);
	if(Merges->alg)
   	delete Merges->alg;
   Merges->alg=new MergeSortAlgorithm(Merges);
	if(Buckets->alg)
   	delete Buckets->alg;
   Buckets->alg=new BucketSortAlgorithm(Buckets);
	if(T)
   	delete[] T;
	T=new int[n];
	::Scramble(T);
	Bubbles->alg->SetT(T);
   Inserts->alg->SetT(T);
   Selections->alg->SetT(T);
   Quickies->alg->SetT(T);
   Heaps->alg->SetT(T);
   Merges->alg->SetT(T);
   Buckets->alg->SetT(T);
  	Bubbles->alg->Start();
   Inserts->alg->Start();
   Selections->alg->Start();
   Quickies->alg->Start();
   Heaps->alg->Start();
   Merges->alg->Start();
   Buckets->alg->Start();
}

//El objeto de aplicación SortApp representa a la aplicación en si.

class SortApp : public TApplication {
public:
	SortApp():TApplication() {}
void InitMainWindow();
};

void SortApp::InitMainWindow(){

	TFrameWindow *frame=new TFrameWindow(0,"Sort Algorithms",new SortWindow);
   frame->AssignMenu(SORT_MENU);
   SetMainWindow(frame);
   EnableMultiThreading(true);
}



//.. OwlMain es el punto de entrada de la aplicación ObjectWindows.

int OwlMain(int , char* []){
	return SortApp().Run();
}