Newsgroup: it.comp.programmare
Titolo: Bubble sort più veloce del Quick sort?

Salve ragazzi, stavo facendo delle prove su quanta differenza in termini di
tempo, ci sia tra un ordinamento di bubble sort e quello del quick sort, ho
provato a ordinare un array di centomila elementi e stranamente
l'ordinamento di bubble sort è  più veloce di 24 secondi, del quick sort, è
possibile questo, oppure ho sbagliato io nell'implementazione degli
algoritmi?
-- 
ICQ # 84624356
MSN 
lello...@katamail.com
Yahoo ilpuntatore

 nell'implementazione degli algoritmi?
É difficile dirlo se non fornisci altri dati.
Ad esempio quicksort va in difficoltà quando
i dati sono quasi ordinati; in tal caso
quicksort è O(n^2) come bubblesort, anzi
lievemente peggiore perché è più complesso,
mentre altri agoritmi (come insertion sort)
sono O(n), quindi molto più veloci.
Ma senza sapere come realmente hai condotto
i test (forse un solo test?), non si può dire
molto. In particolare, come hai generato l'array?
-- 
Sabatino
*** Sequenza di reboot:
        Carol - Alt - Del

 molto. In particolare, come hai generato l'array?
L'array viene generato con dei numeri casuali, utilizzando la funzione rand,
comunque ho rivisto il codice e tutto sembra normalizzarsi. Infatti il
bubble sort ordina in 72 secondi, eseguendo 
2502710921
 scambi, ho provato
anche una forma ottimizzata del bubble sort, ma stranamente risulta più
lenta, infatti ordina in 79 secondi ed esegue 
2504224726
 scambi, invece il
quick sort, ordina in 0 secondi ed esegue 387811 scambi. Come si può vedere
la differenza tra il bubble sort ed il quick sort è tantissima :-O
Comunque posto anche il codice, che sicuramente sarà ancora possibile
ottimizzare
#include <iostream>
#include <time.h>
using namespace std;
void qsort(int vect[],int ,int);
void bubblesort();
void quickbubble();
int v[100000];
unsigned int scambi=0;
int main()
{
        int i;
        time_t a,b,ris;
        srand(time(0));
        for ( i=0; i<=99999; i++)
        {
                v[i]=rand();
        }
        a = time(NULL);
 
        qsort(v,0,99999);
        bubblesort();
        quickbubble();
        b = time(NULL);
        ris = b - a;
        /* Visualizzazione array ordinato
        for(int i=0; i<=99999; i++)
                cout<< v[i] <<endl;*/
        cout<< "Tempo: " << ris << " Scambi: " << scambi <<endl;
return 0;
}
void qsort(int v[], int inf, int sup)
{
        int i,j,pivot,temp;
        i=inf;
        j=sup;
        pivot=v[(inf+sup)/2];
        do
        {
                while (v[i]<pivot) i++;
                while (v[j]>pivot) j--;
                if (i<j)
                {
                        scambi++;
                        temp=v[i];
                        v[i]=v[j];
                        v[j]=temp;
                }
                if (i<=j)
                {
                        i++;
                        j--;
                }
        } while (i<=j);
        if (inf<j)
                qsort(v,inf,j);
        if (i<sup)
                qsort(v,i,sup);
}
void bubblesort()
{
        int x,y,temp;
        for (x=0; x<=99998; x++)
                for (y=x+1; y<=99999; y++)
                {
                        if (v[x] > v[y])
                        {
                                scambi++;
                                temp = v[x];
                                v[x] = v[y];
                                v[y] = temp;
                        }
                }
}
void quickbubble()
{
        int i,p=0,sorted=0,temp;
        while(!sorted)
        {
                sorted=1;
                ++p;
                for(i=0; i<=99999-p; ++i)
                {
                        if(v[i]>v[i+1])
                        {
                                scambi++;
                                temp=v[i];
                                v[i]=v[i+1];
                                v[i+1]=temp;
                                sorted=0;
