Classificação na estrutura de dados: categorias e tipos [com exemplos]

A disposição dos dados em uma ordem preferencial é chamada de classificação na estrutura de dados. Ao classificar os dados, é mais fácil pesquisá-los de forma rápida e fácil. O exemplo mais simples de classificação é um dicionário. Antes da era da Internet, quando você queria procurar uma palavra em um dicionário, você o fazia em ordem alfabética. Isso facilitou.

Imagine o pânico se você tivesse que ler um livro grande com todas as palavras em inglês do mundo em uma ordem confusa! É o mesmo pânico pelo qual um engenheiro passará se seus dados não forem classificados e estruturados.

Então, em suma, a classificação torna nossas vidas mais fáceis. Confira nossos cursos de ciência de dados para aprender a fundo sobre algoritmos de ciência de dados.

Neste post, vamos levá-lo através das diferentes estruturas de dados e algoritmos de classificação. Mas primeiro, vamos entender o que é um algoritmo de ordenação e ordenação na estrutura de dados.

O que é um algoritmo de ordenação?

Um algoritmo de ordenação é apenas uma série de ordens ou instruções. Neste, uma matriz é uma entrada, na qual o algoritmo de classificação executa operações para fornecer uma matriz classificada.

Muitas crianças teriam aprendido a classificar estruturas de dados em suas aulas de ciência da computação. Ele é introduzido em um estágio inicial para ajudar as crianças interessadas a ter uma ideia de tópicos mais profundos de ciência da computação – métodos de divisão e conquista, árvores binárias, pilhas, etc.

Aqui está um exemplo do que a classificação faz.

Vamos supor que você tenha um array de strings: [h,j,k,i,n,m,o,l]

Agora, a classificação produziria uma matriz de saída em ordem alfabética.

Saída: [h,i,j,k,l,m,n,o]

Vamos aprender mais sobre classificação na estrutura de dados.

Checkout: Tipos de Árvore Binária

Classificando categorias

Existem duas categorias diferentes na classificação:

• Ordenação interna : Se os dados de entrada são tais que podem ser ajustados na memória principal de uma só vez, é chamado de ordenação interna.
• Classificação externa : Se os dados de entrada não puderem ser ajustados na memória de uma só vez, eles precisam ser armazenados em um disco rígido, disquete ou qualquer outro dispositivo de armazenamento. Isso é chamado de classificação externa.

Leia: Ideias e tópicos interessantes de projetos de estrutura de dados

Tipos de classificação na estrutura de dados

Aqui estão alguns dos tipos mais comuns de algoritmos de classificação.

1. Mesclar Ordenação

Este algoritmo funciona dividindo um array em duas metades de tamanhos comparáveis. Cada metade é então classificada e mesclada novamente usando a função merge().

Veja como o algoritmo funciona:

MergeSort(arr[], l, r)

Se r > l

1. Divida a matriz em duas metades iguais, localizando o ponto médio:

meio m = (l+r)/2

2. Use a função mergeSort para chamar a primeira metade:

Chame mergeSort(arr, l, m)

3. Chame mergeSort para a segunda metade:

Chame mergeSort(arr, m+1, r)

4. Use a função merge() para mesclar as duas metades classificadas nas etapas 2 e 3:

Chamar mesclagem (arr, l, m, r)

Confira a imagem abaixo para ter uma ideia clara de como isso funciona.

Fonte

Programa Python para implementação de classificação de mesclagem

def mergeSort(a):

se len(a) > 1:

mid = len(a)//2

A = a[:meio]

B = a[meio:]

merge Sort(A)

mergeSort(B)

i = j = k = 0

enquanto i < len(A) e j < len(B):

se A[i] < B[j]:

a[k] = A[i]

i+=1

outro:

a[k] = B[j]

j+=1

k+=1

enquanto i < len(A):

a[k] = A[i]

i+=1

k+=1

enquanto j < len(R):

a[k] = B[j]

j+=1

k+=1

def printLista(a):

