Сортировка и поиск. Алгоритм сортировки подсчётом. Описание алгоритма решения. Описание баз данных. Текст программы

Министерство образования Российской Федерации

Тульский государственный университет

Кафедра прикладной математики и информатики

Базы данных и экспертные системы

Лабораторная работа № 2

Сортировка и поиск.

Выполнил студент гр. 520212                                                                    

Принял                                                                                                        

Тула-2004.

Постановка задачи.

Необходимо запрограммировать алгоритм сортировки подсчётом. Тип информационной структуры – линейный список с последовательным распределением.

Описание алгоритма решения.

Данный алгоритм применим в случае если каждый из элементов последовательности – целое положительное число в известном диапазоне (не превосходящее заранее известного числа). Идея алгоритма в том, чтобы для каждого элемента сортируемой последовательности предварительно подсчитать сколько элементов входной последовательности меньше текущего. После чего записать текущий символ напрямую в выходную последовательность в соответствии с этим числом.

Описание баз данных.

При решении задачи входная и выходная последовательности были реализованы в виде линейных односвязных списков.

Текст программы.

// lab2.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <stdio.h>

#include <time.h>

#include "iostream"

using namespace std;

template <class xType2>

struct Element

{

int count;

xType2 value;

Element *Next;

};

template <class xType1>

class LinearList

{

private:

Element <xType1>*begin;

Element <xType1>*last;

public:

LinearList(int number);//количество элементов в очереди

void OutAll ();

xType1 OutCertain(int i);//выводит из существующей очереди элемент i

void Push (int i,xType1 val);//вставить в существующую очередь на место i, элемент со значением val

~LinearList();

};

template <class xType1> LinearList<xType1>::LinearList (int number)

{

Element <xType1>*a;

int count2 = 1;

begin  = new Element<xType1>;

begin->count = count2++;

begin->Next = NULL;

begin->value = 0;

last = begin;

for (int i = 0; i < number-1; i++)

{

a = new Element<xType1>;

a->count = count2++;

a->Next = NULL;

a->value = 0;

last->Next = a;

last = a;

}

srand( (unsigned)time( NULL ) );

}

template <class xType1> LinearList<xType1>::~LinearList()

{

while(begin!=NULL)

{

if (begin->Next != NULL) last = begin->Next; else last = NULL;

delete begin;

begin = last;          

}

}

template <class xType1> void LinearList<xType1>::OutAll ()

{

last = begin;

while (last!=NULL)

{

cout<<last->value<<"  ";

last = last->Next;

}

}

template <class xType1> xType1 LinearList<xType1>::OutCertain(int i)

{

last = begin;

while (last->count != i)

last = last->Next;

return last->value;

}

template <class xType1> void LinearList<xType1>::Push(int i,xType1 val)

{

last = begin;

while (last->count != i)

last = last->Next;

last->value = val;

}

int _tmain(int argc, _TCHAR* argv[])

{

int k = 100;//заранее известное число, элементы очереди не могут его превосходить

int size = 20;

LinearList <int>a(size);//в a находится исходная последовательность

LinearList <int>b(size);//в b отсортированная

LinearList <int>c(k);

for (int i = 1; i <= size; i++)

a.Push(i,rand()%k);

a.OutAll();

cout<<endl;

for (int j = 1; j <= size; j++)

c.Push(a.OutCertain(j),c.OutCertain(a.OutCertain(j))+1);

for (i = 2; i <= k; i++)

c.Push(i,c.OutCertain(i) + c.OutCertain(i-1));

for (j = size; j >=1 ; j--)

{

b.Push(c.OutCertain(a.OutCertain(j)),a.OutCertain(j));

c.Push(a.OutCertain (j),c.OutCertain(a.OutCertain(j))-1);

}

b.OutAll();

return 0;

}

Результаты работы программы.

59  73  23  73  31  44  45  93  74  26  15  84  34  18  26  34  72  57  24  1 

1  15  18  23  24  26  26  31  34  34  44  45  57  59  72  73  73  74  84  93