Quicksort - implementacja

Piszę sobie quicksorta, w którym pivot jest losowym elementem. Zrobiłem to na dwa sposoby. Sposób pierwszy:

int Sort::partRand(int l, int r) {
    srand(time(0));
    int x = (rand() % (r - l)) + l;
    int p = tab[x];

    swap(tab[x], tab[r]);
    int i = l - 1;
    for (int j = l; j < r; j++)
        if (tab[j] <= p)
            swap(tab[++i], tab[j]);
    swap(tab[++i], tab[r]);
    return i;
}

void Sort::quickSort(int l, int r) {
    if (l < r) {
       int p = partRand(l, r);
        quickSort(l, p - 1);
        quickSort(p + 1, r);
    }
}

Czyli pierwsze co robię to zamieniam pivota z ostatnim elementem i wykonuję standardowy algorytm (w ten sposób quicksort jest zaprezentowany w Cormenie).

Drugi sposób:

void Sort::qsort2(int l, int h) {
    int i, j;
    int x;
    i = l;
    j = h;

    x = tab[(rand() % (h - l)) + l];

    while (i < j) {

        while (tab[i] < x) i++;
        while (tab[j] > x) j--;

        if (i <= j) {
            swap(tab[i], tab[j]);
            i++;
            j--;
        }
    }

    if (l < j) qsort2(l, j);
    if (h > i) qsort2(i, h);
}

Tutaj z dwóch stron idą "wskaźniki", które zamieniają ze sobą odpowiednie elementy.

Pytanie mam następujące: czy jest jakaś różnica pomiędzy tymi implementacjami? Głównie chodzi mi o stronę wydajnościową. Bardziej przychylam się do implementacji pierwszej, ponieważ łatwiej mi będzie na jej podstawie napisać introsorta. Czy oba sposoby są tożsame i dla takiej samej porcji danych będą działać w tym samym czasie (zakładając, że będą się losować te same pivoty)?

Drugi QuickSort ma wklejoną procedurę Partition, a pierwszy ją wywołuje. Partition w pierwszym QuickSorcie pochodzi od Lomuto, a drugi od Hoare'a. Czas działania będzie różny jeżeli wartości w tablicy mogą się powtarzać (tak myślę, po pobieżnym przeanalizowaniu Lomuto Partition dochodzę do wniosku że kwadraci on QuickSorta jeśli wszystkie wartości w tablicy wejściowej są równe). Można to poprawić poprzez dzielenie na trzy partycje: elementy mniejsze, równe i większe od elementu dzielącego. Na Wikipedii znajdziesz metodę na ograniczenie głębokości drzewa rekursji.