Разработки программ

Разработка эффективных алгоритмов внешней сортировки существенно сложнее, чем алгоритмов внутренней сортировки, при которой сортируемый массив полностью помещается в оперативную память. Трудности внешней сортировки вызваны, в частности, необходимостью учета параметров устройств внешней памяти. Разработка такой программы будет хорошим применением для функций работы с файлами.

Предлагаемая внешняя сортировка не является лучшей среди таких сортировок. К достоинствам этого алгоритма можно отнести ясность и простоту. В рамках данного алгоритма предполагается, что сортируемый массив разбит на К блоков, из них К-1 одинаковой длинны, а последний может быть меньше. Предполагается что в оперативной памяти помещается два любых блока. Сортировка заключается в том, что в оперативную память загружаются два различных блока и сортируются с помощь внутренней сортировки как единый массив. Таким образом, сначала загружается первый блок и сортируется с К-1 блоком (с 2...К). Затем загружается второй блок и сортируется с К-2 блоком (с 3...К) и т.д.

Предлагаемая программа внешней сортировки иллюстрирует указанный алгоритм. Сначала она создает файл случайных чисел с помощью функций randomize() и random(). Прототипы этих функций описаны в файле <stdlib.h>. Функция randomize() инициализирует датчик случайных чисел, а функция int random(int num) возвращает случайное число от 0 до num-1. В программе задан массив из 102 чисел типа double, максимальный размер блока равен 10 чисел. Таким образом, имеется 11 блоков.

Конечно, такой пример рассмотрен только для иллюстрации предлагаемого алгоритма. После создания файла текущий указатель файла перемещается в конец файла и с помощью функции ftell() находим длинну файла в байтах, количество блоков kolb, и длинну последнего блока oct в байтах. Напомнию, последний блок может быть короче остальных (их длинна в байтах равна MAX). Затем загружается i-й блок и j-й блок с помощью функций fseek и fread. После внутренней сортировки этих блоков (с помощью сортировки прямым выбором, функция sort) онизаписываются на диск.

После окончания сортировки внешний массив выводится на экран. Число операций будет порядка K²*MAX².

#include <stdlib.h>

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

#define MAX 10

/*Внешняя сортировка*/

void main () {

FILE *in;

long li,lj,oct,i,n,j,kolb,dl,t,dlb;

double v,* buf;

void sort (double *, int n);

clrscr();

n=102; dlb=sizeof(double);

in=fopen("file.chs","w+b");

randomize();

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

v=random(1000);

prinf("%4.0lf",v);

fwrite(&v,dlb,1,in);

}

dl=dlb*MAX;

fseek(in,0L,SEEK_END);

kolb=ftell(in)/dl;

oct=n-kol*MAX;

if(oct!=0) kolb++; else oct=MAX;

buf=(double *)malloc(2*dlb);

if(!buf){printf("Недостаточно памяти!");exit(0);}

printf("/n");

for(i=1;i<=kolb;i++) {

fseek(in,dl*(i-1),SEEK_SET);

li=MAX;

fread(buf,dlb,li,in);

for(j=i+1;j<=kolb;j++) {

fseek(in,dl*(j-1),SEEK_SET);

if(j!=kolb) lj=MAX; else lj=oct;

fread(buf+li,dlb,lj,in);

sort(buf,li+lj);

fseek(in,dl*(j-1),SEEK_SET);

fwrite(buf+li,dlb,lj,in);

}

fseek(in,dl*(i-1),SEEK_SET);

fwrite(buf,dlb,li,in);

}

fseek(in,0L,SEEK_SET);

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

fread(&v,dlb,1,in);

printf("%4.0lf",v);

}

fclose(in);

getch();

}

void sort(double *buf,int n) {

int i,j,k; double p;

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

k=i;

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

if(buf[j]<buf[k]) k=j;

if(k!=i) {

p=buf[k]; buf[k]=buf[i]; buf[i]=p;

}

}

}

}