[Java] Sorteren

[Verwijderd]

He, voor school hebben wij een opdracht gekregen om 2 arrays te sorteren die bij elkaar horen. Je hebt 2 kolommen, artiest en titel (een CD-lijst) en nu staat er het volgende in het boek:

Gebruik hiervoor de bubble sort methode zoals die in deel 1 is behandeld

Nu is de pech, ik heb deel 2 en vorig jaar hebben we er niks over gehad

Op google vond ik wel bij Sun zelf de bubble sort class, maar die is maar voor 1 rij en die hele code daarvan vat ik absoluut niet.

Hier nog het adres van de code:
http://java.sun.com/apple...mo/SortDemo/example1.html

en hier de code:

code:

class BubbleSortAlgorithm extends SortAlgorithm {
    void sort(int a[]) throws Exception {
    for (int i = a.length; --i>=0; )
        for (int j = 0; j<i; j++) {
        if (stopRequested) {
            return;
        }
        if (a[j] > a[j+1]) {
            int T = a[j];
            a[j] = a[j+1];
            a[j+1] = T;
        }
        pause(i,j);
        }
    
    }
}

Ik weet echt niet wat ze hier bedoelen. Wij krijgen echt n00b-Java op school.

Weet iemand misschien een goeie site waar zoiets op staat of ooit zelf een applet gebouwd met een vergelijkend script?

[Soultaker]

Bubble-sort werkt als volgt:
Je doorloopt je hele reeks door en vergelijkt elke keer je huidige element met het volgende element. Als het volgende element kleiner is dan het huidige element, wissel je de twee om (ze stonden immers verkeerd om; nu staan ze goed). Dit herhaal je net zo vaak als je lijst lang is en dan heb je gegarandeerd een gesorteerde lijst.

Dat wordt ook in die code uitgedrukt. De binnenste lus doorloopt de array en wisselt elementen om als dat zo uitkomt. De buitenste lus herhaalt die operatie net zo vaak als de lijst lang is.

Een eigenschap van dit algoritme is dat het grootste element de eerste keer al gegarandeerd onderaan komt, het op een na grootste element de tweede keer al, etcetera. Vandaar dat ze hier een optimalisatie hebben toegepast, door middel van de conditie "j<i" in de definitie van de for-lus. Dit zou (volgens mijn uitleg daarnet) "j < a.length" moeten zijn, maar "j < i" scheelt de helft van het aantal iteraties en heeft hetzelfde resultaat tot gevolg.

Om dit algoritme toe te passen op je eigen lijst, moet je een vergelijking definiëren op de elementen van je array; simpelweg ">" werkt dus niet. Denk daarbij aan een functie waar je twee objecten (elk object bevat de artiest en de titel) in stopt, en die een boolean retourneert die aangeeft of het eerste element groter is dan het tweede. Verder kun je de gegeven implementatie klakkeloos overnomen.

De mogelijkheid tot pauseren of afbreken heb je waarschijnlijk niet nodig, dus die kun je er veilig uitslopen.

[zeroxcool]

Lolz, je zal wel de Turing methode hebben . Wij hebben dat hoofdstuk als test gehad voor de volgende HAVO4 klassen, heb het boekje helaas alweer in moeten leveren.

En bubble-sort vind ik persoonlijk een geheugenvretend algoritme, er stonden in dat boekje nog meer sorteer algoritmes, één daarvan is snel en goed .

Je woont btw in Grave, is hier een kilometertje of 12 vanaf .

[ Voor 42% gewijzigd door zeroxcool op 24-11-2002 17:29 ]

[Verwijderd]

Soultaker schreef op 24 november 2002 @ 17:24:
Denk daarbij aan een functie waar je twee objecten (elk object bevat de artiest en de titel) in stopt.

IDD, ik was zelf ook al bezig met zelf eentje maken, maar hoe maak je dan zo'n voorwaarde?

[Soultaker]

