Улучшенный алгоритм сортировки: быстрая сортировка, сортировка Шелла

Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn> реорганизуется в список B’,< K1 >,B", где В’ - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B’,< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B’ и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >.

Пример:

               9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26

               7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26

               3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26

               <3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52>

               3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52

               3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52

Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка.

Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B’ и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов.

Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.

               /*        быстрая сортировка        */

               double * quick(double *s,int low,int hi)

               {

                                    double cnt,aux;

                                    int i,j;

                                    if (hi>low)

                                     {

                                    i=low;

                                    j=hi;

                                    cnt=s[i];

                                                         while(i < j)

                                                        {

                                                                            if (s[i+1]<=cnt)

                                                                            {

                                                                                                 s[i]=s[i+1];

                                                                                                 s[i+1]=cnt;

                                                                                                 i++;

                                                                            }

                                                                            else

                                                                            {

                                                                                                 if (s[j]<=cnt)

                                                                                                 {

                                                                                                                     aux=s[j];

                                                                                                                     s[j]=s[i+1];

                                                                                                                     s[i+1]=aux;

                                                                                                 }

                                                                                                  j--;

                                                                            }

                                                        }

                                    quick(s,low,i-1);

                                                        quick(s,i+1,hi);

                                     }

                                    return(s);

               }

Здесь используются два индекса i и j, проходящие части массива навстречу друг другу. При этом i всегда фиксирует разделяющий элемент cnt=s[low], слева от которого находятся числа, не большие cnt, а справа от i - числа, большие cnt. Возможны три случая: при s[i+1]<=cnt; при s[i+1]>cnt и s[j]<=cnt; при s[i+1]>cnt и s[j]>cnt. По окончании работы i=j, и cnt=s[i] устанавливается на своем месте.

Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции quick (неявный стек).

Оценка среднего количества действий, необходимых для выполнения быстрой сортировки списка из N различных чисел, получена как оценка отношения числа различных возможных последовательностей из N различных чисел, равного N!, и общего количества действий C(N), необходимых для выполнения быстрой сортировки всех различных последовательностей. Доказано, что C(N)/N! < 2*N*ln(N).

Существенными в сортировках вставками являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент помест. Этим отличается СОРТИРОВКА ШЕЛЛА: исходный массив разбивается на n частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно, то есть

               0, m, 2m, 3m,...

               1, m+1, 2m+1, 3m+1,...

               2, m+2, 2m+2, 3m+2,...

Каждая часть сортируется отдельно с использованием алгоритма вставок. Затем выбирается меньший шаг, и алгоритм повторяется. Шаг может быть выбран равным степеням 2, например 64, 32, 16, 8, 4,2, 1. Последняя сортировка выполняется с шагом 1.

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

               #include

               #include

               #define MAXLINES 5000 // максимальное число строк

               char *lineptr[MAXLINES]; // указатели на строки

               int readlines(char *lineptr[], int nlines);

               void writelines(char *lineptr[], int nlines);

               void qsort(char *lineptr[], int left, int right);

                                    /* сортировка строк */

               main()

               {

                                    int nlines; /* количество прочитанных строк */

                                    if ((nlines = readlines(lineptr, MAXLINES)) >= 0)

                                    {

                                                        qsort(lineptr, 0, nlines-1);

                                                        writelines(lineptr, nlines);

                                                        return 0;

                                    }

                                    else {

                                                                            printf("ошибка: слишком много строк\n");

                                                                            return 1;

                                                        }

               }

 

 

44. Методы поиска: последовательный и двоичный поиск.

Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация, когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то

                                            n

  Max{А} = max{ Si, i=1,n }; Avg{А} = Pi Si.

                                           i=1

Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядкеих расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера.

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

  /* последовательный поиск без стоппера */

  #include

  main()

  {

    int k[100],v,i;

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

                                    scanf("%d",&k[i]);

                                    scanf("%d",&v);

                                    i=0;

             while(k[i]!=v && i<100) i++;

       if (k[i]==v) printf("%d %d",v,i);

        else printf("%d не найден",v);

  }

С использованием стоппера программу можно записать в виде:

  /* последовательный поиск со стоппером */

  #include

  main()

    {

                                    int k[101],v,i;

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

                                    scanf("%d",&k[i]);        //ввод данных

                                    scanf("%d",&v);

                                    k[100]=v;                 //стоппер

                                    i=0;

                                    while(k[i]!=v) i++;

                                if (i<100) printf ("%d %d",v,i);

                                       else printf ("%d не найден",v);

    }

