[java] zelf een sort bouwen

[Verwijderd]

ik ben een java newbie, maar ben een sort aan het schrijven; het idee is je voert een regel in en hij gaat de woorden vervolgens sorteren in de zin. Nu is het schrijven van een sorteer functie al gelukt, echter ik wil graag duplicaten in de zin voorkomen , dus wanneer 4x 'een' voorkomt moet dat maar 1x voorkomen in de gesorteerde lijst.

iemand een idee hoe ik dat moet aanpakken, heb zelf al veel gegoogled en kan iets relevants vinden, aangezien je normaal gewoon een functie uit de sort library voor arrays zou nemen, maar dat mag nu niet..

EDIT:
ik heb al de volgende code, echter ik houd duplicaten wie weet hoe ik dit kan verhelpen? iets met een break en continue misschien?

code:

import java.util.*;
import jpb.*;

public class InsertSort {

public static void main (String[] args) {
    
    //input opgeslagen in string inputLine 
    SimpleIO.prompt("Voer de woorden in: ");
    String inputLine = SimpleIO.readLine();
    StringTokenizer st = new StringTokenizer(inputLine);
    //als er geen woorden voorkomen exit programma
    if (st.countTokens()<1)
    { System.exit(0);
    }
    //tel het aantal tokens, deze staan gelijk aan het aantal elementen nodig in array words
    int max = st.countTokens(); 
    String [] words;
    words=new String[max];
    int a=0;
    
    //zet de losse woorden in de string array words
     while (st.hasMoreTokens()) {
         words[a] = st.nextToken();
         a++;
     }
    
    //voer soort uit
    words=sort(words);
    
    //print de array words
    for (int x=0;x<max;x++ )
    {
    
    System.out.println(words[x]);
    
    
}

} 

private static String[] sort(String[] s) {
  
 int i;
 String temp;
 int l = s.length;

 for (int u = 0; u <= l-1; u++){
      temp = s[u];
      i = u - 1;
      while ( i >= 0 && (s[i].compareTo(temp)>=0)){
            
            if (s[i].compareTo(temp)==0){
            System.out.println("een dubbele!" + s[i]);
            
            
            }
            
            
        s[i+1] = s[i];
        i--;
        }
      
  s[i+1] = temp;
      
  }



  //geef de waardes van de gesorteerde array
  return s;
}


}

[ Voor 23% gewijzigd door Verwijderd op 20-02-2005 16:14 ]

[silentsnow]

Het lijkt mij een stuk efficienter om de array te scannen elke keer als je een woord invoert. Hier kan je mooi een methode voor schrijven die het woord in de array zet als deze er nog niet in voorkomt, en anders niets doet. Bijvoorbeeld:

Java:

import java.util.*;

public class week1c
{
   static String[] words;
   int a=0;

   public static void main (String[] args)
   {
      SimpleIO.prompt("Voer de woorden in: ");
      String inputLine = SimpleIO.readLine();

      StringTokenizer st = new StringTokenizer(inputLine);
      int max = st.countTokens();
      words=new String[max];

      while (st.hasMoreTokens())
      {
         insert(st.nextToken());
      }

      for (int x=0;x<max;x++ )
      {
         System.out.println(words[x]);
      }
   }

   private static void insert(String s)
   {
      for ()
      {
            // scan de gehele array voor het woord "s". Indien deze niet in de array voorkomt, voer hem dan in.
      }
      a++;  // indien je het woord in de array zet.
   }
}

[NMe]

Ik denk dat het handiger is om een merge- of quicksort algoritme te implementeren. Niet alleen omdat het sneller is, maar ook omdat je, als ik het me goed herinner, sneller kan zien hoe vaak iets voorkomt.

[Verwijderd]

silentsnow schreef op zondag 13 februari 2005 @ 19:08:
Het lijkt mij een stuk efficienter om de array te scannen elke keer als je een woord invoert. Hier kan je mooi een methode voor schrijven die het woord in de array zet als deze er nog niet in voorkomt, en anders niets doet. Bijvoorbeeld:

Java:

import java.util.*;

public class week1c
{
   static String[] words;
   int a=0;

   public static void main (String[] args)
   {
      SimpleIO.prompt("Voer de woorden in: ");
      String inputLine = SimpleIO.readLine();

      StringTokenizer st = new StringTokenizer(inputLine);
      int max = st.countTokens();
      words=new String[max];

      while (st.hasMoreTokens())
      {
         insert(st.nextToken());
      }

      for (int x=0;x<max;x++ )
      {
         System.out.println(words[x]);
      }
   }

