[Algorytmy] Ustawianie elementów przed sortowaniem

[kasia523]

Wektorem przesunięć dla pewnego algorytmu sortowania S (sortujemy liczby rosnąco) i tablicy liczb rzeczywistych \(\displaystyle{ T = \left\{ t_{1},t_{2}, ..., t_{n} \right\}}\) będziemy nazywać \(\displaystyle{ W = \left\{ w_{1},w_{2}, ..., w_{n} \right\}}\) gdzie \(\displaystyle{ w_{i}}\) to liczba określająca ile liczb większych od \(\displaystyle{ i}\) znajduje się na lewo od niej znajduje się w początkowym ustawieniu liczb tablicy T.

Przykład: \(\displaystyle{ T= \left\{ 5,6,3,2,1 \right\}}\) \(\displaystyle{ \to}\) \(\displaystyle{ W= \left\{ 0,0,2,3,4 \right\}}\)

Zakładając że znasz W i kształt tablicy T po sortowaniu napisz algorytm wyznaczający ustawienie elementów przed sortowaniem.

O jaki algorytm tutaj chodzi?

[Afish]

Dostajesz posortowaną tablicę \(\displaystyle{ T'}\) oraz tablicę \(\displaystyle{ W}\) i masz wyliczyć oryginalną tablicę \(\displaystyle{ T}\).

[pawellogrd]

Zrobiłaś błąd w opisie: napisałaś, że \(\displaystyle{ w_i}\) to liczba określająca ile liczb większych od \(\displaystyle{ i}\) znajduje się na lewo od niej w początkowym ustawieniu liczb tablicy \(\displaystyle{ T}\), a z tego przykładu, który dałaś jasno wynika, że \(\displaystyle{ w_i}\) to liczba określająca ile liczb większych od \(\displaystyle{ t_i}\) (a nie \(\displaystyle{ i}\)) znajduje się na lewo od niej w początkowym ustawieniu liczb tablicy \(\displaystyle{ T}\)

Bazując na tym przykładzie, po posortowaniu otrzymasz: \(\displaystyle{ T'= \left\{ 1,2,3,5,6 \right\}}\). Wiedząc, że \(\displaystyle{ W= \left\{ 0,0,2,3,4 \right\}}\) możesz zacząć odtwarzać tablicę przed posortowaniem. Utwórz tablicę \(\displaystyle{ T}\), której początkowo nadaj wartość dokładnie taką jak \(\displaystyle{ T'}\) czyli na początku niech \(\displaystyle{ T=T'}\). Dalej niech \(\displaystyle{ i=5}\) (czyli równe rozmiarowi tablicy). Wtedy sprawdzasz wartość \(\displaystyle{ w_i}\). W tym przypadku wynosi \(\displaystyle{ 4}\). Zatem znajdujesz liczbę, od której dokładnie cztery inne są większe. Będzie to \(\displaystyle{ 1}\). Niech \(\displaystyle{ j}\) oznacza pozycję, na której stoi ta liczba, zatem w tym przypadku \(\displaystyle{ j=1}\) (indeksuję od jedynki). Teraz zamień liczby stojące na pozycjach: \(\displaystyle{ i}\) oraz \(\displaystyle{ j}\) miejscami. Sprawdź czy tablica jest utworzona zgodnie z porządkiem nadanym przez \(\displaystyle{ W}\) - jeżeli wszystko się zgadza, zakończ działanie. W przeciwnym przypadku zmniejsz \(\displaystyle{ i}\) i powtórz te same czynności. Gdy dojdziesz do \(\displaystyle{ i=1}\), wykonasz czynności i sprawdzenie pokaże, że tablica nie jest jeszcze właściwie odtworzona, nadaj \(\displaystyle{ i}\) z powrotem wartosć początkową, tzn. \(\displaystyle{ i=5}\). Powtarzaj to wszystko dopóki tablica \(\displaystyle{ T}\) nie zawiera liczb ustawionych w porządku nadanym przez \(\displaystyle{ W}\). Kolejne kroki tego algorytmu dla Twojej przykładowej tablicy \(\displaystyle{ T}\) będą wyglądać zatem następująco:

0) \(\displaystyle{ T=\left[ 1,2,3,5,6 \right]}\)

1) dla \(\displaystyle{ i=5}\): \(\displaystyle{ T=\left[ 6,2,3,5,1 \right]}\)

2) dla \(\displaystyle{ i=4}\): \(\displaystyle{ T=\left[ 1,6,3,2,5 \right]}\)

3) dla \(\displaystyle{ i=3}\): \(\displaystyle{ T=\left[ 1,6,3,2,5 \right]}\)

