1. // CombSort.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
2. //
3.  
4. #include <iostream>
5.  
6. using namespace std;
7.  
8. struct node {
9.         int val;
10.         node* next;
11. };
12.  
13. void add(node*& H, int x)
14. {
15.         node* p = new node;
16.         p->val;
17.         p->next;
18.         H = p;
19. }
20.  
21. void del(node*& H)
22. {
23.         if (H != NULL)
24.         {
25.                 node* p = H;
26.                 H = H->next;
27.                 delete p;
28.         }
29. }
30.  
31. void show(node* H)
32. {
33.         node* p = H;
34.         if (H != NULL)
35.         {
36.                 cout << "->" << p->val;
37.                 H = H->next;
38.         }
39.         cout << "NULL" << endl;
40. }
41.  
42. void findmin(node* H)
43. {
44.         node* p = H;
45.         if (H != NULL)
46.         {
47.                 int min = 0;
48.                 while (p)
49.                 {
50.  
51.                         if (p->val < min)
52.                         {
53.                                 min = p->val;
54.                         }
55.                         p = p->next;
56.                 }
57.         }
58. }
59.  
60. int getNextGap(int gap)
61. {
62.         gap = (gap * 10) / 13;
63.         if (gap < 1)
64.                 return 1;
65.         return gap;
66. }
67.  
68. void swap(node*& H)
69. {
70.         if (H != NULL) {
71.                 add(H, 0);
72.                 node* p = H;
73.                 while ((p->next->next) != NULL) {
74.  
75.                         node* p2 = p->next;
76.  
77.                         p->next = p->next->next;
78.                         p2->next = p2->next->next;
79.                         p->next->next = p2;
80.  
81.                         p = p->next->next;
82.                         if (p->next == NULL) break;
83.                 }
84.                 del(H);
85.         }
86. }
87.  
88. int count(node* H)
89. {
90.         node* p = H;
91.         int n = 0;
92.         while (p!=NULL && p->next!=NULL)
93.         {
94.                 n++;
95.                 p = p->next;
96.         }
97.         return n;
98. }
99.  
100. void CombSort(node*& H, int n)
101. {
102.         node* p = H;
103.         int gap = n;
104.         bool swapped = true;
105.         while (gap != 1 || swapped == true)
106.         {
107.                 gap = getNextGap(gap);
108.                 swapped = false;
109.                 for (int i = 0; i < n - gap; i++)
110.                 {
111.                         if (p > p->next)
112.                         {
113.                                 swap(p, p->next);
114.                                 swapped = true;
115.                         }
116.                 }
117.         }
118.  
119. }
120. int main()
121. {
122.         node* H = NULL;
123.         add(H, 5);
124.         add(H, 2);
125.         add(H, 11);
126.         add(H, 9);
127.         add(H, 3);
128.         add(H, 6);
129.         CombSort(H, count(H));
130.         return 0;
131. }
132.  
133.