Olá, tentei resolver o problema abaixo por 5 horas, mas não consegui encontrar a resposta. O título desta pergunta é "Classificação em Linear", então presumo que a resposta ideal deva ter complexidade de tempo O(n). A pergunta está escrita abaixo.
===================================================
Você tem um array de n inteiros originalmente ordenado em ordem crescente. No entanto, até ⌊√n/2⌋ trocas arbitrárias foram feitas entre pares de elementos no array. Consequentemente, no máximo √n elementos podem estar fora de suas posições corretas. Você deve reordenar este array em ordem crescente usando um algoritmo com a menor complexidade de tempo possível.
===================================================
O que descobri até agora é que, se você conseguir encontrar quais elementos estão na posição errada em O(n), a ordenação em si também deve assumir O(n). Mas não sei mais o que fazer :(
Algoritmo LinearSort(A):
n ← length(A)
misplacedIndices ← empty set
// Step 1: Identify indices of potentially misplaced elements
misplacedIndices.add(i) // Do this somehow(!!!!)
// sort indices in ascending order -> takes O(√n · log(√n))
misplacedIndices ← sorted(misplacedIndices)
// Step 2: Separate misplaced elements from correctly placed ones
misplacedList ← empty list
remainderList ← empty list
for i ← 0 to n - 1 do:
if i ∈ misplacedIndices then:
misplacedList.append(A[i])
else:
remainderList.append(A[i])
end for
// Sort the misplaced elements (only up to O(√n) elements)
sort(misplacedList) // Time complexity: O(√n · log√n)
// Step 3: Merge the two sorted lists (remainderList and misplacedList)
result ← empty list
i ← 0, j ← 0
while i < length(remainderList) and j < length(misplacedList) do:
if remainderList[i] ≤ misplacedList[j] then:
result.append(remainderList[i])
i ← i + 1
else:
result.append(misplacedList[j])
j ← j + 1
end while
// Append any remaining elements from either list
while i < length(remainderList) do:
result.append(remainderList[i])
i ← i + 1
end while
while j < length(misplacedList) do:
result.append(misplacedList[j])
j ← j + 1
end while
return result
Itere pelo array. Sempre que a[i] > a[i+1], mova ambos para um array separado. Isso é feito em n passos. O array separado tem tamanho máximo de 2 sqrt n. Você o classifica em O(2 sqrt n log sqrt n) = O(n) passos e, em seguida, o mescla no array original em mais O(n) passos.
O número total de operações é, na verdade, O(n) se até O(n / log n) elementos estiverem no lugar errado, o que é muito maior que O(sqrt n). Por exemplo, para um milhão de elementos, você pode lidar com 50.000 itens no lugar errado, não apenas 1.000.
Acredito que um algoritmo bem simples será suficiente e será O(n) devido às propriedades do array:
Corte a matriz entre os elementos que estão fora de ordem (a[i] > a[i+1]). Isso resulta em um máximo de sequências ordenadas por sqrt(n) + 1.
Classifique as sequências pelo primeiro número.
Crie uma matriz de resultados.
Continue inserindo a partir da primeira sequência até que seu elemento atual seja maior que o primeiro elemento (ou seja, atual) da segunda sequência.
Insira a primeira sequência na posição correta para que as sequências sejam ordenadas novamente pelo seu elemento atual. Se a lista de sequências for armazenada em um heap mínimo (elemento atual como chave), isso requer O(log(sqrt(n))) = O(log(n)), mas uma simples inserção em uma lista O(sqrt(n)) também será suficiente para O(n) no geral.
Continue em 4. até que todos os elementos sejam inseridos (e todas as subsequências consumidas).
Por que é O(n)? Como apenas elementos sqrt(n) podem estar fora do lugar, temos que executar o passo 5 no máximo 2 * sqrt(n) vezes e O(sqrt(n) * log(n)) < O(n) porque O(log(n)) < O(sqrt(n)) e, portanto, O(n) = O(sqrt(n) * sqrt(n)) > O(sqrt(n) * log(n)). E se usarmos um método simples O(sqrt(n)) no passo 5, obteremos O(n), mas isso é no total, então apenas a + O(n) e o algoritmo geral ainda é O(n).