/*
Copyright (C) 2008 Alessandro Bugatti (alessandro.bugatti@istruzione.it)
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/*! \file
* \brief Programma che visualizza il comportamento
* dinamico di vari algoritmi di ordinamento rispetto a diverse
* composizioni dei file di input. Gli algoritmi di ordinamento presi in esame
* sono il BubbleSort, il SelectionSort, l'InsertionSort, l'InsertionSort
* adattativo, lo ShellSort e il QuickSort.
* \author Alessandro Bugatti
*
* \version 0.2
* \date Creazione 16/09/06
* \date Ultima modifica 9/10/08
* \attention Per essere ricompilato richiede la libreria SDL
* \attention Per essere eseguito richiede che la libreria dinamica
* SDL sia presente nel sistema
* \attention Per come è costruito il programma i tempi di esecuzione
* dei vari algoritmi non riflettono in alcun modo l'andamento reale, in quanto
* lo scopo è quello di visualizzarne il comportamento e non misurarne
* le prestazioni
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include "quickcg.h"
#define N 6400
#define X 640
#define Y 480
#define MAX 64000
using namespace std;
using namespace QuickCG;
//Vettore da ordinare
int vet[N];
int separatore = 0; //Non serve a niente, mi separa dalle invasioni del vettore, bisogna metterla a posto
int i=0;
int passo=0;
#define STACK 100
//Funzioni di supporto per il Quick sort non ricorsivo
int *s;
int NUM;
void stackinit(int MaxN)
{
if (s)
delete[] s;
s=new int(MaxN);
NUM=0;
}
int stackempty()
{
return NUM==0;
}
void push(int a)
{
s[NUM++]=a;
}
void push2(int a, int b)
{
push(b);
push(a);
}
int pop()
{
return s[--NUM];
}
//Funzione di partizionamento del Quick sort
int partition(int a[], int l, int r)
{
int i=l-1, j=r, t;
int v=a[r];
for (;;)
{
while (a[++i]<v)
;
while (v<a[--j])
if (j==l)
break;
if (i>=j)
break;
t=a[i];
a[i]=a[j];
a[j]=t;
}
t=a[i];
a[i]=a[r];
a[r]=t;
return i;
}
//Menu iniziale
void drawMenu()
{
print("Menu",X/2 - 4/2*8,Y/10);
print("1 - Bubblesort",X/8,2*(Y/10));
print("2 - SelectionSort",X/8,3*(Y/10));
print("3 - InsertionSort non adattativo",X/8,4*(Y/10));
print("4 - InsertionSort adattativo",X/8,5*(Y/10));
print("5 - ShellSort",X/8,6*(Y/10));
print("6 - QuickSort",X/8,7*(Y/10));
print("Esc - Per terminare",X/8,8*(Y/10));
print("a - Input casuale",X*3/5,2*(Y/10));
print("b - Input ordinato al contrario",X*3/5,3*(Y/10));
print("c - Input gaussiano",X*3/5,4*(Y/10));
print("d - Input quasi ordinato",X*3/5,5*(Y/10));
print("e - Input con 10 valori distinti",X*3/5,6*(Y/10));
print("Realizzato da Alessandro Bugatti - 16/09/2006",
X/2 - 45/2*8,9*(Y/10));
redraw();
}
//Bubblesort
void drawBubbleSort()
{
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
for (int j=N-1;j>i;j--)
if (vet[j-1]>vet[j])
{
int t=vet[j];
vet[j]=vet[j-1];
vet[j-1]=t;
}
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
i++;
}
//Insertionsort non adattativo
void drawInsertionSortNA()
{
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
if (i<N)
for (int j=i; j>0; j--)
if (vet[j]<vet[j-1])
{
int t = vet[j];
vet[j] = vet [j-1];
vet[j-1]=t;
}
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
i++;
}
//Insertion sort adattativo
void drawInsertionSortA()
{
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
if (i==0)
for (int i=N; i>0; i--)
if (vet[i-1]>vet[i])
{
int t=vet[i];
vet[i]=vet[i-1];
vet[i-1]=t;
}
int j=i;
int v=vet[i];
if (j<N)
while (v<vet[j-1])
{
vet[j]=vet[j-1];
j--;
}
vet[j]=v;
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
i++;
}
//SelectionSort
void drawSelectionSort()
{
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
int min=i;
if (i<N)
{
for (int j=i+1; j<=N; j++)
if (vet[j]<vet[min])
min=j;
int t=vet[i];
vet[i]=vet[min];
vet[min]=t;
}
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
i++;
}
//ShellSort
void drawShellSort()
{
int j;
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
if (passo==0)
{
for (int i=1;passo<=(N-1)/9;passo=3*passo+1)
;
i=passo;
}
if (passo>0)
{
j=i;
int v=vet[i];
while (j>=passo && v<vet[j-passo])
{
vet[j]=vet[j-passo];
j-=passo;
}
vet[j]=v;
}
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
if (passo>0)
if (i>=N)
{
passo/=3;
i=passo;
}
else
i++;
}
//Quick sort non ricorsivo
void drawQuickSortNR()
{
int i,l,r;
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Black);
if (!stackempty())
{
l=pop();
r=pop();
if (r<=l)
;
else
{
i = partition (vet,l,r);
if (i-l > r-i)
{
push2(l,i-1);
push2(i+1,r);
}
else
{
push2(i+1,r);
push2(l,i-1);
}
}
}
for (int i=0;i < N ; i++)
pset(i/(N/X),(Y-1)-vet[i]/((MAX/Y)+1),RGB_Yellow);
redraw();
}
//Funzione per produrre interi fino a oltre 4 miliardi
inline int rand2()
{
return rand()*0xFFFF+rand();
}
//Funzione per inizializzare il vettore in diversi modi
void inizializeVector(int mode)
{
i=0;
passo=0;
switch (mode)
{
case 0:
//Riempio il vettore di valori casuali
for (int i=0;i < N ; i++)
vet[i]=rand2()%MAX;
break;
case 1:
//Riempio il vettore ordinato al contrario
for (int i=0;i < N ; i++)
vet[i]=(N-i)*MAX/N;
break;
case 2:
//Riempio il vettore con valori che seguono una distribuzione gaussiana
for (int i=0;i < N ; i++)
vet[i]=rand2()%MAX/2 + rand2()%MAX/2;
break;
case 3:
//Riempio il vettore con valori quasi ordinati
for (int i=0;i < N ; i++)
if (rand()%2)
{
int temp=i*(MAX/N)+rand()%1000;
vet[i] = temp>MAX?temp-1000:temp;
}
else
{
int temp=i*(MAX/N)-rand()%1000;
vet[i] = temp>0?temp:temp+1000;
}
break;
case 4:
//Riempio il vettore con solo 10 valori diversi
for (int i=0;i < N ; i++)
vet[i] = rand()%10*(MAX/10);
break;
}
}
int main(int argc, char** argv)
{
int mode=0; //Tipologia dei diati di input
bool running=false;
bool pause = false;
srand(time(NULL));
inizializeVector(mode);
//Crea uno schermo DIM_X x DIM_Y
screen(X, Y,0, "Confronto di ordinamenti grafico");
/* Main loop */
int choice=0;
while (!done())
{
readKeys();
if (keyPressed(SDLK_ESCAPE))
break;
if (keyPressed(SDLK_0)) //mostra il menu
{
choice=0;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_1)) //BubbleSort
{
choice=1;
pause = false;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_2)) //SelectionSort
{
choice=2;
pause = false;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_3)) //InsertionSortNA
{
choice=3;
pause = false;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_4)) //InsertionSortA
{
choice=4;
pause = false;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_5)) //InsertionSortA
{
choice=5;
pause = false;
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_6)) //QuickSort
{
choice=6;
pause = false;
stackinit(STACK);
push2(0,N-1);
inizializeVector(mode);
cls();
}
if (keyPressed(SDLK_a)) //Input casuale
{
if (!running)
mode = 0;
}
if (keyPressed(SDLK_b)) //Input ordinato al contrario
{
if (!running)
mode = 1;
}
if (keyPressed(SDLK_c)) //Input ordinato al contrario
{
if (!running)
mode = 2;
}
if (keyPressed(SDLK_d)) //Input quasi ordinato
{
if (!running)
mode = 3;
}
if (keyPressed(SDLK_e)) //Input 10 valori diversi
{
if (!running)
mode = 4;
}
if (keyPressed(SDLK_p)) //Mette o toglie dalla pausa
{
if (running)
pause=!pause;
}
switch (choice)
{
case 0:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Menu", "basics");
running = false;
pause = false;
drawMenu();
break;
case 1:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Bubble sort", "basics");
running = true;
if (!pause)
drawBubbleSort();
break;
case 2:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Selection sort", "basics");
running = true;
if (!pause)
drawSelectionSort();
break;
case 3:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Insertion sort non adattativo", "basics");
running = true;
if (!pause)
drawInsertionSortNA();
break;
case 4:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Insertion sort adattativo", "basics");
running = true;
if (!pause)
drawInsertionSortA();
break;
case 5:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Shell sort", "basics");
running = true;
if (!pause)
drawShellSort();
break;
case 6:
SDL_WM_SetCaption("Confronto di ordinamenti grafico - Quick sort", "basics");
running = true;
if (!pause)
drawQuickSortNR();
break;
}
SDL_Delay(0);
};
return 0;
}