Banco de dados, Ordenação alfabética. - C/C++ - Mente Binária
Banco de dados, Ordenação alfabética.
By Amanda Estella, July 9 in C/C++
Amanda Estella 1
Olá, alguém poderia me ajudar? Tenho que fazer um projeto, mas n faço ideia de como. Preciso ordenar os nomes das peças em ordem alfabética. Como é trabalhado em banco de dados n sei muita coisa sobre. Isso é o que eu fiz só precisa do ordenação; Eu sei que tem algumas coisas desnecessárias nesse código, mas ele n esta inteiro, so preciso da parte de ordenar os arquivos pelo nomes que ja estão salvo no pecas.dados
Mesmo com código incompleto, existem diversos problemas aqui:
system("cls");  // NÃO é recomendado!
Ao invés disso você poderia usar uma função que apague a tela. Eis uma que disponibilizo em meu artigo Pare de usar system() nos seus códigos!. Como plus, vai um gotoxy() também...
Outro problema é o uso da função getche() - que não existe na biblioteca padrão! Use getchar().
Quanto á ordenação. Neste código ela é problemática sob o ponto de vista de performance, uma vez que você não mantém nenhum "arquivo de índices" (com uma árvore balanceada contendo a ordem já na inserção)... Assim, terá que recorrer a algum external sorting. Um jeito de fazer é determinar quantos registros há no seu arquivo:
size_t getNumRecords( FILE *f )
long oldpos, endpos;
oldpos = ftell( f );       // guarda posição atual.
fseek( f, 0, SEEK_END );  // pula para o fim do arquivo.
endpos = ftell( f );     // pega tamanho do arquivo.
fseek( f, oldpos, SEEK_SET );  // volta para a posição original.
// Retorna o número de registros no arquivo.
return endpos / sizeof( struct pecas );
De posse desse valor, você pode fazer ordenações rápidas de partições do arquivo... Por exemplo, partições de 2048 registros (isso precisa de um buffer de cerca de 128 KiB apenas, devido ao tamanho da sua estrutura), criando (recs / 2048) arquivos diferentes. A cada 2048 registros do arquivo original você os ordena, na memória, e salva os registros em cada um desses arquivos.
De posse desses arquivos, você abre cada um deles, selecionando a "menor chave" que achar em todos e escreve o registro correspondente num arquivo final (eliminando esse registro do arquivo onde o obteve) - Esse é o princípio do merge external sorting...
No fim das contas, seu arquivo final estará ordenado.
PS: Para ordenar um grupo de N registros (ou menos) usando quicksort:
static int cmp( const void *ptr1, const void *ptr2 )
// OBS: Se desejar um "natural sorting" isso fica mais complexo!
return strcmp( ((struct pecas *)ptr1)->nome, ((struct pecas *)ptr2)->nome );
void sort( struct pecas *ptr, size_t count )
{ qsort( ptr, count, sizeof *ptr, sort ); }
PS2: Existem meios de fazer a mágica com apenas 3 arquivos intermediários, mas dará bem mais trabalho...
Anyway... eu recomendo que você use algum "banco de dados" não relacional como o gdbm, por exemplo...
O external sorting eu deixo por sua conta... Mas, eis um exemplo com letras. Suponha que tenhamos 3 arquivos ordenados:
1: ADFGS
2: HJKLQ
Abre-se o arquivo 1 e 2 e determina-se que A < H, salva 'A' no arquivo 4, tirando-o do arquivo 1:
1: DFGS
Mesma coisa para o arquivo 1 e 3, e determina-se que 'D' < 'I':
1: FGS
Repete-se os procedimentos acima (para 1 e 2; e 1 e 3), até que os 3 arquivos estejam vazios. No final, o arquivo 4 será o arquivo ordenado.
PS: O motivo de eu ter sugerido N arquivos de 2048 registros cada é para usar a memória de maneira conveniente... 2048 registros, como eu disse, ocuparão 128 KiB de RAM. Se todos os registros de seu "banco de dados" couberem na memória, não há necessidade de um external sorting.
PS2: Repare que o procedimento pode ser um cadinho mais complicado do que citei acima... imagine que o arquivo 1 fique sem registros, daí a comparação terá que ser entre os arquivos 2 e 3. De fato, as comparações deveriam ser feitas entre 1 e 2; 1 e 3 e 2 e 3, para selecionar a "menor chave"... Com N arquivos, teremos uma "combinção" de N, 2 a 2, que pode ser bem grande!
Uma última dica: Leia o volume 3 do "The Art of Computer Programming" de Donald E. Knuth. Lá você encontrará algoritmos para external sorting...