   private static void insert(String s)
   {
      for ()
      {
            // scan de gehele array voor het woord "s". Indien deze niet in de array voorkomt, voer hem dan in.
      }
      a++;  // indien je het woord in de array zet.
   }
}

is een idee, maar dan moet ik mijn hele code omgooien, is er geen gemakkelijkere oplossing?

[bigbeng]

Is het niet praktischer om een Set te gebruiken uit het Collections framework? Een van de typerende dingen aan een Set is dat er geen dubbelingen in voorkomen. Ik ken bijvoorbeeld de TreeSet, die lijkt precies te zijn wat je nodig hebt.
http://java.sun.com/j2se/...pi/java/util/TreeSet.html

[prototype]

Misschien is het een idee om de woorden en frequentie van deze op te slaan in een generieke Map<String, Integer> mbv een TreeMap<String, Integer> met een comparable om het te sorteren? Een key is hierbij dus uniek (de string woord).

[drm]

De meest eenvoudige manier is idd een Set gebruiken. (Zie bigbeng)

---

silentsnow:
Het lijkt mij een stuk efficienter om de array te scannen elke keer als je een woord invoert. Hier kan je mooi een methode voor schrijven die het woord in de array zet als deze er nog niet in voorkomt, en anders niets doet. Bijvoorbeeld:

Java:

for (int x=0;x<max;x++ )
{
   System.out.println(words[x]);
}

Dit klopt niet. max bevat het aantal tokens, niet het aantal unieke tokens

[Verwijderd]

heb ook nog dit bedacht:

niet zo netjes maar de gesorteerde array nog een doorlopen en kijken of er dubbele inzitten, werkt niet wat doe ik verkeerd?

code:

 for (int z=0;z<n;z++ )
  {
      if (s2[z].equalsIgnoreCase(s2[z+1]))
      {
       s2[z+1]=s2[z+2];
      }

      
 }

of iets opnemen in de print statement bedacht ik me:

code:

    if (words[x].equalsIgnoreCase(words[x+1]))
    {
    System.out.println(words[x]);
    }

werkt uiteraard ook niet ....

[drm]

femkester:
heb ook nog dit bedacht:

niet zo netjes maar de gesorteerde array nog een doorlopen en kijken of er dubbele inzitten, werkt niet wat doe ik verkeerd?

Is inderdaad niet zo netjes, want 't is nogal inefficient, magoed

code:

 for (int z=0;z<n;z++ )
  {
      if (s2[z].equalsIgnoreCase(s2[z+1]))
      {
       s2[z+1]=s2[z+2];
      }
  }

Je verschuift op deze manier 't probleem alleen maar. Doordat je s2[z+1] = s2[z+2] uitvoert, worden die twee elementen aan elkaar gelijk, maar je verwijdert verder geen elementen. De array is aan het eind van de loop nog even lang (wat niet klopt met de postconditie dat je array geslonken moet zijn als er dubbele elementen in zitten).

of iets opnemen in de print statement bedacht ik me:

Feitelijk hetzelfde probleem.

Ik kan je wel vertellen hoe je dat op kunt lossen, maar dan is de lol er een beetje vanaf, en als je niet op zoek bent naar lol moet je gewoon een Set gebruiken

[Verwijderd]

ow verlos mij uit de kwelling van deze zondagavond

kan het ook zonder sets, sets namelijk nooit gehad..

[drm]

femkester:
ow verlos mij uit de kwelling van deze zondagavond

kan het ook zonder sets, sets namelijk nooit gehad..

Nou, da's toch echt een kwestie van de docs lezen.
• interface SortedSet uit java.util
• implementing class TreeSet uit java.util

[ Voor 4% gewijzigd door drm op 13-02-2005 21:11 ]

[Robtimus]

Een set is gewoon een verzameling waarin elk element maar 1x mag voorkomen. Een SortedSet is, zoals de naam aangeeft, een gesorteerde set.

De TreeSet is idd uitstekend voor dit probleem, zonder Comparator. Dan gebruikt hij nml de String.compareTo method voor het vergelijken, precies wat je wilt. Je hoeft niet eens te controleren of iets al in de set zit, je voegt gewoon een string toe en de set zorgt er wel voor dat hij maar 1x voorkomt, in alfabetische volgorde.

