« Структуры данных и алгоритмы. Теория. Введение Структуры данных и алгоритмы. Теория. Усовершенствованные алгоритмы сортировки »

Структуры данных и алгоритмы. Теория. Работа с массивами. Сортировки и поиск.

January 2, 2007

Работа с массивами. Сортировки и поиск. Массив это самая известная из простейших структур данных и представляет собой множество величин, каждая из которых имеет один и тот же тип, такой тип называют базовым. Массивы различаются по размерности. Бывают одномерные массивы (они же вектора), двумерные, трехмерные и так далее. Количество размерностей массива ограничивается возможностями конкретного компилятора языка программирования и здравым смыслом, в практических задачах достаточно трудно найти ситуацию, когда будет необходимо создавать массив размерностью более чем 4 измерения.

Технически объявление массива различается для разных языков программирования, однако для большинства из них характерны следующие особенности:
  • указывается базовый тип элементов массива;
  • указывается количество измерений массива и размер по каждому измерению;
  • размер массива должен быть известен на этапе разработки программы и в дальнейшем не может изменяться (есть языки, для которых данное правило не абсолютно, например visual basic, java);
  • возможно, совместить объявление массива и его инициализацию (присвоение элементам массива конкретных величин).

Пример объявления массива:
Pascal C/C++ Java
Var arr : array [1..10] of real; Double arr [10][10]; Byte barr = new byte [10000];
Массив представляет собой структуру данных со случайным доступом, т.е. можно обратиться к его элементам в произвольном порядке, для обращения к элементу следует использовать индекс (или порядковый номер) элемента, количество индексов равно количеству измерений массива. Индексы массива принадлежат классу скаляров, для адресации используют целые числа, а, следовательно, номера элементов могут вычисляться по некоторому закону. При вычислении индексов всегда следует проявлять повышенную осторожность, возможен выход за границы допустимого диапазона. Конкретное поведение системы зависит от языка программирования и настроек компилятора и может варьироваться от пренебрежения допущенной ошибкой (в таком случае происходит обращение к произвольному фрагменту оперативной памяти с возможным уничтожением хранящейся там информации), так и контроль за выполняющимися действиями и в случае выхода за пределы генерации ошибки времени исполнения. Языки программирования, обладающие средствами обработки исключений, могут обрабатывать подобные ситуации наиболее изящно (c++, java, delphi).

Над массивами может выполняться целый класс операций (разбиения, слияния, трансформация) однако наибольший интерес для нас представляют методы упорядочения хранимой в массивах информации – сортировки. Цель применения сортировки – оптимизация процесса последующего поиска элементов массива согласно заданному критерию, в общем случае уже доказано, что в среднем трудоемкость операции поиска элемента в неупорядоченном массиве порядка n/2, где n – количество элементов массива, для упорядоченного же массива трудоемкость порядка log2n.

Выделяют различные алгоритмы сортировки. Основное разделение идет в зависимости от объемов сортируемой информации. В том случае если весь набор данных подлежащих обработке можно разместить одновременно в оперативной памяти компьютера, т.е. существует возможность получить произвольный доступ к любому элементу последовательности, то говорят о внутренней сортировке. В отдельных ситуациях данное требование не выполняется, например, при выполнении сортировок очень больших объемов информации, которые хранятся на внешних носителях. В подобном случае, когда доступ к сортируемым данным выполняется последовательно, т.е. в том случае если выделен элемент I и необходимо выполнить переход к элементу i-1 то требуется начать поиск с самого начала последовательности. Итак, такой тип сортировки называется внешним.

Прежде чем мы начнем рассмотрение основных видов внутренних сортировок, имеет смысл определиться с понятием ключей сортировок. В общем случае каждый элемент массива представляет собой некоторый комплексный объект, или нечисловой скаляр. Таким образом, необходимо решить вопрос о критерии упорядочения. Необходимо ввести правило сравнения двух элементов массива. Положим, что существует некоторая функция f, которая является отображением каждого элемента множества X (множество значений которые могут принимать элементы массива) на числовую ось R. в таком случае мы будем говорить, что элементы массива упорядочены по ключу f в том случае если выполняется условие: 
 F(x(1)) < F(x(2)) < F(x(3)) < … F(x(I - 1)) < F(x(i)) < … < F(x(n))
Общепринятым является сопоставление массиву сортируемых элементов массива ключей, которые вычисляются с помощью отображения F. Подобный прием имеет целью уменьшить накладные расходы на вычисление значения отображения F при выполнении каждой операции сравнения элементов при сортировке.

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

