Zadanie z sortowaniem bąbelkowym

Question

Przedszkolaki wyruszyły na spacer do parku. Grupa n osób ustawiła się przy wężu dość przypadkowo. Tymczasem Przedszkolanka - Pani Sylwia, preferuje aby osoby najniższe szły z przodu, a najwyższe z tyłu.

Porównuje więc stojących przedszkolaków parami (ostatni z przedostatnim, przedostatni z trzecim od końca, trzeci od końca z czwartym od końca itd) i jeśli to konieczne zamienia ich miejscami. Postępując w ten sposób przeszła od końca do początku grupy i spostrzegła, że grupa jeszcze nie jest jeszcze posortowana, więc postanowiła wykonać tę czynność jeszcze raz.

Napisz program, który wypisze ile minimalnie przejść musi wykonać Pani Sylwia, aby grupa została ustawiona w wymaganym porządku.

 

Wejście:

Pierwszy wiersz zawiera dwie liczby naturalne  n, k  (1 ≤ n, k ≤ 30 ) n - liczba przedszkolaków 

Drugi wiersz zawiera  n liczb naturalnych  ai  (0 ≤ ai ≤ 200 ) - wzrost kolejnych przedszkolaków.

Wyjście 

Pierwszy i jedyny wiersz wyjścia zawiera liczbę naturalną określającą ilość przejść Pani Przedszkolanki

Przykład:

Dla danych wejściowych:

10 
77 83 85 81 89 80 72 91 76 84

poprawną odpowiedzią jest:

5

Coś takiego mam, ale nie działa jak trzeba.

#include <iostream> #include <algorithm>

using namespace std;

int main() {int n,k=0;

cin>>n;

int T[30], t[30], t2[30];

for(int i=0;i<n;i++) { cin>>T[i]; }

for(int i=0;i<n;i++) { t[i]=T[i]; }

for(int i=0;i<n-1;i++) { for(int i=n-1;i>=0;i--) { if(T[i]<T[i-1]) { int pom=T[i]; T[i]=T[i-1]; T[i-1]=pom; } } }

for(int i=0;i<n;i++) { t2[i]=T[i]; }

while(!std::equal(t2, t2 + n, t))

{ for(int i=0;i<n-1;i++) { for(int i=n-1;i>=0;i--) { if(T[i]<T[i-1]) { int pom=T[i]; T[i]=T[i-1]; T[i-1]=pom; } } } k++; }

cout<<k;

return 0; }

Proszę o pomoc!

 

Comments

Nie wiem czy wyniku nie da się otrzymać szybciej, bez sortowania, ale jeśli już zdecydowałeś się na wykonanie tego sortowania i w międzyczasie policzenie tych przejść to je licz.

Trochę dziwnie teraz uczą. Mnie uczyli, że sortowanie bąbelkowe robi się w postaci dwóch pętli - zewnątrzna jest repeat-until (to było w Pascalu, w C będzie do-while), a wewnętrzna for. Ta zewnętrzna powtarza się aż w tej wewnętrznej nie dokona się żadna zamiana. Potrzebna jest więc flaga lub licznik, która jest zerowany na początku pętli zewnętrznej i ustawiana w trakcie każdej zamiany elementów w pętli wewnętrznej (jak licznik to inkrementowany). Całość kończy się jak wewnętrzna pętla zrobi "pusty przebieg" - tylko sprawdzający czy jest ok. Być może to będzie jedyny przebieg - gdyby tablica już była posortowana. W takiej implementacji od razu masz wynik - wystarczy tylko liczyć przebiegi zewnętrznej pętli.

W sumie w twoim kodzie widzę dwa razy pełne sortowanie w tym jedno w pętli - w jakim celu?

Wewnętrzne pętle są do 0 włącznie (i>=0) a wewnątrz odwołujesz się do elementu i-1 - a więc wychodzisz poza tablicę.

