// #include "stdafx.h"
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
 
struct Item
{
    int key;
    Item * next;
};
 
Item * start = nullptr;
 
const bool debug = false;
const bool print_numbers = true;
const int random_numbers = 1000;
// pri velkem poctu cisel (nad 80 000) dojde k preplneni zasobnik
 
void add (Item * & list, int value)
{
    Item * p = new Item;
    p->key = value;
    p->next = nullptr;
 
    if (list != nullptr)
        p->next = list;
    list = p;
}
 
void swap (int & a, int & b)
{
    int c = a;
    a = b;
    b = c;
}
 
 
void print (Item * i, Item * k, bool stop)
{
   cout << "( ";
   Item * p = start;
   while (p != nullptr)
   {
       if (p == i) cout << "i:";
       if (p == k) cout << "k:";
      cout << p->key << " ";
      p = p->next;
   }
   cout << ")";
   if (stop) cout << " stop=true";
   cout << endl;
}
 
void step (int h, Item * & i, Item * & k, int & lo, int & hi, Item * prev, Item * curr, Item * last, bool & stop)
// h ... pivot
// i ... ukazatel (drive index) jdouci od leveho okraje
// k ... ukazatel (drive index) jdouci od praveho okraje
// lo ... pocet prvku na levem okraji (pro dalsi rekurzivni volani quick)
// hi ... pocet prvku na pravem okraji (pro dalsi rekurzivni volani quick)
// curr ... pracovni prvek na pravem okraji (neumime "couvat", tak rekurze)
// last ... ukazatel na pravy okraj
// stop ... priznak ze jiz doslo k "prekrizeni indexu", obdoba podminky "k < i" pouzivane u ciselnych indexu
// i, k, lo, ho, stop ... reference, tj. sdilene promenne v ramci jednoho quick ()
{
    if (curr != last)
    {
        step (h, i, k, lo, hi, curr, curr->next, last, stop); // rekurze misto cyklu
        // kod po rekurzivnim volani, "sestupujeme dolu, proti smeru seznamu
    }
 
    while (i->key < h) // od leveho okraje postupujeme normalne
    {
        if (debug) cout << "   step -> " << i->key << endl;
        if (i == k) stop = true;
        i = i->next;
        lo ++;
        if (debug) print (i, k, stop);
    }
 
    // od praveho okraje diky rekurzi, po jednom policku
    if (! stop)
    {
        if (curr->key > h)
        {
            // krok dolu
            if (debug) cout << "   step <-- " << curr->key << endl;
            if (i == k) stop = true;
            k = prev;
            hi ++;
            if (debug) print (i, k, stop);
        }
        else
        {
            if (debug) cout << "   swap <--> " << i->key << " <--> " << k->key  << endl;
            swap (i->key, k->key); // vymena
            if (debug) print (i, k, stop);
 
            if (i == k) stop = true;
            k = prev;  // stejny krok dolu
            hi ++;
 
            if (i == k) stop = true;
            i = i->next; // krok nahoru
            lo ++;
 
            if (debug) print (i, k, stop);
        }
    }
}
 
void quick (Item * r, Item * s)
{
    // spocitat prvky
    int cnt = 0;
    Item * p = r;
    if (debug) cout << "quick: ";
    while (p != s)
    {
        if (debug) cout << p->key << " ";
        p = p->next;
        cnt ++;
    }
    if (debug) cout << p->key << " ";
 
    // vybrat prostredni hodnotu
    int inx = cnt / 2;
    p = r;
    while (inx > 0)
    {
        p = p->next;
        inx --;
    }
 
    int h = p->key;
    if (debug) cout << " h=" << h << endl;
 
    Item * i = r;
    Item * k = s;
    Item * prev = nullptr;
    int lo = 0;
    int hi = 0;
    Item * curr = r;
    Item * last = s;
    bool stop = false;
    step (h, i, k, lo, hi, prev, curr, last, stop);
 
    if (lo > 1) quick (r, k);
    if (hi > 1) quick (i, s);
}
 
void quickSort (Item * r)
{
    if (r != nullptr)
    {
       // najit posledni
       Item * s = r;
       while (s->next != nullptr)
            s = s->next;
       quick (r, s);
    }
}
 
int main (int argc, char * argv[])
{
    start = nullptr;
 
    if (random_numbers > 0)
    {
       // srand (time (nullptr));
       int n = random_numbers;
       for (int i = 1; i <= n; i++)
          add (start, rand () % 1000000 );
    }
    else
    {
        // zadani hodnot (od konce)
        if (1)
        {
            add (start, 20);
            add (start, 7);
            add (start, 15);
            add (start, 1);
            add (start, 3);
            add (start, 10);
            add (start, 12);
        }
        else
        {
            int a [] = { 64, 51, 76, 88, 23, 74, 63, 69, 93, 28 };
            int n = sizeof (a) / sizeof (a[0]);
            for (int i = n; i > 0; i--)
               add (start, a[i] );
        }
    }
 
    quickSort (start);
 
    bool err = false;
    Item * p = start;
    while (p != nullptr)
    {
        if (print_numbers) cout << endl << p->key;
        if (p->next != nullptr)
            if (p->key > p->next->key)
            {
                cout << " Chyba";
                err = true;
            }
        p = p->next;
    }
    cout << endl;
    if (err) cout << "NEJAKA CHYBA" << endl;
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}