» »

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

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;

Thomas ::

Man muss immer generalisieren - Carl Jacobi

hasek ::

mogoce je boljse ce uporabis bubble sort je malo lazji za razumet za zacetnika

(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

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).
s8eqaWrumatu*h-+r5wre3$ev_pheNeyut#VUbraS@e2$u5ESwE67&uhukuCh3pr

Zgodovina sprememb…

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.

drola ::

Logaritmi z različnimi osnovami se med sabo razlikujejo za konstantni faktor, zato v O(...) notaciji osnova logaritma sploh ni pomembna.

(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).
https://drola.si

Zgodovina sprememb…

  • spremenil: drola ()


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Digitalna evolucija (strani: 1 2 3 426 27 28 29 )

Oddelek: Znanost in tehnologija
141672854 (23023) pietro
»

Quick sort ascending/descending

Oddelek: Programiranje
161875 (1555) infiniteLoop
»

It means business (strani: 1 2 3 4 5 6 7 8 )

Oddelek: Znanost in tehnologija
37426952 (12951) Thomas
»

[Turbo Pascal] Pomoč...

Oddelek: Programiranje
131363 (1265) Grey
»

sortirni algoritem v Cju

Oddelek: Programiranje
61339 (1191) GaPe

Več podobnih tem