Bubblsort in einer Schleife

Der code ist ursprünglich javascript.Damit kann man nicht die Zahl der Vergleiche reduzieren aber es funktioniert trotzdem.
Man braucht ein feld mit 15 Elementen und eine Funktion fill_random() die dieses Array mit zufallszahlen füllt.

function bubblesort()
{
var i,j,umtausch;
fill_random();
for(i=0;i<15;++i)
document.write("<br>"+feld[i])

for(i=0;i<225;++i)
    {
    j=(i%14);

    if(feld[j]>feld[j+1])
        {
        umtausch=feld[j+1];
        feld[j+1]=feld[j];
        feld[j]=umtausch;
        }
    }

was haltet ihr davon??

WebFritzi

Nichts!

Wenn schon denn schon.Jetzt musst dus auch begründen.

WebFritzi

Das Ding funzt nich!

Schneller wird Bubblesort dadurch bestimmt nicht.
Für gewöhnlich hat man zwei Schleifen:

for( int i=0; i<size-1; ++i)
for( int j=size-1; j>=i+1; --j)
code();

code() wird damit (size-1)*(size)/2 = (size²-size)/2 mal aufgerufen, bei dir aber size² mal.

WebFritzi

Außerdem hat er nur eine Schleife, und j ist immer <14. Das ist kein BubbleSort!

japro

Original erstellt von WebFritzi:
Außerdem hat er nur eine Schleife, und j ist immer <14. Das ist kein BubbleSort!

dann überlag nochmal ganz genau

for(i=0;i<225;++i)
    {
    j=(i%14);
    ...

ist genau das selbe wie:

for(i=0;i<15;++i)
   for(j=0;j<14;++j)
   {
   ...

also jedenfalls fast das selbe... es sollte da nicht 225 sondern 210 heissen...
aber imho is das schwachsinnig... zwei ineinander verschachtelte schleifen sind ziemlich sicher effizienter als das weil dann nur einmal inkrementiert wird und das überflüssige modulo wegfällt(und natürichl noch viel mehr aus dem grund den space genannt hat)

was ist daran auszusetzen das j immer kleiner als 14 ist... das muss so sein!

[ Dieser Beitrag wurde am 05.03.2003 um 16:08 Uhr von japro editiert. ]

[ Dieser Beitrag wurde am 05.03.2003 um 16:14 Uhr von japro editiert. ]

es ist richtig das das nicht schneller wird dadurch,hab ich aaber auch geschrieben

Damit kann man nicht die Zahl der Vergleiche reduzieren...

und es kann gut sein das ich mich da leicht verzählt habe wie oft die schleife aufgerufen wird.Aber um all das alles ging es ganricht.Es ging darum das mein Informatik Lehrer mir gesagt hat man bräuchte immer 2 Schleifen für ein Bubblesort,mir gings darum das in eine schleife reinzubringen, auf alles andere hab ich nicht geachtet,es ging eigentlich nur um den Workaround.

code() wird damit (size-1)*(size)/2 = (size²-size)/2 mal aufgerufen, bei dir aber size² mal.

richtig aber das läßt sich auch bei meinem workaround einbauen,muss man nur :

function bubblesort()
{
var i,j,umtausch,c_;
fill_random();
c_=14
for(i=0;i<15;++i)
document.write("<br>"+feld[i])
for(i=0;i<105;++i)
    {
    j=(i % c_--);
    if(feld[j]>feld[j+1])
        {
        umtausch=feld[j+1];
        feld[j+1]=feld[j];
        feld[j]=umtausch;
        }
    }

105 weil es das 14. glied der reihe der folge a_n+1= a_n +1(ich hoffe ihr könnt das so lesen) ist.
aber wie gesagt der fokus lag nich beim speed.

Gerard

du kannst bubble sort auch rekursiv lösen dann brauchs du nicht mal eine schleife

gut dann spare ich mir die schleife ,knalle dafür aber den speicher mit rücksprung addressen voll... auch nicht soviel besser.