Trouwens, als je het gevisualiseerd wil hebben, moet je even dat voorbeeld van Sun hacken zodat er een VEEL grotere vertraging in zit (zal wel een getalletje in de functie pause() zijn). De rode lijn geeft de waarde van 'i' aan, de blauwe lijn de waarde van 'j', maar die beweegt zo snel dat je niet ziet hoe de waarden worden omgewisseld (er worden, zoals je nu dus niet kan zien, uitsluitend naast elkaar gelegen lijnen omgewisseld).

[Soultaker]

Verwijderd schreef op 24 November 2002 @ 17:27:
IDD, ik was zelf ook al bezig met zelf eentje maken, maar hoe maak je dan zo'n voorwaarde?

Tja, hoe wil jij die dingen ordenen? Functies om twee strings te vergelijken zijn al standaard beschikbaar, dus die kun je gebruiken. Dan moet je zelf nog wel definiëren hoe je je object met twee strings met een ander object met twee strings wilt vergelijken.

Je mag natuurlijk wel een beetje zelf nadenken.

[Soultaker]

ZeRoXcOoL schreef op 24 November 2002 @ 17:26:
En bubble-sort vind ik persoonlijk een geheugenvretend algoritme, er stonden in dat boekje nog meer sorteer algoritmes, één daarvan is snel en goed .

Bubble-sort kost constant geheugen hoor. Uitsluitend de twee indices worden gealloceerd. Er zijn nauwelijks algoritmes denkbaar die dat beter doen.

offtopic:
Woei! Drie posts van mij achter elkaar.

[ Voor 9% gewijzigd door Soultaker op 24-11-2002 17:34 ]

[Verwijderd]

offtopic:
Gebruik de edit

Ik kan dan het beste getBytes gebruiken of niet?

[ Voor 8% gewijzigd door Verwijderd op 24-11-2002 17:36 ]

[Soultaker]

Wat wil je met getBytes() doen dan?

Als je nu begint met vastleggen wat je wil, kun je daarna op een zinnige wijze een vergelijking definiëren.

[wacco]

waarom echt bubblesort? quicksort is zooow ontzettend veel sneller:

code:

void quicksort (int[] a, int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    //  partition
    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
}

(ergens vandaan gehaald... don't ask me where, hij stond nog steeds in m'n temp tekstbestand en het is c code, misschien moet je het ff aanpassen)

Soultaker schreef op 24 November 2002 @ 17:33:
Bubble-sort kost constant geheugen hoor. Uitsluitend de twee indices worden gealloceerd. Er zijn nauwelijks algoritmes denkbaar die dat beter doen.

Zie de quicksort hierboven, maar bedenk dan de functie met pointers ipv vars. Kost je misschien een klein beetje extra cache, maar je bent van het hele gesorteerd 1000x sneller af.

[wasigh]

Als je de Comparable interface gebruikt kun je Arrays.sort() gebruiken dat is een aangepaste bubblesort

[PhoneTech]

<offtopic>
Nog een devver uit ons zeer geliefde Grave? mis ik iets? Waar zit je dan op het HBO
</offtopic>

[Soultaker]

wacco schreef op 24 november 2002 @ 20:28:
Zie de quicksort hierboven, maar bedenk dan de functie met pointers ipv vars. Kost je misschien een klein beetje extra cache, maar je bent van het hele gesorteerd 1000x sneller af.

Jouw implementatie kost zelfs O(log(N)) geheugen! Dan is die bubble-sort een stuk beter, hoor.

wasigh schreef op 24 November 2002 @ 20:58:
Als je de Comparable interface gebruikt kun je Arrays.sort() gebruiken dat is een aangepaste bubblesort

Je hoeft de Comparable interface niet te ondersteunen om van Arrays.sort() gebruik te maken. Dat kan immers ook met een Comparator.

Daarbij gebruiken de meeste variaties van Arrays.sort() een soort mergesort (anderen een soort quicksort); in ieder geval geen bubblesort, wat wel z'n beetje het slechtse algoritme is dat je kunt bedenken.