Метод сортировки является устойчивым, если в процессе сортировки элементы с одинаковыми значениями ключа не подвергаются перестановке.

Рассматриваемые далее алгоритмы сортировки следует рассматривать также с точки зрения затрат на время исполнения. При выполнении подобного анализа следует использовать следующие 4 критерия:
  1. какова средняя скорость сортировки;
  2. какова скорость сортировки в наилучшем и наихудшем из случаев;
  3. естественно ли его поведение;
  4. выполняется ли перестановка элементов с одинаковыми ключами.

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

Естественность поведения определяется количеством действий, которые необходимо выполнить в том случае, когда массив уже упорядочен или когда он упорядочен в обратном порядке. Очевидно, что поведение будет естественно именно в том случае, когда в первом случае будет выполняться минимальное количество действий, а во втором максимальное.

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

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

Пузырьковая сортировка. Сортировка методом прямого обмена.



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



Смысл пузырьковой перестановки заключается в сравнении двух рядом распложенных элементов и в случае необходимости перестановки их местами. Очевидно, что количество один проход по массиву не может упорядочить все элементы. Действительно за один проход элемент массива поднимается в направлении движения, совпадающем с направлением сортировки до необходимой позиции (уровня), если же направления не совпадают, то элемент перемещается только на одну позицию. Поэтому в простейшем варианте подобная сортировка будет выглядеть так. 
  1. char ars [] =  {'z' , 't' , 'a' , 'c' , 'e' , 'f' , 'b' , 'l'};
  2. int n = sizeof (ars) / sizeof (char);
  3. printf ("---- Before -----\n");
  4. for (int i=0; i < n; i++)
  5.    printf ("%c\t" , ars [i]);
  6. printf ("\n");
  7.  
  8. for (int i=1; i < n; i++)
  9.    for (int j=n - 1; j >=i; j--)
  10.       if (ars [j] > ars [j-1]){
  11. 	char t = ars [j];
  12. 	ars [j] = ars [j-1];
  13. 	ars [j-1] = t;
  14.       }
  15.  
  16. printf ("\n---- After -----\n");
  17. for (int i=0; i < n; i++)
  18.    printf ("%c\t" , ars [i]);

Сортировка методом прямого включения



Основная идея данного алгоритма заключается в том, что массив сортируемых объектов условно разбивается на две части: отсортированную и не отсортированную. На каждом шаге, начиная с i=2 (т.е. со второго элемента массива) мы из исходной последовательности извлекаем один элемент и перемещаем его в готовую (отсортированную) половину последовательности в соответствующую позицию так чтобы упорядоченность массива не нарушилась. 
  1. int arr [] = {1 , 3 , 2 , 7 , 5 , 8 , 0 , 4 , 6 , 9};
  2. int n = sizeof (arr) / sizeof (int);
  3. for (int i=1; i< n; i++){
  4.   int tmp = arr [i];
  5.   int j;
  6.   for (j=i - 1; j >=0 && arr [j] > tmp; j--)
  7.      arr [j + 1] = arr [j];
  8.      arr [j + 1] = tmp;
  9. }
  10.  
  11. printf ("\n---- After -----\n");
  12. for (int i=0; i < n; i++)
  13.   printf (“%4d” , arr [i]);
Обратите внимание на вложенный цикл по “j”. Условием его завершения будет либо ситуация когда мы с выделенным элементом дошли до начала отсортированной последовательности не найдя ни одного элемента который бы был меньше, чем выделенный, а следовательно новый элемент должен быть вставлен в самое начало ряда. Либо как второй вариант цикл будет завершен, когда будет найден такой элемент номер “j” который оказался больше чем выделенный, а, следовательно, после него в позицию “j+1” необходимо поместить выделенный элемент.

Сортировка методом прямого выбора



Данный алгоритм сортировки основан на многократном выполнении следующего набора шагов:
  1. в исходном массиве находится элемент с наименьшим значением ключа F(x);
  2. найденный элемент меняется местами с самым первым элементом;
  3. эти два шага повторяются многократно для оставшейся неупорядоченной части массива, начиная со второго, потом третьего и так далее до тех пор, пока мы не дойдем до конца массива и не отсортируем его целиком.

  1. int arr [] = {1 , 3 , 2 , 7 , 5 , 8 , 0 , 4 , 6 , 9};
  2. int n = sizeof (arr) / sizeof (int);
  3. for (int i=0; i< n; i++){
  4.    int posMax = i;
  5.    for (int j=i + 1; j < n; j++)
  6.      if (arr [j] > arr[posMax])
  7. 	posMax = j;
  8.    int tmp = arr [posMax];
  9.    arr [posMax] = arr [i];
  10.    arr [i] = tmp;
  11. }
  12.  
  13. printf ("\n---- After -----\n");
  14. for (int i=0; i < n; i++)
  15.    printf (“%4d” , arr [i]);

