// CombSort.MergeSort 30.08 0055.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include 

using namespace std;

struct node node
{
        int val;
        node* next;
};

void add(node*& H, int x)
{
        node* p = new node;
        p->val;
        p->next;
p->val = x;
        p->next = H;
        H = p;
}

void del(node*& H)
{
        
        if (H != NULL)
        {
                node* p = H;
                H = H->next;
                delete p;
        }
}

int count(node*& H)
{
        node* p = H;
        int n = 1;
        while (p != NULL)
        {
                n++;
                p = p->next;
        }
        return n;
}

int half(node*& H, int x)
{
        if (H != NULL)
        {
                node* slow = H;
                count(x);
                for (int i = 0; i < x; i++)
                {
                        slow = slow->next;
                }

        }
        return slow;  //potrzebuje zwrocic wskaznik na element ktory jest polowa listy
}

void show(node* H)
{
        node* p = H;
        if (H != NULL)
        {
                node* p = H;
                cout << "->" << p->val;
                H = H->next;
        }
        else
                cout << "NULL" << endl;
}

void findmin(node* merge(node*& H)
{
                
        node* p front = H;
        if (H != NULL)
        {
                int min x = 0;
                while (p)
                {

                        if (p->val < min)
                        {
                                min = p->val;
                        }
                        p = p->next;
                }
        }
half(H, count(H));
}

int getNextGap(int gap)
{
        gap = (gap * 10) / 13;
        if (gap < 1)
                return 1;
        return gap;
}

void swap(node*& H)
{
        if (H != NULL) {
                add(H, 0);
                node* p = H;
                while ((p->next->next) != NULL) {

                        node* p2 = p->next;

                        p->next = p->next->next;
                        p2->next = p2->next->next;
                        p->next->next = p2;

                        p = p->next->next;
                        if (p->next == NULL) break;
                }
                del(H);
        }
}

int count(node* H)
{
        node* p = H;
        int n = 0;
        while (p!=NULL && p->next!=NULL)
        {
                n++;
                p = p->next;
        }
        return n;
}

void CombSort(node*& H, int n)
{
        node* p = H;
        int gap = n;
        bool swapped = true;
        while (gap != 1 || swapped == true)
        {
                gap = getNextGap(gap);
                swapped = false;
                for (int i = 0; i < n - gap; i++)
                {
                        if (p > p->next)
                        {
                                swap(p, p->next);
                                swapped = true;
                        }
                }
        }

}
int main()
{
        node* H = NULL;
        add(H, 5);
        add(H, 2);
        add(H, 11);
        add(H, 9);
        add(H, 3);
        add(H, 6);
        CombSort(H, count(H));
        return 0;
    
}