[es] - Sortiranje niza??

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

^{04.06.2003. u 02:05 - pre 261 meseci}

Ovako,problem je sortirati niz koji se sastoji od integer vrednosti,koje su poredjane po velicini pocev od 1 pa do nekog broja(1,2,3,4,5,...).Stvar je u tome sto je taj niz potrebno sortirati tako da njegovi elementi budu poredjani u redosledu koji je identican nacinu kako se rasporedjuju takmicari za neki teniski turnir.Neophodno je da niz bude dimenzija stepena broja dva(8,16,32,...) a ako ima manje takmicara onda se nadopunjuje nulama do najveceg stepena(ako je prijavljeno 12 takmicara recimo nadopunjujemo do 16 sa 4 nule).
(pr:ako ima 16 takmicara onda je niz sledeceg izgleda:
1-15,7-11,3-13,5-9,2-16,8-12,4-14,6-10(treba primetiti da su u prvoj polovini niza uvek neparni a u drugoj uvek parni brojevi)
pr za 8 elemenata:
1-7,3-5,2-8,4-6
radim u DELPHI-ju ali je bilo kakva pomoc dobrodosla(koristim i C/C++ ,JAVA)

Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.racasse.se

Sajt: dejan.lekic.org

+2 Profil

Re: Sortiranje niza??

^{19.06.2003. u 17:36 - pre 261 meseci}

Stvar koju ne razumem je - kako takav niz treba da bude sortiran? Daj primer nesortiranog niza (nazovimo ga ulazni niz) i sortiranog niza (izlazni niz), pa ćemo malo prodiskutovati kako to da se odradi... Pascal ne koristim godinama, tako da ću sa svoje strane pomoći i dati primere u C/C++/JAVA/PHP.
P.S. preferiram prva dva.

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beograd-3.tehnicom.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Sortiranje niza??

^{19.06.2003. u 18:32 - pre 261 meseci}

Leko, čini mi se da se ovde ne radi o nizu u smislu memorijske strukture, već prosto o nizu brojeva od 1 do 2ⁿ.

Ono što ja ne razumem ovde je kako se vrši to „tenisko sortiranje“, tj. to što su u prvom delu parni, a u drugom neparni brojevi meni ne govori zašto bi trebalo 7-11 da dođe pre 3-13.

Ono što pretpostavljam da treba uraditi je sledeće:
— imamo brojeve od 1 do

— broj

treba upariti sa brojem

— sve parove

za koje je

izdvojimo u jedan niz, a ostale u drugi
— svaki od ova dva niza posmatramo zasebno, i damo im indekse od 1 do

, i ponovimo postupak uzimanjem za

na svaki od ova dva niza

Ako ovo nije tačan postupak, onda treba malo konkretizovati o čemu se radi.

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: Sortiranje niza??

^{20.06.2003. u 21:02 - pre 261 meseci}

Mogao bi ja (kao bivši teniser) da objasnim kako ide to "tenisko sortiranje". Ako me sećanje dobro služi, onda onaj primer koji je dao Ajvan i nije baš najbolji. Naime, pretpostavimo da imamo

tenisera u turniru. "Najpravednije" bi bilo da u prvom kolu 1. nosilac igra sa poslednjim, 2. sa pretposlednjim, ... (

protiv

). Dalje, u drugom kolu, pod pretpostavkom da "favoriti" prođu, parovi bi bili

protiv

(pod onim "favoriti prođu" sam mislio da igrači od

izgube). Dalje ide analogno.
Pretpostavljam da je sad malo jasnija situacija.
Evo kako bi glavni "žreb" na turniru sa 8 igrača trebao da izgleda na osnovu toga:
1
8
5
4
3
6
7
2
Ovo znači da su u prvom kolu parovi 1-8, 5-4, 3-6, 7-2; u drugom kolu se sastaju pobednici iz prva dva meča i pobednici iz druga dva meča; i naravno, u poslednjem kolu (finalu) se sastaju pobednici iz mečeva drugog kola. (formira se stablo od dna ka vrhu)

E sad, po nekoj logici, verovatno se zadatak sastoji u tome da se za zadat broj igrača napravi ovakav niz.

Ako sam pogodio ono što se traži, mogu poslati i kod koji bi to trebao da radi.

Odgovor na temu

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

Re: Sortiranje niza??

^{22.06.2003. u 22:17 - pre 261 meseci}

Ljudi,nisam ja izmislio to sortiranje.
Radim za diplomski aplikaciju koja treba da automatizuje karate takmicenje,odnosno formiranje zrebnih lista.Ljudi koji organizuju takmicenje sortiraju takmicare po toj semi.
Dakle jos jedanput:
imam niz integer vrednosti:
1,2,3,,,16 (ili do 32 ili do bilo kog stepena dvojke)Znaci ako se za neku disciplinu prijavi recimo 12 takmicara ja do 16 dopunjujem nule pa ce prva cetvorica imati slobodno prvo kolo.
Sort moze da se izvede preko binarnog stabla odgovarajucom pretragom i ja sam krenuo u takvu realizaciju ali sada sam nesto zauzet pa sam stao.

znaci ovako prijavilo se 12 takmicara recimo:
oni inicijalno dobijaju takmicarske brojeve u zavisnosti od bodova osvojenih na predhodnim takmicenjima tako:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 su redni brojevi u zrebnoj listi

1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 ali ima samo 12 prijavljenih pa tako:

evo kako idu neparni:
1
1 3

1 7 3 5

1 15 7 11 3 13 5 9

ovako bi izgledalo stablo za neparne

Odgovor na temu

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

Re: Sortiranje niza??

^{22.06.2003. u 23:52 - pre 261 meseci}

ovako,nalupao sam predhodnu poruku jer mi je bila neka guzva,
sad cu malo da pojasnim:
prijavilo se recimo 32 takmicara.Oni nose redne brojeve od 1 do 32
Rasporedjujem parne na jednu a neparne na drugu stranu:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 i
ovako,nalupao sam predhodnu poruku jer mi je bila neka guzva,
sad cu malo da pojasnim:
prijavilo se recimo 32 takmicara.Oni nose redne brojeve od 1 do 32
Rasporedjujem parne na jednu a neparne na drugu stranu:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 i
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 to su mi dva odvojena niza
meni je u sustini bitno da sortiram samo jedan od njih recimo neparni
a parni posle ide po istoj semi.Tako imam
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
sad ide ukrstanje:
1 kao najboljeg u ovoj polovini rasporedjujem za nosioca jedne polovine
kostura a 3 kao drugog najboljeg rasporedjujem u drugu polovinu
neparnog dela kostura:
1 3
Onda uzimam 5 i njega postavljam da ide na 3 a 7 postavljam da ide na 1

(ako bih imao samo 8 takmicara to bi znacilo da su 4 neparna pa najgori
neparni ide na najboljeg neparnog a drugi najgori neparni na drugog
najboljeg neparnog,treba napraviti semu koja se moze preslikati na
bilo koji broj takmicara koji je naravno stepen broja 2)

1 7 5 3
ako se prati binarno stablo najlakse se moze razumeti:
1

1 3 (4 takmicara od kojih su 2 neparna)

1 7 5 3 (8 takmicara od kojih su 4 neparna)

1 15 7 11 9 5 13 3 (16 takmicara - 8 neparnih)

1 31 15 23 27 7 11 19 17 9 5 25 21 13 29 3 (32 tak. - 16 neparnih)

Prikačeni fajlovi

sort.jpg - 11k

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: Sortiranje niza??

^{23.06.2003. u 04:59 - pre 261 meseci}

Moram priznati da i dalje ne kontam logiku soritanja niza. Evo, za početak, kaži mi samo zašto se sastaju 7-11 i 5-9. Drugim rečima, zar 5. igrač (kao bolji od 7.) ne bi trebao da dobije "lakšeg" protivnika, to jest 11. igrača?
Dalje, zašto je toliko bitno da se odvoje neparni od parnih? Ako bi krenuo logikom da igraju 1-3 i 2-4, zar ne bi bilo logično da onda u neparnoj polovini igraju 1-5 i 3-7 (ili u parnoj polovini 2-6 i 4-8) - mislim na odgovarajuće runde?

Odgovor na temu

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

Re: Sortiranje niza??

^{23.06.2003. u 17:40 - pre 261 meseci}

Prijatelju,odvajanje parnih od neparnih kao sto sam ranije rekao nisam ja izmislio,ti si 100 % u pravu ali se tako trazi i ja ne mogu tu nista da menjam.Jednostavno ljudi iz karate saveza to tako rade godinama i nemaju nameru da tu nesto menjaju.
U vezi drugog dela tvog pitanja:
nema logike da u neparnoj polovini igraju 1 i 5 a 3 i 7 (ako je 8 ukupno takmicara a od toga 4 neparna) jer najbolji neparni uvek mora da ide na najgoreg neparnog (sta bi se desilo da se prijavi samo 6 takmicara - onda bih morao da uzmem model 8 i onda bi u prvom kolu najbolji tj. prvi morao da se bori a 3 bi pauzirao to kolo,to bas nema smisla).
Prvo tvoje pitanje ,zasto 7 ide na 11.Pa treba pogledati binarno stablo: 1 i 3(govorim o neparnom kosturu) idu 1 uvek u levu granu a treci uvek u desnu granu stabla i obojica se propagiraju do kraja tako.Sledeci tj. 5 ide u levu granu desnog dela a 7 u desnu granu levog dela.Njih dvojica(5 i 7) se onda propagiraju do dna stabla naizmenicno jednom desno pa jednom levo.zapravo se interval uvek polovi,malo mi je tesko ovako da ti objasnim,ja sam sam sebi iscrtao pola sveske i jos uvek nisam uspeo da napravim sort kako valja.Profesor insistira da to bude neka dinamicka struktura (stablo).Pokusacu da vizuelno to interpretiram pa da postavim u svakom slucaju hvala na trudu svih vas koji pokusavate da mmi pomognete.
U jednoj od predhodnih mojih poruka ima zakacena slika gde sam probao da predstavim stablo,pa prati kako se dodaju elementi kako se ide u dubinu.

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: Sortiranje niza??

^{23.06.2003. u 18:17 - pre 261 meseci}

U redu.
Znači ovaj izgled žreba nisi sam konstruisao, već oni to stvarno tako postavljaju (mislim na karatiste). Ono što je meni opet čudno je to da ako se prijavi 10 igrača, onda bi 007 (koji bi po tvom trebao da igra sa 11.) bio slobodan u prvom kolu, za razliku od 5. koji je po svemu sudeći bolji od njega (pa mu se na taj način čini "nepravda", pošto će po svemu sudeći dobiti batina u prvom kolu).

Odgovor na temu

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

Re: Sortiranje niza??

^{23.06.2003. u 21:38 - pre 261 meseci}

Da u pravu si 5 ide na 9 pa se bori u prvom kolu a 7 pauzira ali zato u sledecem kolu ide na prvog a peti na 3 pa 7 bas i nije dobro prosao

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: Sortiranje niza??

^{25.06.2003. u 23:16 - pre 261 meseci}

Evo, ja sam pokušao da nadjem neku pravilnost u onom tvom objašnjenju. Da li sam uspeo - ne znam. Poteraj ovaj kod, pa proveri da li je to ono što ti treba.

Code:

#include <stdio.h>

#define MAX_IGRACA 128

unsigned int moj_log_2(unsigned int n);
unsigned int moj_pow_2(unsigned int n);

int main(void) {
  unsigned int broj_igraca, i, j, k, log_2, razmak, velicina_niza;
  unsigned int redni_broj_igraca[MAX_IGRACA+1], raspored_igraca[MAX_IGRACA+1];
  unsigned int pozicija_veceg, pozicija_manjeg;

  printf("Unesi broj igraca na turniru: ");
  scanf("%d", &broj_igraca);

  // najmanje 2^n vece ili jednako broju igraca
  velicina_niza = moj_pow_2(moj_log_2(broj_igraca - 1));

  redni_broj_igraca[1] = 1;
  redni_broj_igraca[3] = velicina_niza >> 1;
  log_2 = moj_log_2(velicina_niza) - 1;
  for (i = 3; i <= log_2; i++) {
    pozicija_veceg = moj_pow_2(i - 1) + 1;
    razmak = moj_pow_2(log_2 - i);
    for (j = moj_pow_2(i - 2); j > 1; j >>= 1) {
      pozicija_manjeg = j + 1;
      for (k = 0; k < j >> 1; k++) {
        if (((pozicija_veceg - 1) >> 1) & 0x01)
          redni_broj_igraca[pozicija_veceg] = redni_broj_igraca[pozicija_manjeg] + razmak;
        else
          redni_broj_igraca[pozicija_veceg] = redni_broj_igraca[pozicija_manjeg] - razmak;
        pozicija_veceg += 2;
        pozicija_manjeg += 2;
      }
    }
    redni_broj_igraca[pozicija_veceg] = redni_broj_igraca[1] + razmak;
  }

  for (i = 1; i <= velicina_niza >> 1; i++)
    redni_broj_igraca[i << 1] = redni_broj_igraca[(i << 1) - 1] + (velicina_niza >> 1);
  for (i = 1; i <= velicina_niza; i++)
    raspored_igraca[redni_broj_igraca[i]] = i;
  for (i = 1; i <= velicina_niza; i++)
    if (raspored_igraca[i] > broj_igraca)
      printf("0\n");
    else
      printf("%d\n", raspored_igraca[i]);
  return 0;
}

unsigned int moj_log_2(unsigned int n) {
  unsigned int log_2 = 0;

  while (n > 0) {
    n >>= 1;
    log_2++;
  }
  return log_2;
}

unsigned int moj_pow_2(unsigned int n) {
  unsigned int pow_2 = 1;

  while (n-- > 0)
    pow_2 <<= 1;
  return pow_2;
}

Odgovor na temu

Ajvan
Ivan Jovanovic
Novi Sad

Član broj: 10783
Poruke: 71
*.ftn.ns.ac.yu

Profil

Re: Sortiranje niza??

^{28.06.2003. u 00:52 - pre 261 meseci}

Prijatelju proverio sam na brzaka to sto si poslao i izgleda da je to to,nisam jos siguran jer sad radim nesto drugo ali ovo mi je vrlo bitno,u svakom slucaju ti hvala na trudu,kad ga budem prebacio u DELPHI i testirao u potpunosti javicu sta je bilo.

Odgovor na temu