Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Mali problem oko sortiranja

[es] :: Art of Programming :: Mali problem oko sortiranja

[ Pregleda: 3325 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stf

Član broj: 51276
Poruke: 65
*.150.EUnet.yu.



Profil

icon Mali problem oko sortiranja01.06.2005. u 11:53 - pre 235 meseci
Problem se sastoji u sledecem: Najpre se ucitava broj n, broj tacaka u ravni. Zatim se svaka tacka ucitava svojim koordinatama x i y. Napisati proceduru koja tacke sortira s leva na desno. Ukoliko mozete opisite algoritam kojim se to postize ili mi ostavite kod u Pascalu. Valjalo bi da algoritam ima vremensku slozenost N log N, ukoliko je moguce. Hvala!
If you don't live for something, you will die for nothing.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 12:02 - pre 235 meseci
Pa ne vidim sta je problem, jedino sto treba da uradis je da sortiras tacke po x koordinati ?

Ako ne znas kako da sortiras niz, pogledaj TOP temu

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

vladab
Vladimir Bašanović
Beograd

Član broj: 9512
Poruke: 498
*.etf.bg.ac.yu.



Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 12:19 - pre 235 meseci
Citat:
stf: ...Valjalo bi da algoritam ima vremensku slozenost N log N, ukoliko je moguce. Hvala!

Pogledaj malo quick sort, mislim da on ima tu slozenost.
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.186.eunet.yu.



Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 12:44 - pre 235 meseci
Da, procedura quicksort. OK! Kako sad da svaku y koordinatu vezem za x koordinatu. Ako clanovi niza x zamene mesta, kako da u toj proceduri ubacim da se za svaku promenu niza x na taj nacin menja i niz y?
If you don't live for something, you will die for nothing.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 13:32 - pre 235 meseci
Pa na svakom mestu gde zamenjujes x [ i ] i x [ j ] zamenis i y [ i ] i y [ j ].

Ali mnogo je elegantnije da napravis strukturu "tacka", koja ce da ima dve promenljive - x i y, pa ce to biti tacka [ i ].x i tacka [ i ].y. Onda jednostavno uporedjujes x-ove, a kad vrsis zamenu zamenjujes celu strukturu tacka.

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.142.eunet.yu.



Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 18:46 - pre 235 meseci
Ne znam da operisem sa slogovnim tipom podatka. Moram malo da proucim proceduru quicksort, pa da znam tacno na kom se mestu zamenjuju konkretno vrednosti x-eva, pa tu da promenim y-e. Sve ovo sto ste rekli znao sam, ocigledno lako je. Ako mozete napisite code (u Pascalu) kako izmeniti tu proceduru u skladu sa tim, ako ne, pozabavicu se sam. Hvala u svakom slucaju.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 19:26 - pre 235 meseci
evo ti citat iz examples is turbo pascala:
Code:
{************************************************}
{                                                }
{ QuickSort Demo                                 }
{ Copyright (c) 1985,90 by Borland International }
{                                                }
{************************************************}

program QSort;
{$R-,S-}
uses Crt;

{ This program demonstrates the quicksort algorithm, which      }
{ provides an extremely efficient method of sorting arrays in   }
{ memory. The program generates a list of 1000 random numbers   }
{ between 0 and 29999, and then sorts them using the QUICKSORT  }
{ procedure. Finally, the sorted list is output on the screen.  }
{ Note that stack and range checks are turned off (through the  }
{ compiler directive above) to optimize execution speed.        }

const
  Max = 1000;

type
  List = array[1..Max] of Integer;

var
  Data: List;
  I: Integer;

{ QUICKSORT sorts elements in the array A with indices between  }
{ LO and HI (both inclusive). Note that the QUICKSORT proce-    }
{ dure provides only an "interface" to the program. The actual  }
{ processing takes place in the SORT procedure, which executes  }
{ itself recursively.                                           }

procedure QuickSort(var A: List; Lo, Hi: Integer);

procedure Sort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i] < x do i := i + 1;
    while x < a[j] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin {QuickSort};
  Sort(Lo,Hi);
end;

begin {QSort}
  Write('Now generating 1000 random numbers...');
  Randomize;
  for i := 1 to Max do Data[i] := Random(30000);
  Writeln;
  Write('Now sorting random numbers...');
  QuickSort(Data, 1, Max);
  Writeln;
  for i := 1 to 1000 do Write(Data[i]:8);
end.


da ne bi sad menjao, neka je a [ i ] ustvari x koordinata.
na mestu gde pise
Code:
y := a[i]; a[i] := a[j]; a[j] := y;

treba dodati jos jedan red:
Code:
y := b[i]; b[i] := b[j]; b[j] := y;

ako b [ i ] predstavlja y koordinatu.

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.147.EUnet.yu.



Profil

icon Re: Mali problem oko sortiranja01.06.2005. u 19:49 - pre 235 meseci
Hvala ti puno!!! To mi je trebalo.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

Toyo

Član broj: 45193
Poruke: 227
*.kovnet.co.yu.



+1 Profil

icon Re: Mali problem oko sortiranja02.06.2005. u 03:20 - pre 235 meseci
He he.... Pa nisi znao nista. Dao ti je samo QS - sto si mogao da nadjes na 1000 sajtova. :)
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.149.EUnet.yu.



Profil

icon Re: Mali problem oko sortiranja02.06.2005. u 08:15 - pre 235 meseci
Fora je u tome sto ne poznjem dobro quicksort, pa nisam znao gde da ubacim da kad menja jedan niz, menja i drugi. Sad sam to proanalizirao i pomoglo mi je da optimalnije resim brdo zadataka.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

[es] :: Art of Programming :: Mali problem oko sortiranja

[ Pregleda: 3325 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.