[-FoX-]

Verwijderd schreef op zondag 13 februari 2005 @ 21:06:
ow verlos mij uit de kwelling van deze zondagavond

kan het ook zonder sets, sets namelijk nooit gehad..

Okay dan.. het is allemaal zo ingewikkeld niet...

Volgende code zou alles toch iets duidelijker moeten maken:

Java:

import java.util.*;

public class Week1c{
    public static void main(String[] args) {

    Set strSet = new TreeSet();
    //Set strSet = new TreeSet(String.CASE_INSENSITIVE_ORDER);

        // Voeg elk argument toe aan de Set:
        for (int i=0; i < args.length; i++) {
            strSet.add(args[i]);
        }
        System.out.println(strSet);
    }
}

Dan kan je nog zelf een comparator gaan schrijven, en deze als argument meegeven bij de creatie van de TreeSet. Op die manier kan je je eigen sortering gaan bepalen (bvb: sorteren op de omgekeerde lettervolgorde oid)

[ Voor 19% gewijzigd door -FoX- op 13-02-2005 21:54 ]

[Alarmnummer]

Je kunt natuurlijk ook gebruik maken van Collections.sort

[Verwijderd]

-FoX- schreef op zondag 13 februari 2005 @ 21:53:
[...]

Okay dan.. het is allemaal zo ingewikkeld niet...

Volgende code zou alles toch iets duidelijker moeten maken:

Java:

import java.util.*;

public class Week1c{
    public static void main(String[] args) {

    Set strSet = new TreeSet();
    //Set strSet = new TreeSet(String.CASE_INSENSITIVE_ORDER);

        // Voeg elk argument toe aan de Set:
        for (int i=0; i < args.length; i++) {
            strSet.add(args[i]);
        }
        System.out.println(strSet);
    }
}

Dan kan je nog zelf een comparator gaan schrijven, en deze als argument meegeven bij de creatie van de TreeSet. Op die manier kan je je eigen sortering gaan bepalen (bvb: sorteren op de omgekeerde lettervolgorde oid)

ik ga het morgenochtend gelijk proberen!

[Verwijderd]

de opdracht is veranderd, ik moet de zin meegeven als argument in de command prompt,

dus

code:

java Sort deze zin moet worden gesorteerd

weet iemand hoe ik dat doe, kan niets vinden in de boeken of i-net

[Roel]

Zodra je je java programma opstart wordt de rest wat je opgeeft ook aan de main methode doorgegeven, en komt in String[] args. Een array met stringen waarbij ieder woord een nieuwe string is.

Even die uitlezen en je hebt je zin

[Verwijderd]

Roel schreef op zaterdag 19 februari 2005 @ 12:41:
Zodra je je java programma opstart wordt de rest wat je opgeeft ook aan de main methode doorgegeven, en komt in String[] args. Een array met stringen waarbij ieder woord een nieuwe string is.

Even die uitlezen en je hebt je zin

ai daar wordt het geheel wel een stukkie eenvoudiger door

[Verwijderd]

-FoX- schreef op zondag 13 februari 2005 @ 21:53:
[...]

Okay dan.. het is allemaal zo ingewikkeld niet...

Volgende code zou alles toch iets duidelijker moeten maken:

Java:

import java.util.*;

public class Week1c{
    public static void main(String[] args) {

    Set strSet = new TreeSet();
    //Set strSet = new TreeSet(String.CASE_INSENSITIVE_ORDER);

        // Voeg elk argument toe aan de Set:
        for (int i=0; i < args.length; i++) {
            strSet.add(args[i]);
        }
        System.out.println(strSet);
    }
}

Dan kan je nog zelf een comparator gaan schrijven, en deze als argument meegeven bij de creatie van de TreeSet. Op die manier kan je je eigen sortering gaan bepalen (bvb: sorteren op de omgekeerde lettervolgorde oid)

ik mag niet gebruik maken van de sort libraries van java voor de opdracht, dus neem aan dat treeset ook buiten het te mogen gebruiken valt
dus moet met een andere oplossing komen ...

ik heb een bubble sort geschreven en het moet dus een insertion sort worden

[ Voor 7% gewijzigd door Verwijderd op 20-02-2005 12:54 ]

[Verwijderd]

code:

import java.util.*;
import jpb.*;

