[C++] Bubble Sort e Quick Sort

[Squall1988]

Salve, qualcuno per caso ha una versione del bubble sort e del quick sort scritte in c++?? Possibilmente non dovrebbero essere ricorsive (anche se non credo si possa fare il quick sort non ricorsivo).

Xkè il bubble non lo conoscevo prima e ho trovato alcune versioni su internet ma sono identiche al sort ingenuo...

[dekdek]

Che intendi per sort ingenuo?

P.S. Qualsiasi algoritmo ricorsivo puo' essere riscritto in forma iterativa. Se vengono fatte chiamate multiple, pero', ti tocca gestire manualmente un sostituto del call stack...

[Squall1988]

intendo quello che confronta tutti i numeri con tutti gli altri tipo

for (int i = 0; i < n-1; i++)
 for (int j = i+1; j<n; j++)
  if (v[i] > v[j])
  {
    int temp = v[i];
    v[i] = v[j];
    v[j] = temp;
  }

[dekdek]

Questo _E'_ il bubble sort.
Se ritieni ingenuo il bubble sort, allora cosa penseresti del Selection sort? ^__^

Ah, manca solo il modify flag.

int flag = 1; // In C++ esistono i boolean? Boh...
for (int i = 0; (i < n-1) && flag; i++) {
 flag = 0;
 for (int j = i+1; j<n; j++)
  if (v[i] > v[j])
  {
    int temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    flag = 1;
  }
}

Se flag resta zero vuol dire che non e' stato fatto nessuno scambio, ergo, il vettore e' ordinato e si puo' uscire dal ciclo.

Un'ulteriore miglioria consiste nel rendere l'algoritmo bidirezionale. In generale convergera' prima.

[Squall1988]

nn è ke lo ritengo ingenuo è ke a me han sempre detto ke quello si kiama così...

[dekdek]

Ingenuo sort?

[Squall1988]

no, sort ingenuo, o naive sort se preferisci