4) dla \(\displaystyle{ i=2}\): \(\displaystyle{ T=\left[ 1,6,3,2,5 \right]}\)

5) dla \(\displaystyle{ i=1}\): \(\displaystyle{ T=\left[ 6,1,3,2,5 \right]}\)

6) dla \(\displaystyle{ i=5}\): \(\displaystyle{ T=\left[ 6,5,3,2,1 \right]}\)

7) dla \(\displaystyle{ i=4}\): \(\displaystyle{ T=\left[ 6,5,3,2,1 \right]}\)

8) dla \(\displaystyle{ i=3}\): \(\displaystyle{ T=\left[ 6,5,3,2,1 \right]}\)

9) dla \(\displaystyle{ i=2}\): \(\displaystyle{ T=\left[ 5,6,3,2,1 \right]}\)

Tablica \(\displaystyle{ T}\) jest uporządkowana zgodnie ze wskazaniami wektora \(\displaystyle{ W}\) zatem algorytm kończy działanie. Tablica \(\displaystyle{ T'}\) przed posortowaniem wyglądała jak tablica \(\displaystyle{ T}\).

[kasia523]

Stanęłam w kodzie na:

Sprawdź czy tablica jest utworzona zgodnie z porządkiem nadanym przez W - jeżeli wszystko się zgadza, zakończ działanie.

jak to napisać w kodzie?

[pawellogrd]

Weź tablicę T oraz porządek W. Wtedy dla każdego elementu tablicy T znajdź odpowiadający jej element porządku W (będzie miał ten sam indeks) i sprawdź czy na lewo od tego elementu znajduje się dokładnie tyle elementów większych, ile wskazuje porządek W. Nie wiem jakiego języka używasz, więc trudno mi podać tutaj konkretny kod.

[kkk123]

jaki bedzie zatem koszt tego algorytmu i dlaczego?

[pawellogrd]

Trudno tutaj jednoznacznie go podać (tzn. uśredniony), bo zależy on od tego jaka była początkowa postać tablicy \(\displaystyle{ T}\). Optymistyczny przypadek to przypadek, gdy tablica przed posortowaniem była posortowana czyli w tej samej postaci. Wtedy algorytm jedyne co zdąży zrobić, to sprawdzić, że wszystko jest ok, dla każdego elementu o indeksie \(\displaystyle{ i}\) trzeba wykonać \(\displaystyle{ i-1}\) sprawdzeń czyli łącznie dla tablicy n-elementowej wykonanych zostanie sprawdzeń \(\displaystyle{ 1+2+3+...+\left( n-1\right) =\frac{n\left( n-1\right) }{2}}\) sprawdzeń, więc przyjmując liczbę sprawdzeń za miarę złożoności to będzie \(\displaystyle{ O\left(\frac{n\left( n-1\right) }{ 2}\right) \approx O(n^2)}\) w przypadku optymistycznym, gdzie złożoność kwadratowa czyli to przybliżenie będzie dobre dla dużych wartości \(\displaystyle{ n}\).

Przypadek pesymistyczny - nie jestem pewien, ale wydaje mi się, że będzie \(\displaystyle{ n}\) cykli wykonanych, w każdym \(\displaystyle{ n}\) weryfikacji czy tablica jest już odtworzona w pełni poprawnie, wtedy złożoność pesymistycznym należy przemnożyć przez \(\displaystyle{ n \cdot n = n^2}\), więc wynosiłaby ona \(\displaystyle{ O\left(\frac{n^3\left( n-1\right) }{ 2} \right)\approx O(n^4)}\), gdzie znów złożoność przybliżona jest dla dużych \(\displaystyle{ n}\)