Trochę dziwne jest stosowanie tak samo nazwanej zmiennej w zagnieżdzonych pętlach - akurat tutaj chyba nie przeszkadza, bo ta zewnętrzna jest nie używana, ale dziwnie wygląda.

---

Zrobiłem to tak, bo kompletnie nie wiedziałem jak mam sprawdzić to kiedy są już posortowane i dalej nie wiem, bo nie znam się na tym aż tak bardzo i potrzebuję łopatologicznego wytłumaczenia na podstawie kodu, ale dziękuję za komentarz.

---

Staram się nie podawać gotowców, więc podam taki szkic kodu bez tych fragmentów które mialeś dobrze:

int przebieg = 0;
bool zamiana;

do
{
    zamiana = false;
    for (int i = n-1; i>0; i--)
    {
        if (T[i]<T[i-1])
        {
             [ zamiana elementow tablicy - bylo ok ]
             zamiana = true;
        }
    }
    przebieg++;
}
while (zamiana);   

cout << przebieg << endl;

W sumie raz wykonujesz takie sortowanie i masz wynik.

Oczywiście trzeba rozważyć jak się odnosi rzeczywistość do programu komputerowego. Nauczycielka nie musi robić pustego przebiegu - w treści jest "spostrzegła" - wieć jakby od razu widzi czy już jest dobrze - być może trzeba nie liczyć tego finałowego przebiegu programu i po prostu wyświetlić o jeden mniej.

Z drugiej strony w programie można wrócić na konieć jednym podstawieniem, a nauczycielka musi jednak tam pójść, nie teleportuje się. A wracająć może też wykonywać zamiany - czyli byłyby dwie pętle wewnętrzne - jedna w dół, jedna w górę. Akurat dla sortowania bąbelkowego kierunek tej pętli może znacząco wpłynąć na  czas wykonania (zależnie od danych).

---

Dziękuję za pomoc. Dla danych jednak daje wynik 6.

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int n,k=0;
cin>>n;
int T[30];
for(int i=0;i<n;i++)
{
	cin>>T[i];
}
int przebieg = 0;
bool zamiana;
 
do
{
    zamiana = false;
    for (int i = n-1; i>0; i--)
    {
        if (T[i]<T[i-1])
        {
             int pom=T[i];
			T[i]=T[i-1]; T[i-1]=pom;
             zamiana = true;
        }
    }
    przebieg++;
}
while (zamiana);   
 
cout << przebieg << endl;

	return 0;
}

 

---

Tak jak pisałem - program musi zrobić jeden pusty przebieg, człowiek spojrzy i już wie. Trzeba wypisać przebieg-1.

---

Tak zrobiłem i jest prawie wszystko dobrze gdyby nie to, że dla

5
70 70 70 70 70

powinno być 1 a przez to -1 daje na końcu 0. Może dać jakieś sprawdzenie czy wszystkie liczby w ciągu są równe i wtedy 1 wypisać a w innym wypadku tatmto co już było.

---

To nie jest przypadek wszystkich liczb równych, tylko ciągu już posortowanego. Zadanie jest trochę niejednoznaczne, zależy od tego odwzorowania rzeczywistości w postaci programu. Tten wynik masz podany w treści, czy sobie założyłeś? W treści jest napisane, że nauczycielka sprawdza jak jest na początku - raz przejść musi. Być może zamiast typowo używanej zmiennej należy użyć takiego sprawdzenia czy jest już posortowane realizowanego jako pętla. W sumie to jest trochę dziwne - skoro nauczycielka raz przeszła i nikogo nie przestawiła już nie musi sprawdzać/patrzeć.

---

Te liczby to jak po sprawdzeniu na stronie internetowej, takiej edukacyjnej w mojej szkole, jak wysłałem to pokazało, że takiego problemu program nie rozwiązał poprawnie. Jakoś sobie już z tym poradzę. Dziękuję Panu bardzo za poprowadzenie i pomoc w tym problemie.