A classificação de listas de dados é uma parte crucial do processamento em aplicativos.
É útil para exibir dados e realizar pesquisas. Portanto, não é surpresa que qualquer bom engenheiro de software saiba como classificar arrays. Este artigo explica alguns dos algoritmos mais comuns para classificação de arrays em JavaScript.
últimas postagens
O que é classificação e por que ela é útil?
Fonte: Remover respingo
Classificação é a organização sistemática de valores por alguma ordem. Esta ordem pode ser decrescente ou ascendente. Classificar arrays em JavaScript é útil porque permite que os dados sejam exibidos de forma mais significativa.
Por exemplo, uma pessoa pode querer ver os arquivos classificados primeiro com os arquivos mais recentes ou os produtos classificados por preço. Também é útil para realizar pesquisas binárias em dados, que só funcionam com dados classificados.
Embora existam funções e bibliotecas para ajudá-lo a classificar dados facilmente, você ainda precisa saber como a classificação funciona nos bastidores para entrevistas de codificação ou quando precisar escrever código de baixo nível.
Algoritmos de classificação de array JavaScript
Tipo de bolha
Bubble Sort é sem dúvida o algoritmo mais fácil de entender e implementar. Ele funciona percorrendo o array em uma passagem. A cada passagem, percorremos o array, do início ao fim, comparando dois elementos adjacentes. Se os elementos estiverem na ordem errada, nós os trocamos.
Realizamos n passagens onde n é o número de elementos no array. A cada passagem, o array é classificado começando da direita. O pseudocódigo do algoritmo para classificar os números em ordem crescente é o seguinte:
1. Let n be the number of elements in the array 2. Loop n times, keeping count of the loops using i (doing the following in each loop) a. loop the array from the second element to the (n - i)th element b. if the previous element is greater than the current element, swap them.
Traduzindo para JavaScript, o código ficaria assim:
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
Para entender melhor o que está acontecendo, recomendo adicionar console.logs dentro dos dois loops para ver como a matriz muda a cada passagem.
No código abaixo, modifiquei a função sort para adicionar console.logs dentro dos dois loops. Também criei um pequeno array não classificado que classifiquei usando a função sort.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
console.log(`Pass: ${i}`);
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
console.log(arr);
}
}
return arr;
}
const array = [9, 2, 7, 4, 1];
sort(array);
console.log(array);
O resultado da execução do código acima seria:
A classificação por bolha tem uma complexidade de tempo Big O de O (n ^ 2). Isso ocorre porque ele executa n passagens, que percorrem a matriz para cada passagem. Portanto, não é bem dimensionado. No entanto, tem uma complexidade de espaço de O(1), uma vez que modifica os elementos do array no local.
Classificação de inserção
A classificação por inserção é um algoritmo popular de classificação de array JavaScript. Suponha que estejamos usando a classificação por inserção para classificar os valores em ordem crescente. O algoritmo funciona escolhendo um número, que chamaremos de num. Em seguida, ele move num para a esquerda até que todos os outros números à esquerda de num sejam menores que num. Todos os números serão ordenados se isso for feito do segundo elemento até o final. Aqui está uma descrição em pseudocódigo.
1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
a. Set currentElement to array[i]
b. Set j to i - 1
c. While j >= 0 and array[j] > current_element
i. Move array[j] to array[j+1]
ii. Decrement j by 1
d. Set array[j+1] to current_element
E agora, o pseudocódigo implementado em JavaScript é o seguinte.
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
}
return array;
}
Assim como acontece com o Bubble Sort, adicionar console.logs ajuda a visualizar o que está acontecendo. O trecho de código abaixo mostra a classificação por inserção em funcionamento.
function sort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
console.log("Placing element:", currentElement);
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
console.log("Placed it at position:", j + 1);
console.log(array);
}
return array;
}
const array = [4, 1, 2, 5, 3];
sort(array);
E executar o trecho acima produz o seguinte resultado:
Mesclar classificação
Enquanto a classificação por inserção e a classificação por bolha são dimensionadas em tempo quadrático, a classificação por mesclagem é dimensionada em tempo quase linear. Tem uma complexidade de tempo de O(n * log(n)).
A classificação por mesclagem utiliza a estratégia de dividir para conquistar. A matriz é repetidamente dividida em matrizes menores de 1 elemento cada. Após a divisão, eles são mesclados novamente.
A divisão é recursiva para que o array possa ser remontado posteriormente.
Ao mesclar a matriz novamente, as submatrizes são mescladas em ordem. A mesclagem é feita da mesma maneira que você mesclaria um array classificado. O pseudocódigo para fazer isso está escrito abaixo:
1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
b. Create rightArray and copy the second half of the array into it (from index mid+1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
a. Create an empty resultArray
b. While both leftArray and rightArray are not empty:
i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
ii. Otherwise, append the first element in rightArray to resultArray
c. Append any remaining elements in leftArray to resultArray (if any)
d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray
Implementá-lo em JavaScript resultaria no seguinte:
function sort(array) {
// Base case in which we stop subdividing the array
if (array.length == 1) {
return array;
}
// Finding the middle point of the array
const m = Math.round(array.length / 2);
// Divide the array into two halves
const leftUnsorted = array.slice(0, m);
const rightUnsorted = array.slice(m);
// Recursively call merge sort
const leftSorted = sort(leftUnsorted);
const rightSorted = sort(rightUnsorted);
// Return a merged sorted array
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
// Merge two sorted lists
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
Se você executar o código com um array de exemplo, ele deverá funcionar.
Ordenação rápida
Assim como o Merge Sort, o Quick Sort depende da estratégia de dividir para conquistar. O algoritmo seleciona um elemento pivô. Em seguida, ele move todos os elementos maiores que o pivô para a direita e menores que o pivô para a esquerda. Feito isso, o pivô estará na posição correta.
Para mover elementos ao redor do pivô, o algoritmo começa movendo o pivô para o final da matriz.
Depois de movê-lo, usamos um ponteiro para fazer um loop a partir da esquerda do array, procurando o primeiro número maior que o pivô. Simultaneamente, usamos outro loop de ponteiro à direita do array, procurando o primeiro número menor que o pivô. Depois que os dois números forem identificados, nós os trocamos. Este procedimento é repetido até que o ponteiro da esquerda seja maior que o ponteiro da direita.
Quando paramos, trocamos o maior dos dois últimos números trocados pelo pivô. Neste ponto, o pivô estará na posição correta; os números menores que o pivô estarão à esquerda, enquanto os maiores estarão à direita.
Este procedimento é repetido recursivamente para as submatrizes à esquerda e à direita do pivô até que as submatrizes tenham apenas um elemento restante.
Aqui está o pseudocódigo para classificação rápida:
1. If lessThanPointer is less than greaterThanPointer:
a. Choose a pivot element from the array
b. Move elements such that elements less are to the left and elements greater are to the right:
c. Recursively call Quicksort on leftSubarray
d. Recursively call Quicksort on rightSubarray
E convertendo para JavaScript:
function sort(array, low, high) {
if (low < high) {
// Choose the pivot index and partition the array
const pivotIndex = move(array, low, high);
// Recursively sort the subarrays to the left and right of the pivot
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
}
function move(array, low, high) {
// Select the pivot element (in this case, the last element)
const pivotElement = array[high];
// Initialize the index for the smaller element
let i = low - 1;
for (let j = low; j < high; j++) {
// If the current element is less than or equal to the pivot, swap it with the element at index i+1
if (array[j] <= pivotElement) {
i += 1;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element into its correct position
const temp = array[i];
array[i] = array[j];
array[j] = temp;
// Return the index of the pivot element
return i + 1;
}
A classificação de um array de exemplo com Quick Sort em Node.js deve resultar no seguinte:
Na melhor das hipóteses, o Quicksort é executado em complexidade de tempo quase linear. O uso de espaço na classificação rápida também é dimensionado logaritmicamente. Portanto, é relativamente eficiente em comparação com outros algoritmos de classificação de array JavaScript.
Dicas para suas entrevistas de codificação
❇️ A prática é fundamental. Ajuda você a aprender diferentes algoritmos, mas, mais importante, ajuda a desenvolver habilidades de resolução de problemas e pensamento computacional. Você também pode praticar em plataformas como Código Leet e AlgoExpert.
❇️ Tente resolver o problema primeiro. Em vez de ir direto para a solução, tente resolvê-la, pois isso ajuda você a desenvolver suas habilidades de resolução de problemas.
❇️ Se um problema estiver demorando muito, vá direto para a solução; você ainda pode aprender a resolver o problema a partir da solução. A maioria das plataformas de aprendizagem oferece soluções. ChatGPT ou Google Bard também são úteis para explicar conceitos.
❇️ Além disso, não escreva código imediatamente; coloque suas soluções no quadro branco e pense nelas antes de escrever o código. O pseudocódigo também é uma forma útil de anotar ideias rapidamente.
Conclusão
Neste artigo, cobrimos os algoritmos de classificação mais populares. No entanto, aprender tudo isso pode parecer complicado no início. Portanto, geralmente recomendo misturar várias fontes em vez de depender apenas de uma. Boa codificação!
A seguir, confira como entender a função classificada em Python.