Sortiranje niza??

Sortiranje niza?? 04.06.2003. u 03:05 · pre 285 meseci #1

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)

Re: Sortiranje niza?? 19.06.2003. u 18:36 · pre 284 meseca #2

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.

Potpis

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Re: Sortiranje niza?? 19.06.2003. u 19:32 · pre 284 meseca #3

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 $2^n$
— broj $i$ treba upariti sa brojem $2^n-i+1$
— sve parove $(i, 2^n-i+1)$ za koje je $i=2k,\,k\in N$ izdvojimo u jedan niz, a ostale u drugi
— svaki od ova dva niza posmatramo zasebno, i damo im indekse od 1 do $2^{n-1}$ , i ponovimo postupak uzimanjem za $n:=n-1$ na svaki od ova dva niza

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

Potpis

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

Re: Sortiranje niza?? 20.06.2003. u 22:02 · pre 284 meseca #4

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 $2^n$ tenisera u turniru. "Najpravednije" bi bilo da u prvom kolu 1. nosilac igra sa poslednjim, 2. sa pretposlednjim, ... ( $i$ protiv $2^n - i + 1$ ). Dalje, u drugom kolu, pod pretpostavkom da "favoriti" prođu, parovi bi bili $i$ protiv $2^{n-1} - i + 1$ (pod onim "favoriti prođu" sam mislio da igrači od $2^{n-1} + 1$ do $2^n$ 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.

Re: Sortiranje niza?? 22.06.2003. u 23:17 · pre 284 meseca #5

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

Re: Sortiranje niza?? 23.06.2003. u 00:52 · pre 284 meseca #6

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)

sort.jpg11k

Re: Sortiranje niza?? 23.06.2003. u 05:59 · pre 284 meseca #7

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?

Re: Sortiranje niza?? 23.06.2003. u 18:40 · pre 284 meseca #8

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.

Re: Sortiranje niza?? 23.06.2003. u 19:17 · pre 284 meseca #9

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).

Re: Sortiranje niza?? 23.06.2003. u 22:38 · pre 284 meseca #10

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

Re: Sortiranje niza?? 26.06.2003. u 00:16 · pre 284 meseca #11

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;
}

Re: Sortiranje niza?? 28.06.2003. u 01:52 · pre 284 meseca #12

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.

Forum kao aplikacija na telefonu

Srodne teme