sortowanie z 5 "ifami"

0

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

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
  1. porównujesz dwie pierwsze liczby i robisz swap() jeśli konieczny
  2. porównujesz dwie ostatnie liczby i robisz swap() jeśli konieczny
  3. 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
  4. porównujesz znów dwie ostatnie liczby i robisz swap() jeśli konieczny
  5. 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 ;)

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