Sorting an “almost sorted” array in sub linear time
-
03-11-2019 - |
Pergunta
I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array in sublinear time asymptotically.
My proof is to suppose a sorted array of length $n$. Now assume that every second element is swapped with the element on its left. The new array is almost sorted. To sort it would require a minimum of $n/2$ swaps - asymptotically linear amount of operations. Therefore, no sublinear sorting algorithm exists.
Is this proof correct?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange