quicksort z własnym komparatorem

W jaki sposób zmodyfikować poniższy quicksort, żeby sortował ze względu na moją własną funkcje porównującą? Funkcja z argumentami (a, b) zwraca 1, gdy a > b (gdzie > jest dowolną relacją), oraz 0, gdy nie jest to prawdą. Dokładnie tak, jak quicksort z algorithm.

template <class type>
void sort (type T[], type left, type right) {
	type i = left;
	type j = right;
	type pivot = T[(left + right) / 2];
	do {
		while (T[i] < pivot)
			++i;

		while (T[j] > pivot)
			--j;

		if (i <= j) {
			swap (T[i], T[j]);

			++i;
			--j;
		}
	} while (i <= j);

	if (left < j) sort (T, left, j);
	if (right > i) sort(T, i, right);
}

Może coś takiego?

 
//musisz gdzieś zdefiniować te operatory
bool operator<(const TwojTyp &a, const TwojTyp &b)
{
	return /*jakis warunek*/	
}

bool operator>(const TwojTyp &a, const TwojTyp &b)
{
	return /*jakis warunek*/	
}

bool operator<=(const TwojTyp &a, const TwojTyp &b)
{
	return /*jakis warunek*/	
}

template <class type>
void sort (type T[], type left, type right) {
    type i = left;
    type j = right;
    type pivot = T[(left + right) / 2];
    do {
        while (T[i] < pivot)
            ++i;
 
        while (T[j] > pivot)
            --j;
 
        if (i <= j) {
            swap (T[i], T[j]);
 
            ++i;
            --j;
        }
    } while (i <= j);
 
    if (left < j) sort (T, left, j);
    if (right > i) sort(T, i, right);
}

Niestety sortowana tablica będzie tablicą unsigned intów.

@stryku : niemożliwe jest przeładowanie operatorów dla typów wbudowanych. Przynajmniej jeden z argumentów operatora musi nie być owym typem wbudowanym. Unsigned int jest typem wbudowanym.
Pytanie 2: a jeśli chciałbym sortować według ilości '1' w zapisie binarnym? Albo według ilości znaków ']' w moim własnym systemie osiemnastkowym?

Jest wiele sposobów na zrobienie tego co chcesz. Podałem tylko jeden z nich. Nie wiedziałem, że unsigned inty bd używał.

Możesz zrobić też coś takiego

bool lessThan(const TwojTyp &a, const TwojTyp &b)
{
    return /*jakis warunek dla <*/    
}
 
bool greaterThan(const TwojTyp &a, const TwojTyp &b)
{
    return /*jakis warunek dla >*/    
}
 
bool lessEqual(const TwojTyp &a, const TwojTyp &b)
{
    return /*jakis warunek dla <=*/    
}
 
template <class type>
void sort (type T[], type left, type right) {
    type i = left;
    type j = right;
    type pivot = T[(left + right) / 2];
    do {
        while (lessThan(T[i], pivot))
            ++i;
 
        while (greaterThan(T[i], pivot))
            --j;
 
        if (i <= j) {
            swap (T[i], T[j]);
 
            ++i;
            --j;
        }
    } while (lessGreater(i, j));
 
    if (lessThan(left, j)) sort (T, left, j);
    if (greaterThan(right, i)) sort(T, i, right);
} 

@stryku: wtf? Twoje rozwiązania wymagają globalnego przeładowania trzech funkcji (powodzenia z posortowaniem dwóch tablic według różnych predykatów) i nie są w ogóle elastyczne. Ponadto nie powinno mieć żadnego znaczenia jaki typ jest sortowany.

@OP: to ostatnie się też tyczy Ciebie. Typ elementu tablicy i typ indeksu nie mają logicznego powiązania.

Imho najlepszym rozwiązaniem będzie opisanie wszystkich porównań za pomocą jednej funkcji, a następnie zamiana tej funkcji na predykat przekazany w parametrze.

Czyli:
T[i] < pivot ⟶ T[i] < pivot ⟶ pred(T[i], pivot)
T[j] > pivot ⟶ pivot < T[j] ⟶ pred(pivot, T[j])

Dlaczego nie ruszam i <= j, które można opisać jako !pred(j,i)? Ponieważ porównujesz indeksy, które powinny móc być innego typu niż element sortowanego kontenera i których porównanie nie ma się nijak do porównania elementów kontenera.

W kodzie (dodatkowo dodałem sprawdzanie, czy nie wyszedłeś za zakres, bo o tym zapomniałeś):

template <class type, typename Pred = less<type>>
void mySort (type T[], type left, type right, Pred&& p = less<type>{}) {
	type i = left;
	type j = right;
	type pivot = T[(left + right) / 2];
	do {
		while (p(T[i],pivot) && i <= right)
			++i;

		while (p(pivot,T[j]) && j >= left)
			--j;

		if (i <= j) {
			swap (T[i], T[j]);

			++i;
			--j;
		}
	} while (i <= j);

	if (left < j) mySort(T, left, j, p);
	if (right > i) mySort(T, i, right, p);
}

Przykład: http://melpon.org/wandbox/permlink/uPavqyz5wdtmi7dT
Dowód dla ostatniego sortowania: http://melpon.org/wandbox/permlink/LtYQYMNPXUhF2Ywx

Użyj odejmowania.
Zwykle wygląda to tak: c = a - b

i teraz uwaga - będzie rewelacja!

gdy a > b, co znaczy tyle co: a jest większe od b, wtedy c > 0,
gdy a < b, co znaczy: a jest mniejsze od b, i wtedy c < 0.

Jako zadanie domowe pozostawiam przypadek: a = b -> c = ?

@sraka niebieska : proponuje jeszcze raz przeczytać pytanie.
@kq : dokładnie o to chodziło, nie byłem tylko pewien, gdzie zamiast relacji "<" powinienem postawić funkcję porównującą. Swoją drogą - mój kod nie wydaje się być mało uniwersalny. Nie bardzo rozumiem
"Ponadto nie powinno mieć żadnego znaczenia jaki typ jest sortowany.
@OP: to ostatnie się też tyczy Ciebie. Typ elementu tablicy i typ indeksu nie mają logicznego powiązania."
Zrobiłem ładną templatke, więc typ sortowany nie będzie miał znaczenia, dopóki istnieje dla niego operator porównania. Swoją drogą - jaka jest różnica między class a typename w template? Jakoś nigdy nie było mi to dane wiedzieć...

type i = left;
type j = right;
type pivot = T[(left + right) / 2];

Przecież tutaj zakładasz, że zarówno indeksy i, j, jak i wartość w tablicy mają ten sam typ type.

anonymous23456 napisał(a):

Swoją drogą - jaka jest różnica między class a typename w template? Jakoś nigdy nie było mi to dane wiedzieć...
Między <> żadna. Natomiast typename ma również inne zastosowania np.

template<class A, typename B>
class Foo
{
    typename A::some_type bar;
    class A::some_type bar2;         // to nie przejdzie
};

Swoją drogą - mój kod nie wydaje się być mało uniwersalny. Nie bardzo rozumiem

void mySort (type T[], type left, type right,

T[] to (tutaj) wskaźnik na pierwszy element tablicy, left i right to indeksy. Czy z takim zapisem będziesz w stanie posortować tablicę stringów? Co będzie znaczyło T[i] lub type pivot = T[(left + right) / 2];?

Swoją drogą - jaka jest różnica między class a typename w template?
Tutaj żadna, ale template template wymaga syntaxu z class. Przy czym ja wolę typename, ponieważ nie sugeruje, że typ musi być klasą.

template<template <typename,typename> class Container>
struct ok{};

//template<template <typename,typename> template Container>
//struct error{};

int main()
{
	ok<vector> foo{};
//	error<vector> bar{};
}

Okej, dzięki wielkie ; )