Multidesk.be » Forums » Java » sorteren 2-D array (gesloten)

Helpinformatie
Dit onderwerp bevindt zich in het archief.
Het is bijgevolg niet mogelijk er nog op te reageren.
  • Pagina
  • 1 van 1
  • RSS
  • Eerste ongelezen reactie
  • Plaats een reactie
  • Abonneer mij
  • Onderwerp sluiten
0 gasten lezen dit onderwerp.
^ Onderwerp geschreven door een gast op vrijdag 27 april 2007 om 21:21:37.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
stel je hebt een 2D array rij[][]
en je wilt die sorteren op de 1e kolom (enkel de eerste kolom)

_____________________________________________________________________

verduidelijking:
elke rij stelt een object voor (maar wordt niet geimplementeerd als een object)
elke kolom bevat een waarde die hoort bij een object (dus bij een rij)
en als een cel uit de 1e kolom verplaatst wordt door de sortering
is het de bedoeling dat alle kolommen van die rij mee verplaatsen

voorbeeldje:

3 4 5 1 9 6
7 2 8 => 3 4 5
1 9 6 7 2 8

______________________________________________________________________


bestaat hiervoor een methode? (in de api)

ik weet wel dat er een methode is Arrays.sort()
maar die werkt alleen voor een 1D array

bedankt!
^ Reactie #1 geschreven door een gast op vrijdag 27 april 2007 om 21:23:09.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
de indentatie klopt niet niet meer :s

3 4 5
7 2 8
1 9 6

wordt:

1 9 6
3 4 5
7 2 8
^ Reactie #2 geschreven door Martijn op zaterdag 28 april 2007 om 09:43:21.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Probeer dit eens:
CODE
  1. import java.util.*;
  2.  
  3. public class Demo {
  4.     public static void main(String... args) {
  5.         new Demo().go();
  6.     }
  7.    
  8.     void go() {
  9.         List<Thing> list = Arrays.asList(new Thing[] {
  10.             new Thing("ann", 10),
  11.             new Thing("barry", 5),
  12.             new Thing("mark", 8),
  13.         });
  14.         Collections.sort(list, Thing.BY_VALUE);
  15.         for (Thing t : list) {
  16.             System.out.println(t);
  17.         }
  18.     }
  19. }
  20.  
  21. final class Thing {
  22.     public static Comparator<Thing> BY_VALUE = new ValueComparator();
  23.     private String name;
  24.     private int value;
  25.    
  26.     public Thing(String name, int value) {
  27.         this.name = name;
  28.         this.value = value;
  29.     }
  30.    
  31.     public String toString() {
  32.         return name + " " + value;
  33.     }
  34.    
  35.     private static final class ValueComparator
  36.             implements Comparator<Thing> {
  37.         public int compare(Thing t1, Thing t2) {
  38.             if (t1.value < t2.value) return -1;
  39.             else if (t1.value > t2.value) return 1;
  40.             else return 0;
  41.         }
  42.     }
  43. }


Sun Java forums

Werkt wel via namen en twee kolommen, maar dat is niet zo moeilijk aan te passen he :).
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #3 geschreven door een gast op zaterdag 28 april 2007 om 23:51:55.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
hm worden hier niet gewoon dingen vergeleken?
en het is niet echt wat ik nodig heb
en het moet ook gebeuren in 0(nlogn)

en het aantal kolommen kan heel groot zijn
en het aantal rijen ook....
^ Reactie #4 geschreven door Martijn op zondag 29 april 2007 om 09:54:46.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Wat bedoel je met in 0 (nlogn)?

Hier worden toch wel dingen vergeleken? De array wordt gesorteerd op de erste kolom. Het enige wat je nog moet doen, is een lus inbouwen om het aantal kolommen achter de eerste rij te bepalen om die mee te verplaatsen. Het vergelijken gebeurt door de Comparator.
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #5 geschreven door een gast op zondag 29 april 2007 om 15:52:39.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
de complexiteit is O(n log n)
met n de grootte van de te sorteren rij
een oplossing zou zijn mergesort, maar deze is nogal omslachtig om zelf te implementeren
vandaar dat ik op zoek ben gegaan naar een voorgedefinieerde sorteermethode
en de enige die ik vond voor arrays was die van Arrays.sort()
maar deze wil niet werken met een 2D-array

jouw methode gaat elk element vergelijken en dan nog eens alle kolommen (op dezelfde rij) overlopen om die mee te verplaatsen als er een element uit de 1e kolom mee verplaatst

=> n keer om alle rijen te verlopen
(en stel dat het een nxn matrix is)
=> per verplaatsing nog eens (n-1) verplaatsingen

zo krijg je in worst case een algoritme van n x (n-1)
=> complexiteit O(n≤)

