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

#include <iostream>

using namespace std;

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

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

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

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

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

			if (p->val < min)
			{
				min = p->val;
			}
			p = p->next;
		}
	}
}

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;
}