Scelta algoritmo di ordinamento

[lans23]

ragazzi...ho questo problema:
devo ordinare lessicograficamente un set di stringhe, la lunghezza è variabile ma data una lunghezza tutti i set devono essere lunghi uguali (per esempio tutti da 9 caratteri)

ESEMPIO:
ABBABBABA
DDKSJHAGK
ALOSHDGAA
NASBAHSJA
LOLOAHSIA
.....
lista ordinata:

ABBABBABA
ALOSHDGAA
DDKSJHAGK
LOLOAHSIA
NASBAHSJA
......
Potete consigliarmi il miglior algoritmo di ordinamento per questo problema, oltre ai soliti merge-sort e quick-sort. Sono applicabili quelli non a confronti che hanno costi O(n)????quali???

[gugoXX]

Prova a dare un occhio al Radix Sort.
che sia "Migliore" di altri dipende molto da quanti record da ordinare hai.

[lans23]

in generale si suppone siano tanti....cmq quello che volevo capire è se per questo tipo di ordinamento ci sono migliori possibilità (più efficienti) di quelle classiche come appunto il quick o il merge.
Il radix che ordina per cifra (in questo caso per lettera) usa per ogni cifra il counting-sort??? altrimenti non si spiegherebbe il tempo lineare, sarebbe un alg a confronti.

[gugoXX]

Originariamente inviato da lans23

Il radix che ordina per cifra (in questo caso per lettera) usa per ogni cifra il counting-sort??? altrimenti non si spiegherebbe il tempo lineare, sarebbe un alg a confronti.

No, questo e' l'errore. L'agoritmo interno del RADIX non ordina, ma distribuisce.
Semplicemente ad ogni passo dell'algoritmo dovrai costruire 23 liste, chiamate buckets. (23 sono le possibili lettere? Sarebbe 10 per le cifre decimali volendo). Passi ognuno dei record e lo vai a piazzare nel Bucket giusto, senza ordinare alcunche'.
Ovvio che tra un passo e l'altro potrai distruggere le liste precedenti non piu' usate.
In M passi, dove M e' la lunghezza delle stringhe da ordinare, sei a posto.
L'algoritmo e' infatti

O(N*M) ed e' migliore di O(N Log(N)) se N e' grande e M piccolo, soprattutto perche' nella rappresentazione algortmica O(N Log(N)) si trascura sempre la M, poiche' si presume che un cofnronto tra due elementi costi 1.
Cosa vera se sono numeri (meglio, "oggetti" trattabili in modo atomico dalla macchina), ma falsa se sono stringhe come in questo caso.

[lans23]

quindi mi converrebbe questo tipo di algoritmo...potresti postarmi una sorta di pseudocodice... non ho ben capito la distribuzione come avviene. ti ringrazio anticipatamente.

[gugoXX]

Provo

Sia N il numero di record ed M la lunghezza fissa di ciascun record.
La variabilita' di ciascun carattere e' A-Z, quindi 25 caratteri diversi.

Alloco un array di 25 Liste, chiamate Bucket, ciascuno associato ad un carattere

For m = 0 to M
  Buckets.Clear(); // Pulisco tutti i Bucket
  foreach string str in Records
    int questo=string[m];
         // Ovvero il carattere t-esimo del record u-esimo
    
    Bucket[questo].Add(str);
       // Ovvero aggiungo questa stringa al bucket corrispondente
  endfor
  
  Records=Bucket.Join();
      //Passo virtuale, in pratica ricostruisco di nuovo l'array di tutti
      // i record per il prossimo passo del ciclo for esterno
      // Ma in pratica non lo faro'. Semplicemente il foreach ciclera'
      //   sul contenuto dei buckets.
      // In pratica "io" farei una sorta di double buffer
      //    Con 25*2 liste
endfor

Come vedi non ci sono confronti, ma solo distribuzioni (esattamente M*N)

[lans23]

si ok, questo l'ho capito però segeundo questo esempio:

ESEMPIO RECORD:

DZAH
AVVA
MLOA
ABAB
DION

e costruendo le 26 liste distribuisco al primo passo in questo modo:

liste

A->AVVA->ABAB
B
C
D->DZAH->DION
E
....
L
M->MLOA
N
....
Poi al secondo passo per distribuire la seconda lettera come faccio???....cioè io alla fine devo avere questo:

A->ABAB->AVVA
B
C
D->DION->DZAH
E
....
L
M->MLOA
N

[wizard1993]

dentro ogni bucket ricicli ricorsivamente avendo quindi una repprentazione quale questa

a__
|a->abab
|...
|v->avva
il caso base è un bucket di un solo elemento

[gugoXX]

Originariamente inviato da wizard1993

dentro ogni bucket ricicli ricorsivamente avendo quindi una repprentazione quale questa

a__
|a->abab
|...
|v->avva
il caso base è un bucket di un solo elemento

Puo' essere che funzioni ma il RADIX dice diverso.

Distribuisci sull'ultima lettera:
A -> AVVA, MLOA
B -> ABAB
H -> DZAH
N -> DION

Poi riconsideri tutto come se fosse di nuovo un array, facendo attenzione a prendere il contenuto di ogni bucket nel proprio ordine (mi raccomando, considera solo, non fare veramente la JOIN)
AVVA, MLOA, ABAB, DZAH, DION
svuoti le liste (ne costruisci di nuove...) E distruisci sulla terza
A -> ABAB, DZAH
O -> MLOA, DION
V -> AVVA

Poi sulla seconda
B -> ABAB
I -> DION
L -> MLOA
V -> AVVA
Z -> DZAH