Ik neem trouwens aan dat het om huiswerk gaat en dan is het ten eerste logisch dat de TS een inferieur algoritme moet implementeren (het gaat om het implementeren van het algoritme; niet om het bedenken van een nieuw goed algoritme) en ten tweede dat de TS geen standaardfunctie mag gebruiken (ook al is dat in de praktijk een slimme keuze); daar leer je het programmeren van een algoritme niet van.

[ Voor 62% gewijzigd door Soultaker op 24-11-2002 22:48 ]

[Verwijderd]

PhoneTech schreef op 24 November 2002 @ 22:35:
<offtopic>
Nog een devver uit ons zeer geliefde Grave? mis ik iets? Waar zit je dan op het HBO
</offtopic>

Ik zit nu op 5 HAVO, maar volgend jaar ga ik naat Fontys Eindhoven proberen mijn propadeuse te halen en dan de TU/e...

Ik heb dus ook een soort van bubblemethode uitged8, want ik ga niet een of andere voorgebakken rotzooi gebruiken Mijn leraar houdt van buitenbeentjes

Nu is mijn vraag hoe je nou met 2 woorden voorwaarden kan stellen.
Dus zoiets als
Woordje A > Woordje B

[ Voor 9% gewijzigd door Verwijderd op 24-11-2002 23:45 ]

[Soultaker]

Zoals ik al min of meer letterlijk had voorgekauwd: "woordje A" > "woordje B" en als je zulke berichten blijf posten reageer ik verder wel in SeM.

Of houdt jouw docent wel van leerlingen die anderen hun huiswerk laten maken?

[ Voor 29% gewijzigd door Soultaker op 24-11-2002 23:52 ]

[Verwijderd]

Soultaker schreef op 24 november 2002 @ 22:42:
Daarbij gebruiken de meeste variaties van Arrays.sort() een soort mergesort (anderen een soort quicksort); in ieder geval geen bubblesort, wat wel z'n beetje het slechtse algoritme is dat je kunt bedenken.

Het kan altijd nog korter en slechter... hier mijn zigzagsort algoritme

code:

void sort(int[] a){
for (int i=0;i<a.Length;i++) 
  if (1<=i && a[i-1]<a[i])
  {int t=a[i];a[i]=a[--i];a[i--]=t;}
}

[Soultaker]

Weet je zeker dat het (veel) slechter is?

Hij lijkt iig wel te kloppen (of ik heb iets over het hoofd gezien).

[vinnux]

java.utils.Arrays.sort() ?

[Soultaker]

vgouw schreef op 25 november 2002 @ 01:52:
java.utils.Arrays.sort() ?

OMG -- LEES DE DRAAD!

[Rataplan]

Verwijderd schreef op 25 november 2002 @ 00:43:
Het kan altijd nog korter en slechter... hier mijn zigzagsort algoritme

Dat ik ogenblikkelijk sneller kan maken

code:

void sort(int[] a){
for (int i=1;i<a.Length;i++) 
  if (a[i-1]<a[i])
  {int t=a[i];a[i]=a[--i];a[i--]=t;}
}

Goedgoed, het scheelt maar een paar cycles, maar toch

[edit:]
Ik zit te kijken en te kijken, maar volgens mij is dit gewoon 1 pass uit een bubblesort. De reeks 5-2-4-3-1 levert (uit het hoofd) het array 2-4-3-1-5 op...

[ Voor 27% gewijzigd door Rataplan op 25-11-2002 02:07 ]

[Soultaker]

Rataplan schreef op 25 November 2002 @ 02:03:
Dat ik ogenblikkelijk sneller kan maken

Nee, nee, nee, nee! Nu klopt er niets meer van.