public class InsertSort {

public static void main (String[] args) {
    
    //input opgeslagen in string inputLine 
    SimpleIO.prompt("Voer de woorden in: ");
    String inputLine = SimpleIO.readLine();
    StringTokenizer st = new StringTokenizer(inputLine);
    //als er geen woorden voorkomen exit programma
    if (st.countTokens()<1)
    { System.exit(0);
    }
    //tel het aantal tokens, deze staan gelijk aan het aantal elementen nodig in array words
    int max = st.countTokens(); 
    String [] words;
    words=new String[max];
    int a=0;
    
    //zet de losse woorden in de string array words
     while (st.hasMoreTokens()) {
         words[a] = st.nextToken();
         a++;
     }
    
    //voer soort uit
    words=sort(words);
    
    //print de array words
    for (int x=0;x<max;x++ )
    {
    
    System.out.println(words[x]);
    
    
}

} 

private static String[] sort(String[] s) {
  
 int i;
 String temp;
 int l = s.length;

 for (int u = 0; u <= l-1; u++){
      temp = s[u];
      i = u - 1;
      while ( i >= 0 && (s[i].compareTo(temp)>=0)){
            s[i+1] = s[i];
                i--;
                }
      s[i+1] = temp;
  }


  //geef de waardes van de gesorteerde array
  return s;
}


}

ik heb nu het volgende en het werkt echter hij laat duplicaten staan, weet iemand hoe ik dit kan verhelpen??

[ Voor 58% gewijzigd door Verwijderd op 20-02-2005 14:16 ]

[Gert]

Loop door de array en haal de dubbelen er uit, bijvoorbeeld door een woord te pakken, nogmaals door de array te lopen en alle dubbelen waarvoor geld indexdubbel > indexwoord op null te zetten.

[Verwijderd]

Gert schreef op zondag 20 februari 2005 @ 16:46:
Loop door de array en haal de dubbelen er uit, bijvoorbeeld door een woord te pakken, nogmaals door de array te lopen en alle dubbelen waarvoor geld indexdubbel > indexwoord op null te zetten.

hoe bedoel je dat precies?

[Gert]

Zoals ik het zeg.

Duidelijkere pseudo code is moeilijk dus dan maar zo.

Java:

