[es] - Pitanje QuickSort da li je ovo uredu?

osmania
Panet

Član broj: 26316
Poruke: 773
*.20.11.vie.surfer.at.

+7 Profil

Pitanje QuickSort da li je ovo uredu?

^{09.10.2008. u 12:00 - pre 188 meseci}

ljudi ne mogu nikako da ga skontam, patim se pravo....

ali evo nesto sam skontao a zelio bi da mi kazete da li je ok ili nije ok...

2 8 7 6 20 2 5 4 30 je jedan niz

sredina je pivot= 20 (kako tacno sredinu uzimamo ovde kod neparnih nizova je ok ali kod parnih nizova imamo 2 5 1 3 sta je sredina 5 ili 1?)

prvi poredimo sa 20
2<20 ok
prvi sa zadnjim 2<30 ok
pivot sa zadnjim 20 < 30 ok
znaci nigdje nismo izvrsili zamijenu super.

pivot zamijenjivamo za prezadnjim 4kom
novi niz izgleda ovako

2 8 7 6 4 2 5 20 30

sada idemo od lijeva prema prema 20 trazimo najveci sa lijeve strane i najmanji sa desne strane.
Sta me ovde buni: 2<20 ok, 8<20 ok, 6< 20 ok, jel tu stajemo (kao to je ta lijeva strana ili idemo sve do 20 posto nismo nasli ni jedan veci od dvadeset da bi ga mjenjali)
A sa druge strane sta me buni na desnoj strani su svi manji od 20 sta sa njima....

Moje misljenje je da prvo trazimo najveci od 20 ako nema ostaje niz takav kakav je. a u nasem slucaju 2 8 7 6 4 2 5 20 30

pa pet pozovemo QS za niz (2 8 7 6 4 2 5) onda sve ponovo
pivot sreina pivot = 6
2<6 ok, 2<5 ok 6<5 ne zamijenimo izgleda ovako 2 8 7 5 4 2 6, i sada mijenjamo sredinu (jel to nas novi pivot=5 ili?) 5 sa prezadnjim 2 i onda imamo novi niz 2 8 7 2 4 5 6

trazimo sa lijeve starne veci od 5
2<5 ok 8<5 ne nasli smo 8 je veci
sa desna trazimo manji od 5 evo ga 4
8 i 4 zamijenimo i dobijemo niz: 2 4 7 2 8 5 6
trazimo dalje 7 je veci od 5 ok nasli smo na lijevoj strana
idemo sada desna strana trazimo manji i to je 2
znaci 7 i 2 zamijenimo.
i imamo novi niz: 2 4 2 7 8 5 6

eh sada taj nas pivot = 5 mogu li zamijeniti sa 7 da dobijem taj niz u kojem je lijeva strana manja a desna veca.
a to bi izgledalo ovako 2 4 2 5 8 7 6

i onda uradim quicksort za (2 4 2) lijevu starnu pa onda za desnu stranu i spojim sve...
jel to pravilno ili nije.... sto sam sada uradio...

Problem je sto sam na netu nasao par vrsta sa malim oscilacijama

Mada ne znam kako bi poceo da je pivot na zadnjem mjestu, kako bi poredio pivot za zadnjim brojem sto sam ovde uradio i kako bi poredio prvi broj sa zadnjim?
skroz sam zbunjen sad stvarno nista ne znam

Hvala puno

Odgovor na temu

StefanJer91
Stefan Jeremic
Beograd

Član broj: 121923
Poruke: 160
*.static.ikomline.net.

Profil

Re: Pitanje QuickSort da li je ovo uredu?

^{09.10.2008. u 12:43 - pre 188 meseci}

Mislim da je na wikipediji na srpskom lepo objasnjeno kako qsort funkcionise sto mi se ne poklapa bas sa svim sto si ti rekao.

http://sr.wikipedia.org/wiki/%...%D0%BA%D1%81%D0%BE%D1%80%D1%82

The earth teaches us more about ourselves than all the books. Because it resists us. Man discovers himself when he measures himself against the obstacle.

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
87.250.42.57

+1064 Profil

Re: Pitanje QuickSort da li je ovo uredu?

^{09.10.2008. u 20:46 - pre 188 meseci}

Nesto sam se zezao sa quick sortom, pa je ispalo ovo.
No ne mogu da objasnim kako radi ako uopste radi ;)
Mislim po rezultatima radi, ali ne znam kako ;)

Code:

#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>
using namespace std;

template <typename T>
inline bool operator<=(T l,T r)
{
  return !(r < l);
}
template <typename T>
inline bool operator>=(T l,T r)
{
  return !(l < r);
}