wat veel langer is dan een O(n log n)
^ Reactie #6 geschreven door Martijn op zondag 29 april 2007 om 16:24:44.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Als je het wil oplossen, quick and dirty, maak dan een tweede array aan en sorteer rij per rij. Performantie? Twee keer niets... Hiervoor zal je moeten beroep moeten doen op een quick sort of shear sort.

Wat is de oplossing die je momenteel hebt?

Interessant leesvoer ;).
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #7 geschreven door een gast op zondag 29 april 2007 om 23:13:52.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
hoe bedoel je een 2e array?

momenteel nog geen concrete oplossing
^ Reactie #8 geschreven door Martijn op maandag 30 april 2007 om 08:45:40.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Heel eenvoudig: alles kopiŽren en sorteren, zowat de slechtste techniek die je je kan inbeelden.

Als je verschillende algoritmes op performantie wil vergelijken, lees je best de link die ik gaf eens door. Zelf heb ik niet enorm veel ervaring met het sorteren via verschillende algoritmes, maar in dat document staat alles dat je zou moeten weten (inclusief source code) :).
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #9 geschreven door een gast op maandag 30 april 2007 om 09:09:48.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
maar ik snap niet goed waarom je een 2e array zou gebruiken?

de link heb ik doorgekeken maar ik ben op een IndexOutOfBoundsException gebotst bij merge sort

de laatste forlus van het algortime:

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}


volgens mij zit de fout bij right = right - 1
maar ik ben niet zeker, en ik weet niet waarom
^ Reactie #10 geschreven door een gast op maandag 30 april 2007 om 09:31:37.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
trouwens dit zijn sorteeralgoritmes voor 1D rijen
^ Reactie #11 geschreven door Martijn op maandag 30 april 2007 om 11:06:49.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Of dat nu is voor 1 D of voor 2 D, in principe moet je maar een 1D rij sorteren en gewoon hetgene wat er naast komt, mee kopieren hť.

Wat betreft die tweede array: temp is in het voorbeeld hierboven de tweede (tijdelijke) array.

Debug je code eens en kijk waar het probleem net zit; het is ebst mogelijk dat je array temp niet groot genoeg geÔnstantieerd is :).
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #12 geschreven door een gast op maandag 30 april 2007 om 14:26:17.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
ja maar als je alles wat erna komt mee gaat kopieren
dan stijgt je complexiteit toch enorm?

stel dat je elk element gaat moeten verplaatsten
dan moet je ook alle andere elementen gaan mee verplaatsen
en dan krijg je een O(n≤), of niet?

en nog een vraagje
stel je hebt een 2D Array array[][]
als je nu de 1e rij van array wilt hebben, dan doe je toch array[0]
niet?
maar wat als je de 1e KOLOM van array wilt hebben?
^ Reactie #13 geschreven door Martijn op maandag 30 april 2007 om 17:37:40.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
De complexiteit steigt ja, vanzelfsprekend. De eerste kolom van een array betekent dat je die array moet doorlopen, aangezien arrays werken per rij... Elke functie zal (al dan niet intern) de array doorlopen. Het is dan aan het zoekalgoritme om dat op een bepaalde, efficiŽnte, manier te doen.
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #14 geschreven door een gast op maandag 30 april 2007 om 19:15:00.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
dus je kan niet in 1x een hele kolom opvragen, enkel rijen?
^ Reactie #15 geschreven door Martijn op dinsdag 1 mei 2007 om 12:50:13.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Ik vermoed van wel ja, of ik moet iets over het hoofd zien... Misschien dat anderen (experts) hier een afdoend antwoord op kunnen geven? Weet het niet hoor :).
Met vriendelijke groeten,
Martijn Wouters
^ Reactie #16 geschreven door een gast op woensdag 2 mei 2007 om 19:10:55.
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
zucht...ik ben heel dom geweest
ik zat maar te denken aan elk element van een rij apart te verplaatsen
terwijl je de hele rij in 1 keer kan verplaatsen
dus dan moet ik helemaal niet werken met aparte kolommen

dom dom :p
toch bedankt!
^ Reactie #17 geschreven door Martijn op woensdag 2 mei 2007 om 22:40:18.
Martijn heeft nog geen avatar toegevoegd
Multiviteit: 13785
Beheerder
  • Bewerken
  • Citeren
  • Reageren
  • Verwijderen
  • Waarschuw een crewlid
Een rij in een array wordt sowieso verplaatst he :). Simpel gezegd: array[0] in een tweedimensionaal array is sowieso een array op zich; omgezet naar jouw termen: een rij :).

Soit, blij dat het opgelost is, uiteindelijk was het dus eerder een probleem in terminologie blijkbaar :).
Met vriendelijke groeten,
Martijn Wouters
  • Pagina
  • 1 van 1
  • RSS
  • Eerste ongelezen reactie
  • Plaats een reactie
  • Abonneer mij
  • Onderwerp sluiten