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

Быстрая сортировка состоит в том, что список В=< 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. Понятия очереди, стеков, связанных списков и деревьев.