template <typename T>
void qsort(T begin, T end)
{
  if(begin == end)return;
  T low = begin, high = end;
  --high;
  do
  {
    while(high != low && *high>=*begin)--high;
    while(low != high && *low<=*begin)++low;
    swap(*low,*high);
  }while(low != high);
  swap(*low,*begin);
  qsort(begin,low);
  qsort(++low,end);
}

struct Test{
explicit Test(unsigned n = 0):a(n){}
bool operator==(const Test& r)const
{
  return a == r.a;
}
bool operator<(const Test& r)const
{
  return a<r.a;
}
unsigned a;
};

int main()
{
  srand(time(0));
  list<Test> l,l1;
  vector<Test> arr,arr1;
  for (unsigned i =0;i < 3000000; ++i)
  {
    Test tmp(rand());
    arr.push_back(tmp);
    l.push_back(tmp);
  }
  arr1 = arr;
  l1 = l;
  clock_t s,e, t1,t2,t3,t4;
  s = clock();
  qsort(arr.begin(),arr.end());
  e = clock();
  t1 = e-s;
  s = clock();
  sort(arr1.begin(),arr1.end());
  e = clock();
  t2 = e - s;
  s = clock();
  qsort(l.begin(),l.end());
  e = clock();
  t3 = e-s;
  s = clock();
  l1.sort();
  e = clock();
  t4 = e - s;
  if(arr==arr1)cout<<"true\n";
  else cout<<"false\n";
  if(l==l1)cout<<"true\n";
  else cout<<"false\n";
  cout
       <<"qsort:"
       <<((double)t1/CLOCKS_PER_SEC)
       <<"\nsort:"
       <<((double)t2/CLOCKS_PER_SEC)
       <<"\nlqsort:"
       <<((double)t3/CLOCKS_PER_SEC)
       <<"\nlsort:"
       <<((double)t4/CLOCKS_PER_SEC)
       <<'\n';
}

A ovaj sort iz g++ liba kosirsti neke zesce optimizacije izgleda jer je znatno brzi.
Medjutim ovaj moj moze da se primeni i na liste posto ne zahteva random access
iterator i tu vec radi brze od merge sorta koji se verovatno koristi za liste
tako da moze da posluzi.

output:
bmaxa@maxa:~$ ./qsort
true
true
qsort:0.27
sort:0.21
lqsort:0.37
lsort:1.16

Pozdrav!

Odgovor na temu

karas

Član broj: 5574
Poruke: 482
62.189.100.*

+1 Profil

Re: Pitanje QuickSort da li je ovo uredu?

^{10.10.2008. u 08:44 - pre 188 meseci}

Ajde da probam sa pseudo kodom mislim da je lakse tako. Neka se sortiraju elementi niza a[n]. Nazovimo pivotom element niza takav da su svi elementi levo od njega manji od njega, a desno od njega veci.
Funkcija partition() deli niz a[n] na dva dela tako sto elemente manje od pivota smesta levo od njega, a elemente vece od pivota desno. Za pivot je ovde uzet levi element, detalje o izboru pivota potrazi na netu (hint: "srednji od tri"). partition() vraca poziciju unutar niza elementa koji je uzet za pivot kada se zavrsi sa ovom podelom. Dakle, partition() ide kroz niz (unutrasnje petlje idu jedna sleva a druga zdesna) i premesta elemente tako da su svi levo manji od pivota a veci desno od njega. Kada se mimoidju, zavrsice se i spoljna petlja. Posle zavrsetka petlji, svi elementi su smesteni kako treba, osim sto je element na koji pokazuje i manji od elementa na koji pokazuje pivot. Zato se uradi jos jedna zamena tih elemenata. Tada su svi elementi levo od i-tog manji a desno od i-tog veci od njega.

Code:

partition(left, right)
    i = left; j = right; pivot = i;
    while i <= j
    {
        while a[i] <= a[pivot] and i <= r
            i = i + 1;
        while a[j] > a[pivot] and j >= l
            j = j - 1;
        if i < j
            swap(i; j);
    }
    swap(i; pivot);
    return i;

sort() nalazi pivot, kako su elementi levo od pivota manji od njega, a desni od pivota veci, treba samo rekurzivno sortirati prvi i drugi deo niza jer se pivot vec nalazi na svom mestu.

Code:

sort(left, right)
    if left < right
    {
        p = partition(left, right);
        sort(left, p - 1);
        sort(p + 1, right);
    }

Sveti Avgustin: "Dobar hrišćanin treba da se kloni matematičara i svih onih koji daju lažna proročanstva. Postoji opasnost da su matematičari već sklopili pakt sa Đavolom, da pomrače čovekov um i da ga okuju okovima pakla."

Odgovor na temu