Poi sulla prima
A -> ABAB, AVVA
D -> DION, DZAH
M -> MLOA

E hai finito.

[lans23]

ok ci dovrei essere, penso di aver capito, ti ringrazio molto per la disponibilità.

[lans23]

ok,mi funziona....però ho provato a fare il quicksort applicato a stringhe e devo dire che è nettamente + veloce, è normale o cè qualcosa che non va nel mio radix-sort.

Paragone quick e mio:

Input: 10000 stringhe random da 7 caratteri
tempo: 0,172(mio) 0,016(quicksort)

Input: 50000 stringhe random da 7 caratteri
tempo: 17.0 (mio) 0,047(quicksort)

[Misciu87]

Ciao Ians,

potresti postare il codice del quicksort per l'ordinamento delle stringhe?

[khelidan1980]

Originariamente inviato da Misciu87

Ciao Ians,

potresti postare il codice del quicksort per l'ordinamento delle stringhe?

http://it.wikipedia.org/wiki/Quicksort

Qui trovi di tutto e di più!

[Misciu87]

Ci sono già andata su quel sito ma non mi è servito a nulla, io devo ordinare delle strighe prese da un file di input in linguaggio C, dovrei usare la strcmp ma ci ho provato in mille modi e nn riesco a risolvere nulla..

[khelidan1980]

Originariamente inviato da Misciu87

Ci sono già andata su quel sito ma non mi è servito a nulla, io devo ordinare delle strighe prese da un file di input in linguaggio C, dovrei usare la strcmp ma ci ho provato in mille modi e nn riesco a risolvere nulla..

fai un 3d,posti il codice e si vede cosa sbagli,il quicksort alla fine è sempre quello

Comunque qui è ancora meglio:

http://www.algorithm-code.com/wiki/Quick_Sort#C_Code

[Misciu87]

lo so che è sempre quello pero' quando nella partition si fanno i confronti tra le variabili non basta fare low<high && l[high]>=prvotkey perche' io ho delle stringhe e non degli interi non basta usare <> dovrei usare la strcmp!

[khelidan1980]

Originariamente inviato da Misciu87

lo so che è sempre quello pero' quando nella partition si fanno i confronti tra le variabili non basta fare low<high && l[high]>=prvotkey perche' io ho delle stringhe e non degli interi non basta usare <> dovrei usare la strcmp!

ripeto se apri un topic e posti il codice che non ti funziona,qualcuno sicuramente ti aiuterà

[Misciu87]

Ecco il codice incriminato:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>



void readsize(char *inputlist, int *length, int *size) {
	FILE *in=fopen("inputlist.txt","r");
	int i=0,j=0;
	char tmp;

	while(fscanf(in,"%c",&tmp)!=EOF && tmp!='\n') j++;
	rewind(in);
	while(fscanf(in,"%*s\n")!=EOF) i++;
	(*length)=i; (*size)=j;
	fclose(in);
}

char *readline(FILE *in,int size) {
	char *line=(char *)malloc(size*sizeof(char)), tmp;
	int i=0;

	while(i<size && fscanf(in,"%c",&line[i])!=EOF) i++;
	fscanf(in,"%c",&tmp);
	if(tmp!='\n') 
    {
		printf("Error: malformed file\n");
		return NULL;
	}

	return line;
}

char **loadlist(char *inputlist, int *length, int *size) {
	int i;
	char **list;
	FILE *in=fopen("inputlist.txt","r");
	
	readsize(inputlist,length,size);

	list=(char **)malloc((*length)*sizeof(char *));

	for(i=0; i<(*length); i++)
		list[i]=readline(in,(*size));
		
	fclose(in);

	return list;
}
void exchange(char **list, int i, int j) {
	char *tmp=list[i];
	list[i]=list[j];
	list[j]=tmp;
}

int partition(char **list, int p, int r) {
	int i=p, j=r, x, v;
	char *pivot;

	x=rand()%(r-p+1)+p;
	exchange(list,x,p);
	pivot=list[p];
	
	while(p<r) 
    {
		
        while(j>p && strcmp(list[j],pivot)<0) 
          j--;
		while(i<r && strcmp(list[j], pivot)>=0) i++;
		if(i<j) 
          exchange(list,i,j);
	} 
	exchange(list,p,j);
	
}
char **sortlist (char **list, int p, int r) {
	
     int q,i;
	
	if(p<r)
    {
        
		q=partition(list,p,r);
		
		sortlist(list,p,q-1);
		sortlist(list,q+1,r);
	}
	return list;
}
void printlist(char *outputlist, char **list, int length) 
{
	int i;
	FILE *out=fopen("outputlist.txt","w");
	
	for(i=0; i<length; i++)
		fprintf(out,"%s\n",list[i]);
	fprintf(out,"\n");
	fclose(out);
}
int main(int argc, const char *argv[]) {

    char **list;	
	int length,size;
	time_t start, end;

	if(argc!=3) 
    {
		printf("Usage: stringsort <input list> <output list>\n");
		return 1;
	}

	list=loadlist((char *)argv[1],&length,&size);
	start=clock();

   	list=sortlist(list,length,size);
   	end=clock();
		
	printf("%g\n",(int)(end-start)/(int)CLOCKS_PER_SEC);
	printlist((char *)argv[2],list,length);

	return 0;
	
}

[Misciu87]

ci devono essere dei problemi quando faccio p<r,j<p ecc.

[VICIUS]

Non è molto carino inserirsi nelle discussioni altrui e chiedere aiuto su problemi completamente diversi. Apri una nuova discussione e vedrai che riceverai più attenzione.

In ogni caso chiuso.