jak napisac algorytm sortujacy 4 liczby, bez uzycia rekurencji, ani bez iteracji, dostepne sa tylko "if" oraz "zamien", tak by ilosc porownan byla w najgorszym wypadku nie wieksza, niz 5?
0
0
wymyslilem cos takiego:
if a>b
zamien a i b
if c>d
zamien c i d
if a>c
zamien a i c
if b>d
zamien b i d
moje pytanie, czy to juz wszystkie porownania, czy jeszcze czegos brakuje?
0
- porównujesz dwie pierwsze liczby i robisz swap() jeśli konieczny
- porównujesz dwie ostatnie liczby i robisz swap() jeśli konieczny
- porównujesz dwie środkowe liczby i robisz swap() jeśli konieczny
jeśli w kroku 3 nie bylo potrzeby swapa() to koniec, jeśli swap nastąpił to - porównujesz znów dwie ostatnie liczby i robisz swap() jeśli konieczny
- porównujesz znów dwie pierwsze liczby i robisz swap() jeśli konieczny
0
jeszcze trzeba dopisac:
if b>c
zamien b i c
czy to dziala tak jak powinno w kazdym wypadku?
0
dzieki, ale ten Twoj algorytm na moje oko nie zadziala dla tablicy
4 3 2 1
wyjdzie
3 1 2 4
0
po tej poprawce teraz wyjdzie 1 2 4 3
spojrz na ta moja wersje z ta dopiska, ona chyba dziala poprawnie, jak uwazasz?
0
Mój bląd ;)
powinno być tak:
if(tab[0] > tab[1]) //pierwsza para
swap(tab[0],tab[1]);
if(tab[2] > tab[3]) //druga para
swap(tab[2],tab[3]);
if(tab[0] > tab[2]) //pierwsze elementy pierwszej i drugiej pary
swap(tab[0],tab[2]);
if(tab[1] > tab[3]) //drugie elementy pierwszej i drugiej pary
swap(tab[1],tab[3]);
if(tab[1] > tab[2]) //drugi element pierwszej pary i pierwszy element drugiej pary
swap(tab[1],tab[2]);
Dowód że działa:
#include <iostream>
#include <algorithm>
using namespace std;
void sortuj(int* tab);
int main()
{
int tab[] = {1,2,3,4};
int tab2[] = {1,2,3,4};
do {
sortuj(tab);
for(int i=0;i<4;i++)
tab[i]=tab2[i];
} while (next_permutation(tab2,tab2+4));
return 0;
}
void sortuj(int* tab)
{
if(tab[0] > tab[1])
swap(tab[0],tab[1]);
if(tab[2] > tab[3])
swap(tab[2],tab[3]);
if(tab[0] > tab[2])
swap(tab[0],tab[2]);
if(tab[1] > tab[3])
swap(tab[1],tab[3]);
if(tab[1] > tab[2])
swap(tab[1],tab[2]);
for(int i=0;i<4;i++)
cout<<tab[i]<<" ";
cout<<endl;
}
0
ok, dzieki,
PS. To jest dokladnie to co ja napisalem wyzej, nie trzeba bylo kodzic, wystarczylo potwierdzic ;)