Ознайомлення з алгоритмами сортувань статичних та динамічних структур даних, страница 2

    {

     b=a->next;

     a->next=b->next;

     b->next->pred=a;

     b->next=a;

     a->pred=b;

     b->pred=NULL;

     xh=b;

     h=b;

     p=0;

    }

    if(((a->zn)>(a->next->zn))&&((a->next)!=NULL)&&(a!=NULL)&&(a->pred!=NULL))

    {

     b=a->next;

     a->next=b->next;

     b->pred=a->pred;

     a->pred->next=b;

     b->next->pred=a;

     b->next=a;

     a->pred=b;

     if(a->next==NULL) {xe=a;e=a;}

     p=0;

    }

    a=a->next;

   }                               //for while, прямий напрямок

 }

 else //if(napz) зворотній напрямок

 {

   a=xe;      p=1;

   while(a!=NULL)

   {

    if(((a->zn)<(a->pred->zn))&&(a->next==NULL))

    {

     b=a->pred;

     a->pred=b->pred;

     b->pred->next=a;

     b->pred=a;

     a->next=b;

     b->next=NULL;

     xe=e=b;     p=0;

    }

    if(((a->zn)<(a->pred->zn))&&((a->pred)!=NULL)&&(a!=NULL)&&(a->next!=NULL))

    {

     b=a->pred;

     a->pred=b->pred;

     b->next=a->next;

     a->next->pred=b;

     b->pred->next=a;

     b->pred=a;

     a->next=b;

     if(a->pred==NULL) {xh=a;h=a;}

     p=0;

    }

    a=a->pred;

   }                   //for while, зворотний напрямок

 }                     /for ELSE for if(napz)

 if (napr==0) napr=1; else napr=0; //зміна напрямку сортування

 if(p==1) return;

 sort(xh,xe,p,napr);

}

del(point *xh,point *xe)

{

 point *a;

 a=xh;

 while(xh->next!=NULL)

 {

   while(a->next->next!=NULL)

         a=a->next;

   free(a->next);

   a->next=NULL;

   a=xh;

 }

 free(a);

 cout<<"Список успішно вилучений з пам'яті.";

 getch();

}

void main()

{ struct time t;

    int t1,t2;

 clrscr();

 gettime(&t);

 t1=t.ti_hund;

 init(h,e);

 sort(h,e,0,1);

 gettime(&t);

 t2=t.ti_hund;

 printf("\nвремя виконання сортування %d секунд \n",t2-t1);

 viv(h,e);

 getch();

 del(h,e);

}

5.5.2 Текст програми. Сортування статичних структур даних

#include<stdlib.h>

#include<conio.h>

#include<dos.h>

#include<stdio.h>

#define n 500              //кількість елементів у масиві

int a[5];                       //масив, вміст якого буде впорядковуватися

void input()

{

      int i;

      randomize();

      for(i=0; i<n; i++)

      {

         a[i]=random(99);

         printf("%d  " ,a[i]);

      }

      printf("\n");

     }

     void vivod()

{

      int i;

      for(i=0; i<n; i++)

           printf("%d  " ,a[i]);

      printf("\n");

     }

void sort()

{

  int  i,j,t;

  int key; 

  key=1;           // key – ключ, дорівнює false, якщо не було перестановок

// (масив відсортований)

  for (i=1; i<n-1;i++)

  {

       if (!key)  break;

       key=0;

      for (j=i; j<n-i;j++)

         if (a[j]>a[j+1])

        {

             key=1;

             t=a[j]; a[j]=a[j+1]; a[j+1]=t;

         }

      for (j=n-i;i;i--)

      if (a[j]<a[j-1])

     {

          key=1;

          t=a[j]; a[j]=a[j-1]; a[j-1]=t;

      }

   }

}

void main()

{ struct time t;

    int t1,t2;

clrscr();

input();

gettime(&t);

t1=t.ti_hund;

sort();

gettime(&t);

t2=t.ti_hund;

printf("\nвремя виконання сортування %d секунд \n",t2-t1);

vivod();

getch();

}

7.  Результати роботи програм:

а) з динамічним набором даних:

Ініціалізація

73  33  92  17  27

Час виконання сортування  4  сек

17  27  33  73  92

Список успішно вилучений з пам'яті.

б) зі статичним набором даних:

73  33  92  17  27

Час виконання сортування  11  сек

17  27  33  73  92

Висновок:  Отримані результати дають можливість зробити висновок, що шейкерне сортування динамічних структур даних виконується швидше ніж статичних.