sort

#include <iostream>
#include <ctime>
#include <stdlib.h>
#define N 10000
using namespace std;

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


void DELL(node *& H){
    if(H!=NULL){
        node * temp=new node;
        temp = H;
        H=temp->next;
        delete temp;
    }
}

void ADD( node *& H, int val){
    node * temp = new node;
    temp->next=H;
    temp->value=val;
    H=temp;
}


void show(node * H){
    cout <<"H->";
    node *temp=H;
    while(temp!=NULL){
        cout << temp->value<<"->";
        temp=temp->next;
    }
    cout << "NULL"<<endl;
}
void sort(node*&H, node**&tab)
{
	if(H!=NULL)
	{
		node *temp=H;
		while(temp->next!=NULL)
		{
			for(int i=0;i<N/100;i++)
			{
				if (temp->value <= (i + 1) * 100 && temp->value>i*100)
				{
                    ADD(tab[i], temp->value);
					break;
				}
			}
			temp=temp->next;
		}
	}
}

void bubblesort(node*&H)
{
    if (H != NULL)
    {
        int i = 0;
        node *temp = H, *tmp = NULL, *tmp2 = NULL, *tmp3 = NULL;
        while (temp->next->next != NULL)
        {
            i = 0;
            if (H->value>H->next->value)
            {
                i++;
                tmp = H;
                tmp2 = H->next;
                tmp3 = H->next->next;
                tmp->next = tmp3;
                tmp2->next = tmp;
                H = tmp2;
                temp = H;
            }

            while (temp->next->next != NULL)
            {
                if (temp->next->value>temp->next->next->value)
                {
                    i++;
                    tmp = temp->next;
                    tmp2 = temp->next->next;
                    tmp3 = temp->next->next->next;
                    tmp->next = tmp3;
                    tmp2->next = tmp;
                    temp->next = tmp2;
                    temp = temp->next;
                }
                else
                    temp = temp->next;
            }
            if (i != 0)
                temp = H;

        }
    }
}
void lacz(node *&p, node **&tab)
{
    node* temp = NULL;
    temp = tab[0];
    for (int i = 0; i < N / 100; i++)
    {


        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = tab[i + 1];
        if (i == (N / 100) - 1)
            temp->next = NULL;


    }
    p = tab[0];
}

int main()
{
    clock_t s, f;
    double czas=0.0, czas2=0.0;
    node *p = NULL;
    int x = N / 100;
    node **tab = new node*[x];
    for (int i = 0; i < x; i++)
    {
        tab[i] = NULL;

    }
    srand(time(NULL));
    node * H = NULL, *H2=NULL;
    for (int i = 0; i < N; i++)
    {
        ADD(H, rand() % 10000);
        ADD(H2, rand() % 10000);
    }


    //show(H);
	s = clock();
    sort(H, tab);

    for (int i = 0; i < x; i++)
    {
        bubblesort(tab[i]);
        //cout << "DB[" << i << "]->";
        //show(tab[i]);

    }
    lacz(p, tab);
    f = clock();

    czas += (double)(f - s) / CLOCKS_PER_SEC;
    s = clock();
    bubblesort(H2);
    f = clock();
    czas2 += (double)(f - s) / CLOCKS_PER_SEC;


    //show(p);
    cout << czas << endl;
    cout << czas2 << endl;





    system("pause");
}