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?
[Algorytmy] Ustawianie elementów przed sortowaniem
[Algorytmy] Ustawianie elementów przed sortowaniem
Ostatnio zmieniony 16 lis 2012, o 22:52 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Ustawianie elementów przed sortowaniem
Dostajesz posortowaną tablicę \(\displaystyle{ T'}\) oraz tablicę \(\displaystyle{ W}\) i masz wyliczyć oryginalną tablicę \(\displaystyle{ T}\).
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[ALGORYTMY] ustawianie elementów przed sortowaniem
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}\).
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}\).
[Algorytmy] Ustawianie elementów przed sortowaniem
Stanęłam w kodzie na:
jak to napisać w kodzie?Sprawdź czy tablica jest utworzona zgodnie z porządkiem nadanym przez W - jeżeli wszystko się zgadza, zakończ działanie.
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Algorytmy] Ustawianie elementów przed sortowaniem
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.
-
- Użytkownik
- Posty: 31
- Rejestracja: 28 lis 2011, o 13:54
- Płeć: Mężczyzna
- Lokalizacja: wwa
- Podziękował: 4 razy
[Algorytmy] Ustawianie elementów przed sortowaniem
jaki bedzie zatem koszt tego algorytmu i dlaczego?
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Algorytmy] Ustawianie elementów przed sortowaniem
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}\)
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}\)