QuickSort bez porownywania?

Witam! Zadanie które dostałem na kursie i po 7 godzinach ani krok do przodu. Wszelkie wskazówki mile widziane!

Preview of README.md
Question
Suppose that on your computer you have stored n password-protected files, each with a unique password. You’ve written down all of these n passwords, but you do not know which password unlocks which file. You’ve put these files into an array F and their passwords into an array P in an arbitrary order (so P[i] does not necessarily unlock F[i]).

If you test password P[i] on file F[j], one of three things will happen:

1. P[i] unlocks F[j].
2. The computer tells you that P[i] is lexicographically smaller than F[j]’s true password.
3. The computer tells you that P[i] is lexicographically greater than F[j]’s true password.

You cannot test whether a password is lexicographically smaller or greater than another password, and you cannot test whether a file’s password is lexicographically smaller or greater than another file’s password.

Design an algorithm to match each file to its password, which runs in expected runtime O(n log(n)).
Hint: Modify QuickSort to solve this question.

Czasem nie binary search?

https://www.geeksforgeeks.org/binary-search/
https://en.wikipedia.org/wiki/Binary_search_algorithm

tez mi to w pierwszej kolejnosci przyszlo do glowy, ale bez hasel posortowanych alfabetycznie nie da rady, a jak posortowac nie porownujac ich ?

one of three things will happen:

To mi mówi/sugeruje, że dane już są posortowane

"Czarna skrzynka" robi Binary Search i odpowiada:
Bingo! Trafiony zatopiony
Za mało
Za dużo

niestety nie sa posortowane, do test unitow jest random generator i shuffler :(

Posortować hasła leksykograficznie.
Iterując o plikach zrobić binarny serach po hasłach.

o_O A gdzie jest problem? Przecież to jest klasyczny quicksort tylko że pivotem jest F[i]. Bierzesz sobie hasła, "porównujesz je z F[i]" (tzn próbujesz otworzyć F[i]) i przekładasz na 2 strony -> mniejsze od pivota, większe od pivota. Niczym sie to szczególnie nie różni od normalnego quicksorta, tam przecież też porównujesz z jakimś pivotem a nie elementy między sobą. Samą wartość "pivota" też musisz znaleźć bo będzie wśród liczb.

edit: może czegoś nie widzę tutaj, ale na pierwszy rzut oka tu się nic specjalnego nie dzieje.

Sortować Quick
Wybierasz pivot
Czy wybrany pivot jest hasłem? Bingo!
Pivot jest mniejszy/większy? To zajmujesz się za odpowiednią partycję
n logn

Myślę, że jest pewien haczyk. Mamy dwie nieposortowane tablice, więc trzeba obie partycjonować. Jeśli wybierzemy za pivot P[i] i znajdziemy odpowiadający mu F[j] to robimy dwa partycjonowania:

• partycjonujemy P za pomocą F[j]
• partycjonujemy F za pomocą P[i]

Z warunków zadania wynika, że oba partycjonowania zakończą się dokładnie takim samym stosunkiem rozmiarów partycji i będzie można tradycyjnie zejść do tych partycji rekurencyjnie.

PS: pomysł totalnie niesprawdzony, ale obiecujący :)

no ale pivot tez bedzie haslem? wydawalo mi sie ze to by lamalo zastrzezenie o nie porownywaniu
You cannot test whether a password is lexicographically smaller or greater than another password, and you cannot test whether a file’s password is lexicographically smaller or greater than another file’s password.

@Wibowit:

QuickSort worst case to O(n^2) ale chyba nie o to tu chodzi?

Hint: Modify QuickSort to solve this question.

Oczywiście, że nie. 2 * O(n) = O(n). Nie ma znaczenia ile razy skanujesz tablicę w jednym poziomie wywołania QuickSort, dopóki ta liczba jest ograniczona stałą.

@BraVolt: Ale tam napisali "in expected time O(n log(n))", więc żadnej sprzeczności nie ma.