Sortowanie 5 liczb

0

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

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();

1 użytkowników online, w tym zalogowanych: 0, gości: 1