[JAVA] Ordinare i caratteri di una stringa

[CippaPero]

Voglio ordinare mediante un doppio ciclo for una stringa confrontando di volta in volta i char che la costituiscono e nel frattempo ordinare un array di indici che esula dal resto;
nel momento in cui ritorno un array di char contenente la Stringa che dovrebbe essere ordinata ottengo invece una stringa in cui i caratteri vengono si spostati ma non so secondo quale logica O.o

ordinato=k.toCharArray(); 
for(int i=0;i<k.length()-1;i++){
 char box; int boxindice; 
     for(int j=1;j<k.length();j++){ 
          if(k.charAt(i)>k.charAt(j)){
                  box=ordinato[i]; 
                  boxindice=indici[i]; 
                  ordinato[i]=ordinato[j];
                  indici[i]=indici[j]; 
                  ordinato[j]=box; 
                  indici[j]=boxindice; 
          } 
       } 
}

es
q9YU --> U9Yq
xsGe --> eGxs

Deve esserci qualche errore nel codice , magari una stupidata ... se qualcuno volesse illuminarmi ve ne sarei grato

Grazie.

[LeleFT]

Stando all'algoritmo che intendi usare (un bubble-sort), l'indice del for più interno dovrebbe partire dall'attuale valore dell'indice del for più esterno. L'algoritmo, infatti, ad ogni iterazione del for più esterno, porta verso sinistra il valore "più piccolo"... non ha senso, quindi, confrontare gli elementi già ordinati.

for(int j=i;j<k.length();j++){

Questo per quanto concerne la logica dell'algoritmo.

E' chiaro che, per poter funzionare, è necessario che i confronti vengano fatti sull'array ordinato e non sulla stringa, che, essendo immutabile e non venendo mai toccata, non viene di certo ordinata. Quindi dovresti effettuare i confronti usando l'array "ordinato" e non i caratteri provenienti da "k.charAt(...)"... proprio perchè tu non modifichi la stringa "k".

if(ordinato[i]>ordinato[j]){

Ciao.

[CippaPero]

Grazie ,hai perfettamente ragione XP

[Who am I]

Stai applicando in maniera sbagliata il bubblesort, non devi continuare a confrontare l' elemento di indice i con quello di indice j.Semmai l' elemento di indice i con l' elemento di indice i+1, altrimenti confronti sempre lo stesso elemento:

        char[] ordinato=k.toCharArray();
    	for(int i=0;i<k.length()-1;i++)
    	{
    	    for(int j=0;j<k.length()-i-1;j++)
    	    { 
    	          if(ordinato[j] > ordinato[j+1])
    	          {
    	              char temp=ordinato[j];
    	              ordinato[j]=ordinato[j+1];
    	              ordinato[j+1]=temp;
    	          }
    	    } 
    	}

Ti consiglio di prenderti l' algoritmo del bubblesort e di provare ad implementarlo per conto tuo.

[Who am I]

Originariamente inviato da LeleFT

Lui però l' ha fatto al contrario.
Quindi l' indice deve andare da 0 fino a length()-i-1 .
Anche se è vero che l' algoritmo standard del bubblesort non è così.

[LeleFT]

Originariamente inviato da Who am I
Lui però l' ha fatto al contrario.
Quindi l' indice deve andare da 0 fino a length()-i-1 .
Anche se è vero che l' algoritmo standard del bubblesort non è così.

Ehm... ho sbagliato io l'inizializzazione del secondo for... è sufficiente che j parta da i+1 fino a k.length(). Farlo in un senso o nell'altro non ha alcuna importanza: spostare in testa i valori più piccoli o portare alla fine quelli più alti non cambia molto... il senso dell'algoritmo è equivalente.
Il problema era che i confronti li faceva sulla stringa originale e non sull'array che stava ordinando.


Ciao.

[Scara95]

Originariamente inviato da LeleFT
Farlo in un senso o nell'altro non ha alcuna importanza: spostare in testa i valori più piccoli o portare alla fine quelli più alti non cambia molto...
Ciao.

Cambierebbe su una lista. Comunque mi chiedevo con tutti gli algoritmi che ci sono perchè proprio un bubble sort? Ce ne sono di molto più performanti...

[CippaPero]

E' il primo che mi è venuto in mente, se ne conosci di più performanti non ti impedisco di suggerirmene qualcuno . Grazie ancora

[Scara95]

Un quicksort (almeno che la stringa non sia già ordinata)?
Oppure un merge sort...
Oppure Wikipedia con la tavola delle comparazioni e gli esempi di codice ^^
Comunque il quicksort è uno degli algoritmi più usati...

[Who am I]

Originariamente inviato da LeleFT
Il problema era che i confronti li faceva sulla stringa originale e non sull'array che stava ordinando.

Non solo.Stava confrontando l' elemento i-esimo con l' elemento j-esimo.
Pur facendo tale controllo sull' array di char l' algoritmo non sarebbe giusto.
Bisogna confrontare l' elemento (j+1)-esimo con l' elemento j-esimo.

A proposito dell' algoritmo, non è vero che il quicksort e il mergesort compiono sempre meno operazioni del bubblesort.Anche se hanno una complessità bassa le costanti moltiplicative sono alte, per cui il quicksort e il mergesort impiegano meno tempo solo per array molto numerosi.
E suppongo che il suo array non sia molto grande, per cui il bubblesort va bene.