Thursday, July 30, 2015

Quicksort implementation compilation

I made a compilation of different known quick sort partitioning methods, implementations and pivot choosing methods.

Partitioning


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
void Bentley_McIlroy(int*& lo, int*& hi)
    {
         using std::swap;

         int pivot = *lo;
         int *j = lo, *i = hi--, *p = lo + 1, *q = hi;

         while (true)
         {
             while (pivot < *(--i));
             while (*(++j) < pivot) if (j == hi) break;
             if (j >= i) break;     
             swap(*i, *j);

             if (*i == pivot) swap(*q--, *i);
             if (*j == pivot) swap(*p++, *j);
         }
         int min = std::min(p - lo, i - p + 1);
         for (int f = 0; f < min; ++f)
             swap(*(lo + f), *(i - f));

         int min2 = std::min(hi - q, q - i);
         for (int f = 1; f < min2; ++f)
             swap(*(hi - f), *(i + f));

         lo = ++i - (p - lo);
         hi = i + (hi - q); 
    }

     int* lomutoPartition(int* p, int* r)
     {
         using std::swap;

         int pivot = *(--r), *i = p - 1;

         for (int* j = p; j != r; ++j)
         {
             if (*j <= pivot)
                 swap( *(++i), *j);
         }
         swap(*r, *(++i));
         return i;
     }

     int* hoare(int *lo, int *hi)
     {
         using std::swap;
         int pivot = *lo, *i = lo, *j = hi--;

         while (true)
         {
             while (*(++i) < pivot) if (i == hi) break;
             while (pivot < *(--j) );
            
             if (j <= i) break;
             swap(*i, *j);
         }
         swap(*j, *lo);

         return j;
     }


     void dijkstra_3_way_partitioning(int*& l, int*& g)
     {
         using std::swap;
        
         int *i = l + 1, pivot = *l;        
         while (i < g)
         {
             if (*i < pivot)
                 swap(*i++, *l++);
             else if (*i > pivot)
                 swap(*i, *(--g));
             else
                 i++;
         }
     }

     void dual_pivot_partitioning(int*& L, int*& G)
     {
         using std::swap;
        
        if (*L > *(--G)) swap( *L, *G);

         int pivot1 = *L, *first = L,
             *last = G, pivot2 = *G--, *K = L++;

         while (K <= G)
         {
             if (*K < pivot1)
                 swap(*L++, *K++);
             else if (*K > pivot2)
                 swap(*G--, *K);
             else
                 ++K;
         }
         swap(*(--L), *first);
         swap(*(++G), *last);
     }

Pivot and shuffle


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
std::random_device rd;
std::mt19937 mt(rd());

int* random(int *ini, int *fin)
{
    std::uniform_int_distribution <> dist(0, fin - ini - 1);
    return ini + dist(mt);
}

int* randomMedianOfN(int * ini, int * fin, int N)
{
    if (fin - ini < N) return ini;

    for (int * i = ini; i != ini + N; ++i)
    {
        int * r = Pivots::random(i, fin);
        std::swap(*i, *r);
    }
    std::nth_element(ini, ini + N / 2, ini + N);

    return ini + 1;
}

void fisher_yates_shuffle(int *ini, int *fin)
{
    for (auto i = ini; ini != fin; ++ini)
        std::swap(*Pivots::random(ini, fin), *ini);
}

Quicksort



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void B_M_sort(int* ini, int* fin)
{
    if (ini >= fin - 1) return;

    auto ini2 = ini, fin2 = fin;
    Particions::Bentley_McIlroy(ini2, fin2);

    B_M_sort(ini, ini2);
    B_M_sort(fin2, fin);
}

void sort(int* ini, int *fin)
{
    if (ini >= fin - 1) return;

    auto pivot = Particions::hoare(ini, fin);

    sort(ini, pivot);
    sort(pivot + 1, fin);
}

void Lomutosort(int* ini, int *fin)
{
    if (ini >= fin - 1) return;

    auto pivot = Particions::lomutoPartition(ini, fin);

    sort(ini, pivot);
    sort(pivot + 1, fin);
}

void javaSort(int* ini, int *fin)
{
    if (ini >= fin - 1) return;

    auto ini2 = ini, fin2 = fin;
    Particions::dual_pivot_partitioning(ini2, fin2);

    javaSort(ini, ini2);
    if(*ini2 != *fin2) 
        javaSort(ini2 + 1, fin2);
    javaSort(fin2 + 1, fin);
}

void iterativeSort(int* ini, int* fin)
{

    unsigned MaxLength = 2 * static_cast<unsigned> (std::log2l(fin - ini));
    Stack<int*> stack(MaxLength);
    stack.push(nullptr);
    stack.push(nullptr);

    while (!stack.empty())
    {
        while (ini < fin - 1)
        {
            auto ini2 = ini, fin2 = fin;
            Particions::Bentley_McIlroy(ini2, fin2);
            if ((ini2 - ini) >(fin - fin2))
            {
                stack.push(ini2);
                stack.push(ini);
                ini = fin2;
            }
            else
            {
                stack.push(fin);
                stack.push(fin2);
                fin = ini2;
            }
        }
        ini = stack.pop();
        fin = stack.pop();
    }
}
Posted by at
Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)