para i no intervalo(len(a)):

print(a[i],fim=” “)

imprimir()

if __name__ == '__main__':

a = [12, 11, 13, 5, 6, 7]

mergeSort(a)

print(“O array ordenado é: “, end=”\n”)

printLista(a)

Saiba mais: Recursão na estrutura de dados: como funciona, tipos e quando usado

2. Ordenação por Seleção

Neste, a princípio, o menor elemento é enviado para a primeira posição.

Em seguida, o próximo menor elemento é pesquisado no array restante e é colocado na segunda posição. Isso continua até que o algoritmo atinja o elemento final e o coloque na posição correta.

Observe a imagem abaixo para entender melhor.

Fonte

Programa Python para implementação de ordenação por seleção

sistema de importação

X = [6, 25, 10, 28, 11]

para i no intervalo(len(X)):

min_idx = eu

para j no intervalo(i+1, len(X)):

se X[min_idx] > X[j]:

min_idx = j

X[i], X[min_idx] = X[min_idx], X[i]

print ("O array ordenado é")

para i no intervalo(len(X)):

print("%d" %X[i]),

Certificação avançada em ciência de dados, mais de 250 parceiros de contratação, mais de 300 horas de aprendizado, 0% EMI

3. Ordenação por Bolha

É o mais fácil e simples de todos os algoritmos de ordenação. Ele funciona com o princípio de trocar repetidamente elementos adjacentes caso eles não estejam na ordem correta.

Em termos mais simples, se a entrada for classificada em ordem crescente, a classificação por bolha primeiro comparará os dois primeiros elementos da matriz. Caso o segundo seja menor que o primeiro, ele trocará os dois e passará para o próximo elemento, e assim sucessivamente.

Exemplo :

Entrada : 637124

Primeira passagem

63 7124 -> 36 7124 : Bubble sort compara 6 e 3 e os troca porque 3<6.

3 67 124 -> 3 67 124 : Desde 6<7, sem troca

36 71 24 -> 36 17 24 : Trocado 7 e 1, como 7>1

361 72 4 -> 361 27 4 : Trocado 2 e 7, como 2<7

3612 74 -> 3612 47 : Trocado 4 e 7, como 4<7

Segunda passagem

36 1247 -> 36 1247

3 61 274 -> 3 16 274

31 62 74 -> 31 26 74

312 67 4 -> 312 67 4

3126 74 -> 3126 47

Terceiro passe

31 2647 -> 13 2647

1 32 647 -> 1 23 647

12 36 47 -> 12 36 47

123 64 7 -> 123 46 7

1234 67 -> 1234 67

Como você pode ver, obtemos o resultado da ordem crescente após três passagens.

Programa Python para implementação de classificação de bolhas

def bolhaSort(a):

n = len(a)

para i no intervalo(n):

para j no intervalo (0, ni-1):

se a[j] > a[j+1] :

a[j], a[j+1] = a[j+1], a[j]

a = [64, 34, 25, 12, 22, 11, 90]

bolhaClassificar(a)

print (“O array ordenado é:”)

para i no intervalo(len(a)):

print (“%d” %a[i]),

Leia também: Data Frames em Python: Tutorial detalhado de Python

Conclusão

Isso encerra a classificação na estrutura de dados e os algoritmos de classificação mais comuns. Você pode escolher qualquer um dos diferentes tipos de algoritmos de classificação. No entanto, lembre-se de que alguns deles podem ser um pouco tediosos para escrever o programa. Mas então, eles podem ser úteis para resultados rápidos. Por outro lado, se você deseja classificar grandes conjuntos de dados, deve escolher a classificação por bolha. Não só produz resultados precisos, mas também é fácil de implementar. Então, novamente, é mais lento do que os outros tipos. Espero que você tenha gostado do artigo sobre classificação na estrutura de dados.

Para obter mais informações sobre como a classificação funciona, entre em contato conosco e ajudaremos você a começar no curso que melhor atende às suas necessidades!

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.

Divirta-se codificando!