Forum » Programiranje » [C++] Quick sort
[C++] Quick sort
black ice ::
S Quick sortom moram sortirati cca 1 000 000 števil. Približno razumem kako deluje to sortiranje - velik problem delimo na več manjših podproblemov oz. neko dolgo zaporedje razdelimo na več pod-zaporedij. V spodnji kodi me zeza to, da ne vem kako razbiti to polje. Dinamično ustvarim še eno polje, vendar kako prekopiram elemente od desnega indeksa naprej?
Do sedaj sem naredil samo tole:
Do sedaj sem naredil samo tole:
#include <iostream> #include <time.h> using namespace std; void Zamenjaj (int &a, int &b) { int zacasno; zacasno = a; a = b; b = zacasno; } int Deli (int polje[], int dno, int vrh) { int pe = polje[dno]; int l = dno; //levi indeks int d = vrh; //desni indeks int m = (dno + vrh)/2; Zamenjaj(polje[dno], polje[m]); while (l < d) { while ((polje[l] <= pe) && (l < vrh)) { l += 1; } while ((polje[d] >= pe) && (d > dno)) { d -= 1; } } if (l < d) { Zamenjaj (polje[l], polje[d]); } Zamenjaj (polje[dno], polje [d]); return d; } /* void HitroUredi (int polje[], int vrh, int dno) { if (dno < vrh) { int j; j = Deli (a, dno, vrh); HitroUredi (a, dno, j-1); HitroUredi (a, j+1, vrh); } } */ void Preveri (int polje[], int vrh, int dno) { for (int i = dno; i < (vrh - 1); i++) { if (polje[i+1] < polje[i]) cout << endl << "Napacno urejeno zaporedje!" << endl; } } void GenerirajZaporedje(int polje[], int velikost) { srand (time(NULL)); for (int i=0; i<velikost; i++) { polje[i] = rand() % 100000 + 1; } } void IzpisiZaporedje(int* polje, int velikost) { for(int i = 0; i < velikost; i++) { cout << polje[i] << " "; } } int main() { int odg, velikost; cout << "Vnesi velikost polja: " ; cin >> velikost; int* k_polje = new int[velikost]; do { cout << endl << "--------------------------" << endl << "Hitro uredi - izbira: " << endl << "1 Generiraj nakljucno zaporedje" << endl << "2 Generiraj urejeno narascajoce zaporedje" << endl << "3 Generiraj urejeno padajoce zaporedje" << endl << "4 Izpis zaporedja" << endl << "5 Uredi" << endl << "6 Konec" << endl << endl << "Izbira: " ; cin >> odg; switch(odg) { case 1: { GenerirajZaporedje(k_polje, velikost); break; } case 2: { break; } case 3: { break; } case 4: { cout << endl ; IzpisiZaporedje(k_polje, velikost); break; } case 5: { break; } case 6: return 0; } }while (odg != 6); }
Thomas ::
Vse kar ti jaz lahko povem o sortiranju je tole.
http://critticall.com/ArtificialSort.ht...
To algoritem ima samo eno napako. Ne particionira najmanjšega dela, kar pa zlahka popraviš.
Kaj pravijo profesorji me ne zanima niti malo.
http://critticall.com/ArtificialSort.ht...
To algoritem ima samo eno napako. Ne particionira najmanjšega dela, kar pa zlahka popraviš.
Kaj pravijo profesorji me ne zanima niti malo.
Man muss immer generalisieren - Carl Jacobi
Mipe ::
Na http://critticall.com/ArtificialSort2.h... sem trikrat zaporedoma probal... vsakič je zmagal QuickSort.
Thomas ::
Hja .. na kakšni dati si pa probal?
Aja, sploh nisi. Na random dati lahko zmaga Quick, jasno, tako kot zip poveča random bit string.
Ti lepo vzemi C++ kodo dol in probaj z nekimi realnimi podatki.
Aja, sploh nisi. Na random dati lahko zmaga Quick, jasno, tako kot zip poveča random bit string.
Ti lepo vzemi C++ kodo dol in probaj z nekimi realnimi podatki.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
Mipe ::
Zgolj kliknil sem tisti "Animation example with random data" link na strani, ki si jo linkal.
Thomas ::
Ma tist je predposnet gif, ki kaže sortanje ene RANDOM date. Za katero velja, kar smo rekli.
Man muss immer generalisieren - Carl Jacobi
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | [C#] Domača naloga za faksOddelek: Programiranje | 2049 (1673) | Spura |
» | [C] Funkcija vrnitev kazalcaOddelek: Programiranje | 1168 (884) | MrStein |
» | Kruskalov algoritem težave pri implementacijiOddelek: Programiranje | 1593 (1367) | zacetnik11 |
» | [c++] bubblesortOddelek: Programiranje | 3126 (3126) | strictom |
» | Bubble sortOddelek: Programiranje | 1527 (1419) | OwcA |