Mam za zadanie napisać w schemacie blokowym, algorytm sortujący 5 liczb, w maksymalnie 7 porównaniach. Zabrałem się za to, ale kompletnie mi to nie wychodzi. Jakieś sugestie?
0
0
Tutaj jest rozwiązanie tego problemu:
https://cs.stackexchange.com/questions/44981/least-number-of-comparisons-needed-to-sort-order-5-elements
a tutaj mój pseudokod, dzięki drobnej sztuczce wygląda znacznie przyjemniej od tego z linka, swoją drogą fajne zadanie na rekrutację :)
// sortujemy pierwssza pare - 1
if (a > b) swap (a, b)
// sortujemy druga pare - 1
if (c > d) swap (c, d)
// sportujemy pary wzgledem siebie - 1
if (b > d) swap (a, c) swap (b, d)
// wstawiamy e pomiedzy a b d - 2
swap(c, d) // sztuczka ktora nam ulatwi zycie
procedure Foo()
{
if (e < b)
{
if(e < a)
{ // e idzie na pierwsza pozycje [e, a, b, d , c] <- numeracja z przed sztuczki
swap (d,e)
swap (c,d)
swap (c,b)
swap (b,a)
}else
{ // na druga [a, e, b, d, c] <- numeracja z przed sztuczki
swap (d,e)
swap (c,d)
swap (c,b)
}
}else
{
if(e < d)
{ // na trzecia [a, b, e, d, c] <- numeracja z przed sztuczki
swap (d,e)
swap (c,d)
}else
{ // na czwarta [a, b, d , e, c] <- numeracja z przed sztuczki
swap (d,e)
}
}
}
Foo();
// no i teraz pozostało nam wstawic c z przed sztuczki, ktore obecnie znaduje sie na ostatniej pozycji czyli e
// dzieki sztuczce i temu ze c < d (sprzed sztuczki) sprowadza sie to do ponownego wywołania prodecury Foo która wstawia e pomiedzy pierwsze trzy elementy
Foo();