Forum » Programiranje » Quick sort
Quick sort
Microsoft ::
V šoli mamo eno nalogo, ko mormo ene elemente, ki so v polju, razvrstit s to metodo. neki sm gledal po netu, pa mi stvar ni bla najbol jasna... Neki vem, da se gre v tem, da se stvar menda na začetku razdeli na polovico, pol polovica spet na polovico, pa tako naprej.. Sm iz tega si neč ne morem pomagt, sploh nevem, če je prav.
Drgače pa je bla predhodna naloga, da isti problem rešmo z bubble načinom. To mi je ratal...
Sm tale quick sort mi pa ni jasn. Mi ga lahk kdo saj malo razloži,d a bom saj v osnovi vedel, kaj dela?
LP
by Miha
Drgače pa je bla predhodna naloga, da isti problem rešmo z bubble načinom. To mi je ratal...
Sm tale quick sort mi pa ni jasn. Mi ga lahk kdo saj malo razloži,d a bom saj v osnovi vedel, kaj dela?
LP
by Miha
s8eqaWrumatu*h-+r5wre3$ev_pheNeyut#VUbraS@e2$u5ESwE67&uhukuCh3pr
user4683 ::
Včasih pomaga, če navedeš kateri jezik uporabljaš. No, ampak algoritmi so itak univerzalni.
Pa včasih ne škodi, če malce pobrskaš po netu (nekdo je nekoč nekje rekel, da bi v šoli, pri informatiki ali biločem, mogli najprej naučit kako se išče stvari. Strinjam se!).
eh ja
Pa včasih ne škodi, če malce pobrskaš po netu (nekdo je nekoč nekje rekel, da bi v šoli, pri informatiki ali biločem, mogli najprej naučit kako se išče stvari. Strinjam se!).
eh ja
Ripp ::
procedure QuickSort; (* sortiranje s premenami - rekurzivno *)
procedure Sort (l,r: index);
var i,j: index;
x,w: item;
begin
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while a[i].key < x.key do
i := i + 1;
while x.key < a[j].key do
j := j - 1;
if i <= j then
begin
w := a[i];
a[i] := a[j];
a[j] := w;
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
sort(1,n);
end;
procedure Sort (l,r: index);
var i,j: index;
x,w: item;
begin
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while a[i].key < x.key do
i := i + 1;
while x.key < a[j].key do
j := j - 1;
if i <= j then
begin
w := a[i];
a[i] := a[j];
a[j] := w;
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
sort(1,n);
end;
(Maniac) ::
Quick sort deluje na principu "divide-and-conquer" strategije.
Opis delovajna "osnovne" verzije Quick sorta:
(1) Najprej si na tabeli (0,n) izberemo neko cifro x (pivot) (ponavadi na sredini tabele);
(2) nato iščemo iz leve (torej od 0 do x-1) toliko časa dokler ne najdemo cifre(recimo a), ki je večja od x-a.
(3) isto ponovimo na desni strani (od x+1 do n) -> iščemo toliko časa da ne naletimo na cifro(recimo b), ki je manjša od x.
(4) zamenjamo a in b.
(5) ponavljamo toliko časa korak 2,3,4 da se obe pregledovanji ne srečata sredi tabele.
____________________pivot
primer:____________/
osnovni array:___8 7 2 6 1
quicksort:______ 8 7 2 6 1
quicksort:______1 2
quicksort:_________7 6 8
quicksort:___________7 8
sortirani array:__1 2 6 7 8
Opis delovajna "osnovne" verzije Quick sorta:
(1) Najprej si na tabeli (0,n) izberemo neko cifro x (pivot) (ponavadi na sredini tabele);
(2) nato iščemo iz leve (torej od 0 do x-1) toliko časa dokler ne najdemo cifre(recimo a), ki je večja od x-a.
(3) isto ponovimo na desni strani (od x+1 do n) -> iščemo toliko časa da ne naletimo na cifro(recimo b), ki je manjša od x.
(4) zamenjamo a in b.
(5) ponavljamo toliko časa korak 2,3,4 da se obe pregledovanji ne srečata sredi tabele.
____________________pivot
primer:____________/
osnovni array:___8 7 2 6 1
quicksort:______ 8 7 2 6 1
quicksort:______1 2
quicksort:_________7 6 8
quicksort:___________7 8
sortirani array:__1 2 6 7 8
Zgodovina sprememb…
- spremenil: (Maniac) ()
Microsoft ::
Zdele mal študiram kak bi naredu, pa sm že tud mal probal, sam mi še ni ratal.
Me pa neki zanima. Ko te številke začne program delit na večje in manjše od neke vrednosti. A to dela tako dolgo, da pol ostane v vsaki particiji samo ena vrednost?
Primer:
1: 22354
2: 223 54
3: 22 3 54
REcimo, zdej ej iz prvega v drug korak to razdelilo na števila manjša od 4 in na števila enaka al pa večja od 4. Kak nej zdej program ve, da je v drugem koraku spodnji del že prav razvrščen? Da mu pol ne bi blo treba belat še tretji korak za spodnjo particijo?
by Miha
p.s.: Pa uporablam C++ (devcpp).
Me pa neki zanima. Ko te številke začne program delit na večje in manjše od neke vrednosti. A to dela tako dolgo, da pol ostane v vsaki particiji samo ena vrednost?
Primer:
1: 22354
2: 223 54
3: 22 3 54
REcimo, zdej ej iz prvega v drug korak to razdelilo na števila manjša od 4 in na števila enaka al pa večja od 4. Kak nej zdej program ve, da je v drugem koraku spodnji del že prav razvrščen? Da mu pol ne bi blo treba belat še tretji korak za spodnjo particijo?
by Miha
p.s.: Pa uporablam C++ (devcpp).
s8eqaWrumatu*h-+r5wre3$ev_pheNeyut#VUbraS@e2$u5ESwE67&uhukuCh3pr
Zgodovina sprememb…
- spremenil: Microsoft ()
marjan_h ::
Pri algoritmu quicksort sem prebral na wikipediji da ima časovno zahtevnost n*log(n). Zanima me če je ta logaritem z osnovo 2?
Ker algoritem pač razdeli polje na dva dela, in to ponavlja rekurzivno.
Hvala za odgovore.
Ker algoritem pač razdeli polje na dva dela, in to ponavlja rekurzivno.
Hvala za odgovore.
drola ::
Logaritmi z različnimi osnovami se med sabo razlikujejo za konstantni faktor, zato v O(...) notaciji osnova logaritma sploh ni pomembna.
Element na sredini izbereš, če pišeš korake algoritma na tablo. Sicer pa se ponavadi izbira naključen element. Če izbiraš srednjega, lahko potencialni napadalec na tvoj sistem izbere take podatke, da bo quick-sort delal O(n^2) primerjav, kajti O(n*logn) je za quick-sort povprečna časovna zahtevnost in ne časovna zahtevnost v najslabšem primeru. Povprečno časovno zahtevnost pa dosežeš v principu z naključno izbiro pivota. Druga opcija je pa, da podatke pred sortiranjem naključno premešaš in potem sortiraš s pivotom na sredini.
Najbolj tipični primeri takih napadov so sicer na zgoščenih tabelah.
(1) Najprej si na tabeli (0,n) izberemo neko cifro x (pivot) (ponavadi na sredini tabele);
Element na sredini izbereš, če pišeš korake algoritma na tablo. Sicer pa se ponavadi izbira naključen element. Če izbiraš srednjega, lahko potencialni napadalec na tvoj sistem izbere take podatke, da bo quick-sort delal O(n^2) primerjav, kajti O(n*logn) je za quick-sort povprečna časovna zahtevnost in ne časovna zahtevnost v najslabšem primeru. Povprečno časovno zahtevnost pa dosežeš v principu z naključno izbiro pivota. Druga opcija je pa, da podatke pred sortiranjem naključno premešaš in potem sortiraš s pivotom na sredini.
Najbolj tipični primeri takih napadov so sicer na zgoščenih tabelah.
https://drola.si
Zgodovina sprememb…
- spremenil: drola ()
marjan_h ::
Ja, če se razlikuje za konstantni faktor potem v O notaciji nima veze. Kaj pa če bi imelo vezo? Bi potem bil z osnovo 2, tako kot sem rekel?
drola ::
Analiza.
Osnova 2 bi bila za idealne vhodne podatke, ko se ti vsakem koraku problem prepolovi. Odvisno od tega kako srečo imaš z izbiranjem pivota. V najslabšem primeru se ti pa potem dogaja, da vedno deliš problem na 1 element + vse ostale, pri čemer potem končaš z O(n^2).
Osnova 2 bi bila za idealne vhodne podatke, ko se ti vsakem koraku problem prepolovi. Odvisno od tega kako srečo imaš z izbiranjem pivota. V najslabšem primeru se ti pa potem dogaja, da vedno deliš problem na 1 element + vse ostale, pri čemer potem končaš z O(n^2).
https://drola.si
Zgodovina sprememb…
- spremenil: drola ()
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )Oddelek: Znanost in tehnologija | 75764 (25933) | pietro |
| » | Quick sort ascending/descendingOddelek: Programiranje | 2050 (1730) | infiniteLoop |
| » | It means business (strani: 1 2 3 4 5 6 7 8 )Oddelek: Znanost in tehnologija | 28377 (14376) | Thomas |
| » | [Turbo Pascal] Pomoč...Oddelek: Programiranje | 1477 (1379) | Grey |
| » | sortirni algoritem v CjuOddelek: Programiranje | 1447 (1299) | GaPe |