Двоичный поиск

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

Нахождение элемента двоичным поиском осуществляется очень быстро. Max двоичного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg двоичного поиска равен log2(N). Недостаток двоичного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V – элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления двоичного поиска ключа V в списке К1,К2,...,К100.

/* Двоичный поиск */

#include

main()

  {

                                     int k[100],v,i,j,m;

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

                                     scanf("%d",&k[i]);

                                     scanf("%d",&v);

                                     i=0; j=100; m=50;

                                    while (k[m]!=v)

      {

        if (k[m] < v) i+=m;

         else j=m-i;

        m=(i+j)/2;

      }

     printf("%d %d",v,m);

  }

 

 

Основы файловой системы. Стандартные потоки. Указатель файла. Открытие файла. Закрытие файла.

Потоки

Потоки представляют собой удобный переносимый способ чтении и записи данных. Они обеспечивают гибкие и эффективные средства для ввода/вывода.

Поток - это байтовая последовательность, передаваемая в процессе ввода, которая управляется через указатель на поток.

Потоковый ввод/вывод - буферизированный: это означает, что блок данных фиксированного размера читается/пишется в файл не посредственно, а через временную область хранения (буфер).

Это повышает эффективность ввода/вывода, но будьте осторожны: данные, записанные в буфер, не появятся в файле или на устройстве, пока буфер не будет очищен. Всякое неуспешное завершение программы может вызвать проблемы. Потоковый ввод/вывод эффективен для символов и строк.

Основы файловой системы

Основным понятием, связанным с информацией на внешних устройствах ЭВМ, является понятие файла. Всякая операция ввода/вывода трактуется как операция обмена с файлами: Ввод- это чтение из файла в оперативную память; вывод - это запись из оперативной памяти в файл. Сначала нужно открыть поток перед выполнением каких-либо операций ввода/вывода, затем выполнить операции доступа (чтения/записи) и потом закрыть.

В языке Си файл - это байтовая последовательность, заканчивающаяся EOF.

В языке Си отсутствует понятие типа файла.

Указатель файла

Работа с файлами начинается с объявления указателя на поток:

FILE *имя_указателя;

FILE *fp;

FILE внутренняя C-структура данных языка Си,которая используется для работы с потоками и определена в stdio.h. Стуктура FILE содержит следующую информацию: указатель на буфер, указатель текущей позиции в потоке.

Открытие файла

Открыти файла возможно при помощи функции fopen(), синтаксис которой следующий:

               FILE *fopen(char *name, char *mode)

fopen возвращает указатель на структуру FILE. Строка name содержит имя файла. Строка mode определяет способ доступа. Если файл не может быть открыт по какой-либо причине, функция возвращает NULL.

Способы доступа включают:

               "r" - чтение,

               "w" - запись,

               "a" - добавление в конец.

Также способ доступа может включать:

               "t" - текстовый,

               "b" - бинарный.

Для открытия файла myfile.dat на чтение необходимо:

               FILE *stream, *fopen();

               /* описание потока и прототипа fopen */

               stream = fopen("myfile.dat","r");

Необходимо проверять, что файл открылся:

               if ((stream = fopen("myfile.dat", "r")) == NULL)

                                    { printf("Нельзя открыть %s\n", "myfile.dat");

                                                        exit(1);

                                     }

                                                  ......

Закрытие файла

Для того, чтобы закрыть файл, используется функция fclose. Ее синтаксис:

               fclose(FILE *stream)

Пример. Ввести матрицу из файла inputfile.dat.Файл входных данных имеет следующую структуру:

n - количество строк

m - количество столбцов

a a... a

...

a a... a,

где

n - количество строк

m - количество стобцов

a - элементы матрицы.

И вывести ее в файл outputfile.dat.

 

#include <stdio.h>
void main(){
               int A[100][100]; // массив 100х100
               int i,j; // индексы для перемещения по массиву
               int n; // кол-во строк
               int m; // кол-во столбцов
               FILE *fp;

 // открытие файла на чтение
if ((fp = fopen("inputfile.dat", "r")) == NULL)
{ printf("Нельзя открыть %s\n", "inputfile.dat");
return;
}
// ввод размеров матрицы
fscanf(fp,"%d",&n);
fscanf(fp,"%d",&m);
// ввод значений матрицы
for (i=0;i<n;i++)
for (j=0;j<n;j++){
fscanf(fp,"%d",&A[i][j]);
}
fclose(fp);
// открытие файла на запись
if ((fp = fopen("outputfile.dat", "w")) == NULL)
{ printf("Нельзя открыть %s\n", "outputfile.dat");
return;
}
// вывод значение матрицы
for (i=0;i<n;i++){
for (j=0;j<n;j++)
fprintf(fp,"%d ",A[i][j]);
fprintf(fp,"\n");
}
fclose(fp);

}

 