Denk eraan dat i verlaagd kan worden; zelfs als je op 1 begint kan het dus voorkomen dat i 0 wordt en dan kun je a[i-1] niet evalueren. Wanneer je het kleinste getal tegenkomt, is dit bijvoorbeeld het geval, omdat je dan elke keer wilt wisselen met het vorige getal.

Ik zit te kijken en te kijken, maar volgens mij is dit gewoon 1 pass uit een bubblesort. De reeks 5-2-4-3-1 levert (uit het hoofd) het array 2-4-3-1-5 op...

Nee hoor, het is eeen volledig sorteeralgoritme. Je begint vooraan; als je twee getallen tegenkomt die verkeerd om staan, wissel je ze om, en schuif je twee terug. Er komt een gesorteerde reeks uit (1-2-3-4-5 dus).

Het lijkt me trouwens een variatie op insertion sort, met het verschil dat je niet 'direct' naar het einde van je lijst springt als je een element op de juiste plaats hebt geezt, maar terugzigzagt (vandaar de naam, vermoed ik?).

Insertion sort (en deze variatie erop) is trouwens O(N^2) in tijd en O(1) in geheugen, net als bubblesort, dus wat dat betreft is 'ie even slecht. Ik kan me echter voorstellen dat bubblesort een constante factor sneller is.

[ Voor 10% gewijzigd door Soultaker op 25-11-2002 02:36 ]

[Rataplan]

Soultaker schreef op 25 november 2002 @ 02:34:
Nee, nee, nee, nee! Nu klopt er niets meer van.

En bedankt heh

Ik ben bang dat ik een of twee --'etjes gemist heb Elegant, wel, bij nader inzien! Overigens blijft de helft van mijn "optimalisatievoorstel" wel degelijk van kracht: eerste keer is i=0, if() evalueert false, ga verder met i=1. Begin dan ook meteen met 1! Volgens mij wordt het dan

code:

void sort(int[] a){
for (int i=1;i<a.Length;i++) 
  if (i>=1 && a[i-1]<a[i])
    {int t=a[i];a[i]=a[--i];a[i--]=t;}
}

[Verwijderd]

Ja, meteen bij 1 beginnen scheelt inderdaad 1 cycle Maar het ging me om de lengte van de sorteer code en dan maakt het niet uit. De naam zigzagsort hebben we trouwens zelf bedacht.

De korte kan handig zijn bij programmeerwedstrijden. De hele mergesort code uittypen kan even duren, maar met zigzagsort ben je zo klaar Enne, de zigzagsort code kan trouwens nog minstens 1 char korter.

[Verwijderd]

De naam voor alternerend naar boven en dan naar onder bubblesorten is niet "zigzagsort" maar shaker sort (omdat het lijkt op de beweging van een cocktail-shaker). Niets nieuws onder de zon dus.

[ Voor 4% gewijzigd door Verwijderd op 25-11-2002 15:49 ]

[Rataplan]

Verwijderd schreef op 25 november 2002 @ 15:48:
De naam voor alternerend naar boven en dan naar onder bubblesorten is niet "zigzagsort" maar shaker sort (omdat het lijkt op de beweging van een cocktail-shaker). Niets nieuws onder de zon dus.

Dit lijkt me toch een fundamenteel andere sort. Shaker sort doet passes van links naar rechts, dan van rechts naar links, terwijl zigzagsort (of hoe het ook zou mogen heten) na elke sorteeractie 1 stap naar links doet, en verder naar rechts probeert te werken. Als ik het goed samenvat.

edit:
links=boven, rechts=onder. Ach, what the hell

[ Voor 6% gewijzigd door Rataplan op 25-11-2002 16:03 ]

[Verwijderd]

Oeps, klopt. Te snel geantwoord.

[Verwijderd]

Dus ik heb een geheel nieuw sorteer algoritme uitgevonden? Ik ga meteen patent aanvragen!!!

[Verwijderd]

Lol, ik denk dat iemand anders er vast al een keer opgekomen is maar dat het gewoon niet bekend is geraakt.