Шейкерная сортировка



Для алгоритма прямого обмена (пузырьковая сортировка) естественным усовершенствованием является алгоритм шейкерной сортировки. В основе данного алгоритма лежат следующие положения. Следует отказаться от жестко заданного числа повторений внешнего цикла, рассчитанного, по сути, на наихудший случай, внешний цикл должен был быть завершен в том случае, если во время выполнения внутреннего цикла не была выполнена ни одна перестановка. Однако такое усовершенствование не является решающим, как дальнейшее ее развитие можно предложить сохранять историю на каком именно шаге было выполнена последняя перестановка и следовательно при последующем выполнении внутреннего цикла не имеет смысла исследовать элементы находящиеся дальше и следовательно заведомо являющимися упорядоченными. Дальнейшее развитие алгоритма простого обмена приводит непосредственно к идее шейкерной сортировки: необходимо чередовать направления прохода внутреннего цикла, таким образом можно компенсировать «ассиметричность» перемещения элементов по направлению и против движения.

Задание: попытайтесь самостоятельно реализовать алгоритм сортировки с помощью шейкерного метода.

Сортировка слиянием



Метод сортировки слиянием не отличается высокой скоростью выполнения, однако заслуживает внимания из-за использования сходных идей при выполнении внешней сортировки. В данном методе мы предположим существование двух массивов каждый из которых уже отсортирован по возрастанию. Наша цель состоит в том, что необходимо “слить” эти два массива (назовем их A, B) в результирующий (C) так, чтобы этот третий массив был отсортирован по возрастанию. Алгоритм данного метода может быть кратко изложен так:
  1. необходимо взять из каждого из массивов самый первый элемент (очевидно, что это два самых маленьких элемента которые вообще есть в наших двух массивах) и наименьший из них поместить в результирующий.
  2. в том массиве, откуда мы изъяли один элемент предположить что первым будет тот который находился ранее на второй позиции, по сути мы сдвигаем элементы на одну позицию влево.
  3. необходимо повторять шаги 1,2 до тех пор, пока в каком либо из массивов не закончатся числа. Предположим, что это был массив A.
  4. в результирующий массив C необходимо поместить все оставшиеся из массива A.

Задание: по приведенному здесь описанию вам необходимо самостоятельно реализовать алгоритм сортировки слиянием.

Поиск элемента в массиве



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

Задача поиска позиции элемента наиболее проста и имеет два решения:

1) Простой перебор. В данном случае необходимо организовать цикл перебора всех элементов данного массива начиная от первого до последнего и проверять их на предмет совпадения с искомой величиной. Как только было найдено совпадение, поиск может быть прекращен (если конечно не стоит задача поиска всех вхождений искомого элемента в массив). Очевидно, что насколько данный алгоритм прост настолько он и не эффективен. Зависимость от времени поиска линейная. 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. void main (void){
  4.    int arr [] = {2, 4, 1, 6, 7 , 8 , 5 , 9 , 0 , 3};
  5.    int n = sizeof (arr) / sizeof (int);
  6.    int k = 6; // искомый элемент
  7.    for (int i=0; i < n; i++)
  8.      if ( k == arr [i]){
  9. 	printf ("element %d was found at %d position" , k , i);
  10. 	break;
  11.      }
  12. }
2) Существенно улучшить временные показатели поиска можно в случае, если исходный массив является упорядоченным. Тогда мы имеем право применить алгоритм бинарного поиска. Надо отметить, что метод половинного деления широко применяется также в области вычислительной математики для поиска нулей функции. Основные положения алгоритма можно представить согласно следующей схеме:
  1. исходный интервал [a,b] разбивается на две половины путем выделения центрального элемента “c”.
  2. если центральный элемент “c” совпадает с искомым “k”, то поиск завершен.
  3. если искомый элемент “k” меньше чем “c”, то очевидно, что поиск дальше имеет смысл вести только в первой половине отрезка [a,c).
  4. если же элемент “k” строго больше чем “c”, то поиск на следующем шаге будет продолжен на отрезке (c, b].

