Разработать программы сортировки статического и динамического наборов данных по алгоритму сортировки шейкера.
6.5.1 Текст программы. Сортировка динамических структур данных
#include<iostream.h> //cout
#include<stdlib.h> //random, malloc, free
#include<conio.h> //getch
#include<stdio.h>
#include<dos.h>
#define n 500
struct point
{
int zn;
point *pred;
point *next;
} *h,*e;
//Инициализация значения списка
int init(point *xh,point *xe)
{
int i;
point *a,*b;
randomize();
h=(point *)malloc(sizeof(point));
h->zn=random(100);
h->next=(point *)malloc(sizeof(point));
h->pred=NULL;
a=h;
cout<<"Инициализация\n";
cout<<h->zn<<"\n";
for(i=2;i<=n;i++)
{
b=a;
a->next=(point *)malloc(sizeof(point));
a=a->next;
a->zn=random(100);
cout<<a->zn<<"\n";
a->pred=b;
}
a->next=NULL;
e=a;
return (і);
}
void viv(point *xh,point *xe) //Выдача содержимого списка.
{
point *a;
cout<<"Вывести через NEXT\n";
a=h;
while(a!=NULL)
{
cout<<a->zn<<" ";
a=a->next;
}
}
void sort(point *xh,point *xe,int p,int napr)
{
int i;
point *a,*b;
if(napr) //прямое направление
{
a=xh;
p=1;
while(a!=NULL)
{
if(((a->zn)>(a->next->zn))&&(a->pred==NULL))
{
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);
}
Текст программы. Сортировка статических структур данных
#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();
}
Результаты работы программы
а) с динамическим набором данных:
Инициализация
73 33 92 17 27
Время выполнения сортировки 4 сек
17 27 33 73 92
Список успешно удален из памяти.
б) со статическим набором данных:
73 33 92 17 27
Время выполнения сортировки 11 сек
17 27 33 73 92