46. Форматированный ввод-вывод в файл.

 

47. Запись и чтение символов. Ввод/вывод строк. Стирание файлов.

Запись и чтение символа

Функции записи и чтения символа подобны fprintf и fscanf, только пишут и читают не в поток/из потока, а в строку/из строки:

               int sprintf(char *string, char *format, args..)

                   

               int sscanf(char *string, char *format, args..)

Пример:

               float full_tank = 47.0;

               float miles = 300;

               char miles_per_litre[80];

               sprintf(miles_per_litre,"Miles per litre = %2.3f", miles/full_tank);

Ввод/вывод строк

Стандартная библиотека содержит функцию fgets. В результате обращения

               fgets(line, maxline, fp)

следующая строка ввода (включая символ новой строки) считывается из файла fp в символьный массив line; самое большое maxline_1 символ будет прочитан. Результирующая строка заканчивается символом \0. Нормально функция fgets возвращает line; в конце файла она возвращает null.

Предназначенная для вывода функция fputs записывает строку (которая не обязана содержать символ новой строки) в файл:

               fputs(line, fp)

Очистка буфера потока

Функция fflush очищает буфер потока:

               fflush(FILE *stream)

 

48. Понятия очереди, стеков, связанных списков и деревьев.

Понятия очереди, стеков, связанных списков и деревьев В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Стек – это конечная последовательность некоторых однотипных элементов – скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило, изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >. Допустимыми операциями над стеком являются: - проверка стека на пустоту S=< >, - добавление нового элемента Sn+1 в конец стека - преобразование < S1,...,Sn> в < S1,...,Sn+1>; - изъятие последнего элемента из стека - преобразование < S1,...,Sn-1,Sn> в < S1,...,Sn-1>; - доступ к его последнему элементу Sn, если стек не пуст. Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху. Очередь – это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине). Двусторонняя очередь – это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов. Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами. Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией. Например, выражение                (6+8)*5-6/2в польской инверсной записи имеет вид                6 8 + 5 * 6 2 / -Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид               S = < >; <6>; <6,8>; <14>; <14,5>; <70>;                                    <70,6>; <70,6,2>; <70,3>; <67>.                                    Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.     float eval (float *m, int l)    { int p,n,i; float stack[50],c;  for(i=0; i < l;i++)  if ((n=m[i])<0)    { c=st[p--];       switch(n)       { case -1: stack[p]+=c; break;         case -2: stack[p]-=c; break;         case -3: stack[p]*=c; break;         case -4: stack[p]/=c;       }    }  else stack[++p]=n;  return(stack[p]); }Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1.", то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.                #include                typedef struct st      /* объявление типа STACK */               { char ch;               struct st *ps; } STACK;               main()               {                                    STACK *p,*q;                                    char a;                                    p=NULL;                                    do                 // заполнение стека                                    { a=getch();                                                        q=malloc(sizeof(STR1));                                                        q->ps=p; p=q;                                                        q->ch=a;                                    } while(a!= ’. ’);                                    do                 // печать стека                                    { p=q->ps;free(q);q=p;                                                        printf("%c",p->ch);                                    } while(p->ps!=NULL);               } Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47, 60> из 9 элементов. Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С. Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up.                /* слияние списков */               double *merge(double *s, int low, int up, int l)               {                                    double *b,*c,v;                                    int i,j,k;                                    b=calloc(l,sizeof(double));                                    c=calloc(up+1-l,sizeof(double));                                    for(i=low;i< low+l;i++)                                                                            b[i-low]=s[i];                                    for(i=0;i< up-l;i++)                                                                            c[i]=s[i+l+low];                                    v=(b[l]=(c[up-l]=(s[low+l-1]>s[up-1])? (s[low+l-1]+1): (s[up-1]+1)));                                    i=(j=0);                                    k=low;while(b[i]< v||c[j]< v){ if(b[i]< c [j]) s[k]=b[i++];else      s[k]=c[j++];k++;}return (s);}