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