Matriz ordenada - Sorted array
| Matriz ordenada | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Modelo | Variedade | ||||||||||||||||||||
| Inventado | 1945 | ||||||||||||||||||||
| Inventado por | John von Neumann | ||||||||||||||||||||
| Complexidade de tempo em notação grande O | |||||||||||||||||||||
| |||||||||||||||||||||
Uma matriz classificada é uma estrutura de dados de matriz na qual cada elemento é classificado em ordem numérica, alfabética ou em alguma outra ordem e colocado em endereços igualmente espaçados na memória do computador. É normalmente usado em ciência da computação para implementar tabelas de pesquisa estáticas para conter vários valores que têm o mesmo tipo de dados . A classificação de um array é útil para organizar os dados de forma ordenada e recuperá-los rapidamente.
Métodos
Existem muitos métodos conhecidos pelos quais um array pode ser classificado, que incluem, mas não estão limitados a: classificação por seleção , classificação por bolha , classificação por inserção , classificação por mesclagem , classificação rápida , classificação por heapsort e classificação por contagem . Essas técnicas de classificação têm diferentes algoritmos associados e, portanto, há diferentes vantagens em usar cada método.
Visão geral
Matrizes classificadas são a estrutura de dados mais eficiente em termos de espaço com a melhor localidade de referência para dados armazenados sequencialmente.
Os elementos dentro de um array ordenado são encontrados usando uma pesquisa binária , em O (log n ); portanto, os arrays classificados são adequados para os casos em que é necessário procurar elementos rapidamente, por exemplo, como um conjunto ou estrutura de dados multiset . Essa complexidade para pesquisas é a mesma que para árvores de pesquisa binárias com autobalanceamento .
Em algumas estruturas de dados, uma matriz de estruturas é usada. Nesses casos, os mesmos métodos de classificação podem ser usados para classificar as estruturas de acordo com alguma chave como um elemento de estrutura; por exemplo, classificando os registros dos alunos de acordo com os números, nomes ou notas do rolo.
Se estiver usando uma matriz dinâmica classificada , é possível inserir e excluir elementos. A inserção e exclusão de elementos em uma matriz ordenada é executada em O ( n ), devido à necessidade de deslocar todos os elementos após o elemento a ser inserido ou excluído; em comparação, uma árvore de pesquisa binária de autobalanceamento insere e deleta em O (log n ). No caso em que os elementos são excluídos ou inseridos no final, um array dinâmico classificado pode fazer isso em tempo O (1) amortizado, enquanto uma árvore de busca binária de autobalanceamento sempre opera em O (log n ).
Os elementos em uma matriz classificada podem ser consultados por seu índice ( acesso aleatório ) no tempo O (1), uma operação que leva tempo O (log n ) ou O ( n ) para estruturas de dados mais complexas.
História
John von Neumann escreveu o primeiro programa de classificação de array ( merge sort ) em 1945, quando o primeiro computador com programa armazenado ainda estava sendo construído.
Aplicativos de matrizes classificadas
Computação comercial
Organizações governamentais, empresas privadas e muitos aplicativos baseados na web têm que lidar com grandes quantidades de dados. Os dados geralmente terão que ser acessados várias vezes. Manter os dados em um formato classificado permite uma recuperação rápida e fácil.
Em matemática discreta
Matrizes classificadas podem ser usadas para implementar o algoritmo de Dijkstra ou o algoritmo de Prim . Além disso, algoritmos como o algoritmo de Kruskal para encontrar árvores geradoras mínimas.
Em agendamento prioritário
No nível do sistema operacional , muitos processos estão pendentes por vez, mas eles podem lidar com apenas um processo por vez. Portanto, as prioridades estão associadas a cada processo. Em seguida, os processos são enviados para a CPU de acordo com a prioridade mais alta, usando uma matriz classificada de IDs de processo. Aqui, os processos são classificados de acordo com suas prioridades e a CPU é alocada para eles. O processo com a prioridade mais alta assume a primeira posição na matriz classificada. Portanto, é feito o agendamento prioritário dos processos do sistema.
No agendamento do trabalho mais curto primeiro
Este é o caso especial do agendamento prioritário. Aqui, os processos são classificados de acordo com o tempo de burst dos processos. O processo que requer o menor tempo será alocado na CPU primeiro. Conseqüentemente, os processos estão sendo enviados para a CPU de acordo com seu tempo de burst.
| Processar | Tempo de explosão |
|---|---|
| P1 | 3 |
| P2 | 4 |
| P3 | 1 |
| P4 | 8 |
| P5 | 6 |
Veja também
- Algoritmo de classificação
- Algoritmo de busca binária
- Heap (estrutura de dados)
- Estrutura de dados de pesquisa