Hej

ett litet problem, hur gör man quicksort stabil, har hämtat följande kod ur Sedgewick (se nedan).
Funktionen quicksort är stabil men inte partition. DVS hur gör man partition stabil?

Eller måste man gör på något annat sätt?

template <class Type>
void Algorithms<Type>::QuickSort(vector<Type> &a, int l, int r)
{
if (r <= l) return;
int i = partition(a, l, r);
QuickSort(a, l, i-1);
QuickSort(a, i+1, r);
}

template <class Type>
int Algorithms<Type>::partition(vector<Type> &a, int l, int r)
{
int i = l-1, j = r;
Type v = a[r];
for (;;) {
while (a[++i] < v) ;
while (v < a[--j]) if (j == l)
break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}

Har för mig att man kopierar till en temporär buffer som man sen lägger till på slutet

Nåt i stil med:

<code=c++>
template <typename It>
void stable_partition(It first, It last, const It::value_type& key) {
vector<It::value_type> buf;
It next = first;
for (; first != last; ++first) {
if (*first < key)
*next++ = *first;
else
buf.push_back(*first);
}
std::copy(buf.begin(), buf.end(), next);
}
</code>

Är det inte generellt så att den då blir (iofs konstant, men ändå) typ hälften så snabb?

Det finns ett annat sätt att stabilisera alla sorteringsalgoritmer som av någon anledning mycket sällan lärs ut. Jag har "hittat på det" själv, men det kan knappast vara en speciellt unik idé. Det är extremt enkelt:

Vi har en sekvens a, med n(a) element. Vi skapar nu ytterligare en sekvens b av samma typ (lista, vektor, whatever), och samma längd, men med int-element istället. Vi fyller denna sekventiellt med intar från 1 till n(a).

Sen hanterar vi antingen detta som en sekvens med par eller ett par med sekvenser.

(Enklare uttryckt av allt där uppe, vi slänger på en 1:a på första elementet, en 2:a på andra elementet, osv.)

Sen kör vi en godtycklig sorteringsalgoritm. Sorteringsalgoritmen använder (om det är en comparison sort) någonstans en funktion "compare". Låt säga:

for (p = begin(); p != end(); p++)
if(compare(p, q) > 0)
p>q
else if(compare(p, q) < 0)
p<q
else
p==q

Vad vi helt enkelt gör nu är att "augmenta" compare med ytterligare en punkt, typ:

int compare_aux(a, b)
{
if(compare(a, b)==0)
return b.tag-a.tag;
else
return compare(a,b);
}

Så kommer man alltid få distinkta element, och de kommer alltid ligga rätt.

Eller kanske enklare beskrivning av modifikationen:

template<T>
bool operator<(T lhs, T rhs){
if (lhs == rhs)
return lhs.tag < rhs.tag;
return lhs < rhs;
}

Hej å tack för svaren.

Förstår inte riktigt hur och var jag ska implementera jämförelsen.

lhs.tag? antar att man gör om sin array, vector till en vector bestående av struct med int tag och data?!

Ja precis. Mina uttryck var lite pseudokodsaktiga...
Om vi säger så här då, du börjar med:

a b c d e a a d

Du utökar detta till:

(a 1) (b 2) (c 3) (d 4) (e 5) (a 6) (a 7) (d 8)

Sen sorterar du i första hand på bokstav, och i andra hand på din tag. I princip betyder det bara att om bokstäverna är samma så sorterar du på tag.

Detta ger i så fall

(a 1) (a 6) (a 7) (b 2) (c 3) (d 4) (d 8) (e 5)


För att sortera vill man ha något sätt att jämföra två objekt, eller hur?
Det man normalt sätt använder är < osv.
Så säg att du har en klass som har < och == definierad:

class A{
public:
  operator<(A a) {...}
  operator==(A a) {...}
//...
}

//Då skapar du en ny klass
class B{
public:
  operator<(B b) {
    if(b.a == a)
      return (b.tag < tag);
    else
      return b.a<a;
  }
  operator==(B b) {return false;}
//...
private:
  A a;
}

//du har från början
vector<A> va = ...;

//och sen använder du dig av:
vector<B> vb = make_vec_b(va);
QuickSort(vb);

va = make_vec_a(vb);

Tackar!