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

ЛАБОРАТОРНА РОБОТА №5

5.1. Тема: Сортування.

5.2. Мета роботи: Ознайомлення з алгоритмами сортувань статичних та динамічних структур даних.

5.3. Теми для попередньої роботи

5.3.1. Статичні структури даних

5.3.2 Динамічні структури даних

5.3.3. Пошук.

5.3.4. Сортування

-

5.4. Індивідуальне завдання

Розробити програму,  що дозволяє виконати сортування статичного та/або динамічного набору даних.  У програмі обов’язково виконати порівняння алгоритмів сортування за часом.

Індивідуальне завдання вибрати з таблиці 1 з урахуванням парності/непарності номера студента у журналі групи (N) наступним чином:

1). У таблиці 1 по значенню N визначити алгоритм (або алгоритми) сортування.

2).  Для непарного N  реалізувати вказаний алгоритм сортування на різних наборах даних (статичному та динамічному);

      для парного N реалізувати два алгоритми сортування на одному з наборів (статичному або динамічному), причому тип набору визначити так:

                                   непарне число,  то - статичний набір;

             як що N div 3 =  

                                               парне число,  то - динамічний набір.

Таблиця 1.

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Номер сортування	13	1 10	12	3 7	11	4 8	10	5 9	9	6 2	8	7 4	7	8 1	6

16	17	18	19	20	21	22	23
9 13	5	2 3	4	11 13	3	10 6	2

де N – номер студента у журналі.

1.  Пірамідальне сортування.

2.  Модифікація бульбашкового сортування з ознакою.

3.  Бульбашкове сортування з запам'ятовуванням місця останньої перестановки.

4.  Шейкер – сортування.

5.  Сортування Шелла.

6.  Сортування двійковими вставками.

7.  Бульбашкове сортування вставками.

8.  Турнірне сортування.

9.  Сортування простою виборкою.

10.   Сортування Хоара.

11.  Сортування вибором (пошук min та max в одному проході).

12.  Порозрядне цифрове сортування.

13.  Сортування попарним злиттям.

6.5.Типове завдання.

Розробити програми сортування статичного і динамічного наборів даних згідно із алгоритмом сортування Шейкера.   

5.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))