for (int x = 0; x < s.length; x++) {
  if (s[x] != null) {
    for (int y = x+1; y < s.length; y++) {
      if (s[x].equalsIgnoreCase(s[y]) {
         s[y] = null;
      }
    }
  }
}

Dit is natuurlijk niet zo netjes dus je zou hierna kunnen tellen hoeveel niet null elementen er voor komen en een nieuwe array maken met die grote en deze daarin kopieren.

[MrBucket]

Verwijderd schreef op zondag 20 februari 2005 @ 13:44:
ik heb een bubble sort geschreven en het moet dus een insertion sort worden
<knip>
ik heb nu het volgende en het werkt echter hij laat duplicaten staan, weet iemand hoe ik dit kan verhelpen??

Duplicaten kan je heel makkelijk voorkomen met een insertion sort, door ze gewoon niet in te voegen

Stel, je hebt een lijst met woorden (bijv. in een vector, list of arraylist) die ten alle tijden gesorteerd is. In het begin is die lijst nog leeg, maar elke keer als je een woord wil invoegen moet je eerst de juiste plaats bepalen in de lijst waar het nieuwe woord moet komen. Dus: na alle woorden die alfabetisch kleiner zijn, maar voor alle woorden die alfabetisch groter zijn. Als je die plek hebt gevonden, maar ziet dat er op die plek al een woord staat (omdat 'ie en niet alfabetisch groter en niet alfabetisch kleiner is dan het nieuwe woord), dan heb je te maken met hetzelfde woord. En dan voeg je het nieuwe woord dus niet in.

De reden waarom je trouwens geen array, maar een 'echte' datastructuur zou willen gebruiken, is dat die een insert()-methode kennen, waarmee je een nieuw element op een specifieke plek kunt invoegen. En dat werkt een stukje handiger als handmatig alle elementen een plek opschuiven om vervolgens je nieuwe element in de array te kopieren.

[Verwijderd]

de theorie begrijp ik maar nu nog in code omzetten, wat doe ik dan precies verkeerd?

[MrBucket]

Verwijderd schreef op zondag 20 februari 2005 @ 18:50:
de theorie begrijp ik maar nu nog in code omzetten, wat doe ik dan precies verkeerd?

Hmm, de code komt volgens mij bijna letterlijk van http://linux.wku.edu/~lamonml/algor/sort/insertion.html, of niet

Hetgeen wat ze daar doen is een in-place sortering. Dat kan ook, en is zelfs efficienter dan beginnen met een lege lijst en deze woord voor woord vullen, zodanig dat de lijst op elk moment gesorteerd is. Maar de tweede aanpak staat je toe om ervoor te kiezen een woord (in dit geval een duplicaat) niet in te voegen, iets wat ik in de eerste aanpak niet zo snel zie gebeuren omdat alle woorden zich dan al in de lijst bevinden.

Ik heb even zitten dimdammen of ik onderstaande code wel moest posten of dat ik het je het beter zelf uit kon laten zoeken, maar omdat het probleem op zich eigenlijk te simpel is om daar nog moeilijk over te gaan doen, en het vrij aardig illustreert hoe je met een datastructuur als een vector werkt, heb ik het toch maar gepost.

Het idee is dus dat je begint met een lege vector, en vervolgens elk woord uit je woordenlijst aan de vector toevoegt met onderstaande addWord(). Als alle woorden zijn toegevoegd, heb je een gesorteerde lijst met woorden zonder duplicaten.

Java:

/**
 *  Adds sNewWord at the correct position to vSortedWords, such that 
 *  vSortedWords is lexicographically sorted.
 */
Vector MyClass::addWord(Vector vSortedWords, String sNewWord){
  String sWord;
  int iCmpResult;
  
  //Find proper position to insert word at  
  for(int iPos = 0; iPos < vSortedWords.size(); iPos++){
    sWord = (String)vSortedWords.get(iPos);
    iCmpResult = sWord.compareToIgnoreCase(sNewWord);
    
    if(iCmpResult >= 0){
      //Found the first word in vSortedWords that is equal or larger
      //than sNewWord. This should be a good point to insert.
      if(iCmpResult == 0){
        //The word in the vector is the same as sNewWord. Don't insert.
      }else{
        //Insert sNewWord at this position.
        vSortedWords.add(iPos, sNewWord);
      }
      //No need to check any more words - we're done.
      return vSortedWords;
    }
  }

  //Couldn't find a word that was equal or larger than sNewWord. Simply 
  //add it to the end of vSortedWords, then.
  vSortedWords.add(sNewWord);
  return vSortedWords;
}

[Verwijderd]

nee komt niet van die site, maar toch bedankt voor de tip, heel erg aardig dat je met code komt, maar mag helaas niet met vectoren werken, alles moet in arrays ...

[Verwijderd]

heb er nu wel genoeg aan geklust, niet helemaal netjes maar het werkt!

code:

public class InsertSort {

    public static void main (String[] args) {
    
        //voer sort uit
        args=sort(args);
    
        //print de gesorteerde array words
        int max=args.length;
    
        for (int x=0;x<max;x++ ){
                System.out.println(args[x]);
        }

    } 

    private static String[] sort(String[] s) {
    
        String temp;
        String g = "zz78rd34" ;
        int l = s.length;
        int ol = l;
        int i;

        for (int u = 0; u <= l-1; u++){
            //kopieer element naar temp
            temp = s[u];
            //i is 1 element eerder dan u
            i = u - 1;
            //doorloop array s en vergelijk vorige element met huidige
            while ( i >= 0 && (s[i].compareTo(temp)>=0)){
            
                //als elementen gelijk zijn, vervang inhoud element tydelijk door de waarde van string g
                if (s[i].compareTo(temp)==0){
                    s[i]= g;
                    //aangezien een duplicaat is gevonden moet de array met unieken met 1 worden verkleind
                    ol--;
                }
            
                //het huidige element wordt het volgende element    
                s[i+1] = s[i];
                //teller om naar volgende woord te gaan
                i--;
            }
            //het element wordt 1 naar rechts geschoven       
            s[i+1] = temp;
      
        }


        //maak een array aan voor unieke woorden
        String [] o;
        o=new String[ol];
        int a = 0;

        //zet de unieke woorden in array o
        for (int x=0;x<l;x++ ){
            if(s[x].compareTo(g)!=0){
                o[a]=s[x];
                a++;
            }
    
    
        }

        //geef de waardes van de gesorteerde array
        return o;
    }   


}