Несмотря на то, что решение формулируется в терминах рекурсии, применение ее будет неоправданно из-за больших накладных расходов, поэтому применяют итеративное решение. 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. void main (void){
  4.    int arr [] = {1, 2, 3, 4, 5 , 6 , 7 , 8 , 9 , 10};
  5.    int n = sizeof (arr) / sizeof (int);
  6.    int k = 7; 
  7.    int L = 0, R = n-1;
  8.    int m;
  9.    while ( L <= R){
  10.       m = (L+R)/2;
  11.       int med = arr [m];
  12.       if (med == k)
  13. 	break;
  14.       else
  15. 	if ( med > k)
  16. 	   R = m - 1;
  17. 	else
  18. 	   L = m + 1;
  19.    }
  20.  
  21.    if (L > R)
  22. 	printf ("element wasnt found");
  23.    else
  24. 	printf ("element was found at %d position" , m);
  25. }


Эвристические методы последовательного поиска



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

Примечание: для получения информации о связных списках необходимо обратиться к последующему разделу «Динамические структуры данных».

Задание: вам необходимо создать класс “ValuedArray”. данный класс будет представлять собой надстройку над обычным массивом, но при этом каждому из элементов массива должен быть поставлен в соответствие специальный счетчик, показывающий относительную частоту с которой данный элемент запрашивается. Также необходимо добавить метод “reorder”, который должен будет выполнять такую перестановку местами элементов, чтобы в начале массива находились именно те значения, которые пользуются “наибольшим спросом”. Для доступа к элементам будет использоваться метод “findPosition (int Value)” данный метод должен получать значение искомого элемента и возвращать его позицию, если элемент не был найден, то следует возвращать “-1”. Добавление элементов выполянется с помощью метода “appendElement (int Value)”.

Задача поиска k-ого наименьшего элемента



Поставленная задача уже упоминалась в разделе, посвященном алгоритму быстрой сортировки. Если вы обратитесь к той главе, то вспомните, что мы для повышения быстродействия алгоритма quicksort элемент “m”, который мы выбирали и использовали для разделения массива на две части (элементы меньшие и элементы большие, чем “m”) должен был являться медианой. Медиана, как известно, это элемент ряда, который в точности больше или равен половине элементов последовательности, а, следовательно, меньше или равен другой половине элементов. Задача поиска медианы тесно взаимосвязана с задачей сортировки, так если у нас есть отсортированный массив, то медианой будет являться элемент, который находится в его центре. Задача поиска медианы является частным случаем задачи поиска k-ого наименьшего элемента массива, в случае k=n/2. Алгоритм поиска k-ого наименьшего элемента был предложен Ч.Хоаром и основан на применении метода разделения. В качестве разделяющего элемента берется значение a[k]. После выполнения разделения, очевидно, что слева от разделяющего элемента все числа будут меньше или равны ему, а справа все соответственно большие или равные. Также после окончания разделения мы будем знать о том, где прошла граница данного разделения. На приведенном ниже изображении граница определяется положением указателей “i,j”, I – граница, пришедшая со стороны left, j – right краев массива. При этом возможны три варианта:
  1. положение границы меньше чем k, следовательно, дальнейший поиск следует вести в отрезке (i,R).
  2. положение границы больше чем k, в таком случае поиск будет проведен в отрезке (L, j).
  3. если же j 


  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. void main (void){
  4.    int arr [] = {1, -9, -7, -8, 5 , 3 , 7 , 2 , 9 , 10};
  5.    int n = sizeof (arr) / sizeof (int);
  6.    int k = 7; // необходимо найти k-ый наименьший элемент
  7.    int L = 0, R = n-1, i , j;
  8.    while (L < R){
  9.      i = L ;
  10.      j = R;
  11.      while (i < j){
  12. 	while (arr [i] < arr [k]) i++;
  13. 	while (arr [j] > arr [k]) j--;
  14. 	if ( L <= R){
  15.     	   int tmp =  arr [i];
  16. 	   arr [i] = arr [j];
  17. 	   arr [j] = tmp;
  18. 	   i++; 
  19. 	   j--;
  20. 	}
  21.     }
  22.  
  23.     if (j < k) L = i;
  24.     if (i > k) R = j;
  25. }
  26.  
  27. printf ("Results:\n");
  28. printf ("i = %d j = %d k-min = %d", i , j  , arr[(i+j)/2]);
  29. }
Задание: вам необходимо будет повторно реализовать алгоритм сортировки методом вставки описанный в предыдущей главе, однако теперь для поиска позиции вставки нового элемента следует применять алгоритм двоичного поиска.

Categories: Структуры данных и алгоритмы

« Структуры данных и алгоритмы. Теория. Введение Структуры данных и алгоритмы. Теория. Усовершенствованные алгоритмы сортировки »