Algoritmos/Arquivos/Arquivos sequenciais
Num arquivo sequencial a organização de seus itens faz-se de forma que para acessar um determinado registro é necessário varrer todos os que antecedem. A sequência do arquivo pode ser baseada na ordenação através de alguma chave (um campo ou uma combinação de campos), sendo que:
- É a mais conhecida e usada organização de arquivo;
- Apresenta as mais simples (com baixa complexidade de programação) implementações de operações básicas.
Chaves de Ordenação
Os registros de um arquivo de qualquer estrutura podem estar ordenados ou não. Quando não estão ordenados eles são armazenados de acordo com a ordem de inserção, sendo que cada novo registro será alocado ao fim do arquivo (ARQUIVOS SEQUENCIAIS, 2017). Porém, em algumas implementações há a necessidade de acessar os arquivos em uma ordem específica, e nesse caso usamos um critério para definir a ordenação. Esse critério é chamado de chave.
Uma chave de ordenação pode ser composta de uma das seguintes formas:
- Um campo;
- Uma parte de um campo;
- Uma combinação de campos;
- Resultado do processamento de um ou mais campo.
Organização dos Arquivos Sequenciais
Os registros de um Arquivo Sequencial são organizados das seguintes formas:
- Desordenados;
- Ordenados por uma chave (Fisicamente ou Logicamente).
Exemplos:
- Tabela de Arquivo Sequencial Desordenado
| Posição | Paciente | Sangue | RH | Doação | Contato | Peso |
|---|---|---|---|---|---|---|
| 1 | Ricardo | A | + | 09/03/2010 | (33)0892-1232 | 73 |
| 2 | Joaquim | O | - | 10/10/2009 | (54)2324-6902 | 97 |
| 3 | Leandro | AB | + | 04/07/2011 | (64)1903-1234 | 72 |
| 4 | Maria | B | - | 02/01/2011 | (90)9102-8213 | 61 |
| 5 | Felipe | A | - | 08/09/2012 | (23)2978-4902 | 48 |
| 6 | Ana | O | + | 02/11/2014 | (76)2983-2393 | 50 |
(ESTRUTURA DE DADOS 2, 2017)
Nesse exemplo a tabela está desordenada, ou seja, nenhum campo/coluna trás ordenação para a mesma. Nesse caso, ao inserir um elemento pode-se inseri-lo no final da tabela.
- Tabela de Arquivo Sequencial Ordenado Fisicamente
| Posição | Paciente (Chave) | Sangue | RH | Doação | Contato | Peso |
|---|---|---|---|---|---|---|
| 1 | Ana | O | + | 02/11/2014 | (76)2983-2393 | 50 |
| 2 | Felipe | A | - | 08/09/2012 | (23)2978-4902 | 48 |
| 3 | Joaquim | O | - | 10/10/2009 | (54)2324-6902 | 97 |
| 4 | Leandro | AB | + | 04/07/2011 | (64)1903-1234 | 72 |
| 5 | Maria | B | - | 02/01/2011 | (90)9102-8213 | 61 |
| 6 | Ricardo | A | + | 09/03/2010 | (33)0892-1232 | 73 |
(ESTRUTURA DE DADOS 2, 2017)
Nesse exemplo a tabela está ordenada pela chave Paciente e seus registros serão encontrados na memória nessa mesma ordem. Nesse caso, ao inserir, remover ou alterar um elemento deve-se primeiro achar fisicamente a posição desse elemento na tabela e logo após efetuar a operação.
OBS: É importante manter a integridade da ordenação na tabela.
- Tabela de Arquivo Sequencial Ordenado Logicamente
| Posição | Paciente | Sangue | RH | Doação | Contato | Peso | Próximo |
|---|---|---|---|---|---|---|---|
| 0 | 6 | ||||||
| 1 | Ricardo | A | + | 09/03/2010 | (33)0892-1232 | 73 | -1 |
| 2 | Joaquim | O | - | 10/10/2009 | (54)2324-6902 | 97 | 3 |
| 3 | Leandro | AB | + | 04/07/2011 | (64)1903-1234 | 72 | 4 |
| 4 | Maria | B | - | 02/01/2011 | (90)9102-8213 | 61 | 1 |
| 5 | Felipe | A | - | 08/09/2012 | (23)2978-4902 | 48 | 2 |
| 6 | Ana | O | + | 02/11/2014 | (76)2983-2393 | 50 | 5 |
(ESTRUTURA DE DADOS 2, 2017)
Nesse exemplo a tabela também está ordenada pela chave Paciente, mas seus registros não serão encontrados na memória nessa mesma ordem. Usa-se um campo de endereço chamado Próximo no arquivo para saber a ordem do registro. Nesse caso, ao inserir, remover ou alterar um elemento deve-se primeiro achar logicamente a posição desse elemento na tabela e logo após efetuar a operação.
Operações em Arquivos Sequenciais
São 5 as principais operações básicas em arquivos sequenciais:
- Busca
- Inserção
- Remoção
- Alteração
- Listagem
Ordenação Externa
Quando um arquivo sequencial ordenado perder sua ordenação, então deve ser reordenado. Porém, normalmente o conjunto de registros é maior do que a capacidade da memória principal de armazená-los. Nesses casos, os algoritmos tradicionais de ordenação, como o quicksort, não são eficientes, pois requerem muitas operações de leitura e escrita de registros e essas operações no disco são lentas.
A opção mais viável nesses casos é a ordenação externa, como o próprio nome sugere, ordenação externa é o processo de ordenação feito com o auxílio de algum dispositivo de memória externa como, por exemplo, HD's, pendrives e outros. Os métodos de ordenação externa são muito diferentes dos métodos de ordenação interna, já que na ordenação externa os algoritmos devem diminuir o número de acesso as unidades de memória. Deve considerar, também, a otimização através do uso eficiente de buffers e mecanismos do disco rígido.
Fatores que determinam as diferenças das técnicas de ordenação externa:
- Custo para acessar um item.
- O custo principal na ordenação externa é relacionado a transferência de dados entre a memória interna e externa.
- Existem restrições severas de acesso aos dados.
- O desenvolvimento dos métodos é muito dependente do estado atual da tecnologia.
- A variedade de tipos de unidades de memória externa torna os métodos dependentes de vários parâmetros.
Intercalação balanceada
[editar | editar código-fonte]A intercalação balanceada é um algorítimo que ordena os registros por meio da intercalação de 'N' caminhos balanceados.
• Etapas:
1. Distribuição de blocos de registros ordenados por N caminhos balanceados.
2. Intercalações sucessivas dos N caminhos.
Referência Bibliográfica:
ESTRUTURA DE DADOS 2.Dica de Leitura. Disponível em: <https://pt.slideshare.net/KianeLedok/edii04-20121-arquivos-sequenciais-definio-e-desordenado>. Acesso em: 18 de mai. 2017.
ARQUIVOS SEQUENCIAIS.Dica de Leitura. Disponível em: <http://www.din.uem.br/~yandre/AEDEP/arquivo-sequencial.pdf>. Acesso em: 18 de mai. 2017.
Ordenação. Dica de Leitura. Disponível em: <http://www.din.uem.br/~yandre/AEDEP/arquivo-sequencial.pdf>. Acesso em: 24 de mai. 2017.
Livro “Projeto de Algoritmos” – Nívio Ziviani - Capítulo 4. Disponível em: <http://www2.dcc.ufmg.br/livros/algoritmos/implementacoes-04.php>. Acesso em: 24 de mai. 2017.