4878

Сортировка внешних данных. Сортировка прямым слиянием

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-28

62 KB

22 чел.

Сортировка внешних данных. Сортировка прямым слиянием.

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

Рассмотрим процедуру слияния двух отсортированных последовательностей A и B размера Na и Nb соответственно в новую последовательность C длины Na+Nb. Суть процедуры заключается в повторяющемся выборе элемента, наименьшего из двух имеющихся в началах исходных массивов, и переносе этого элемента в конец выходной последовательности:

/ Функция реализуеут слияние массивов A и B размеров

// sizeA и sizeB в выходной массив C

void merge( const double * A, int sizeA

         , const double * B, int sizeB

         , double * C

         )

{

  int a = 0, b = 0; // Индексы текущих элементов в массивах A и B

  while( a + b < sizeA + sizeB ) // пока остались элементы в массивах

  {

     if ( ( b >= sizeB ) || ( ( a < sizeA ) && ( A[a] <= B[b] ) ) )

     {

        // Копируем элемент из массива A

        C[ a + b ] = A[a];

        ++a;

     }

     else 

     {

        // Копируем элемент из массива B

        C[ a + b ] = B[b];

        ++b;

     }

  }

}

Таким образом, сортировку слиянием можно описать в виде алгоритма:

- разбиваем входной массив на пары и осуществляем слияние каждой пары, получая отсортированные блоки длины 2 (при нечетном количестве элементов для последнего элемента парного не будет). Заметим, что пару элементов легко отсортировать, просто обменяв их местами (при необходимости), не осуществляя «честное» слияние одиночных элементов;

- разбиваем имеющиеся отсортированные блоки на пары и выполняем слияние блоков в новые блоки большей длины;

- если число отсортированных блоков больше 1, переходим к предыдущему шагу.

// Функция сортирует массив A из size элементов

void mergeSort( double * A, int size )

{

   if ( size < 2 )

      return; // сортировать нечего

   if ( size == 2 ) // два элемента проще поменять местами,

   {                // чем делать слияние

       if( A[0] > A[1] )

       {

          double tmp = A[0];

          A[0] = A[1];

          A[1] = tmp;

       }

       return;

   }

   

   // Рекурсивно сортируем обе половины массива

   mergeSort( A         , size/2        );

   mergeSort( A + size/2, size - size/2 );

   double * B = new double[ size ]; // временный массив для слияния

   // Слияние половин

   merge( A, size/2

        , A + size/2, size - size/2

        , B);

   // Копируем результат слияния в исходный массив:

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

      A[i] = B[i];

   delete[] B; // удаляем временный массив

}

Оценивая количество сравнений, необходимых для сортировки слиянием, нетрудно получить оценку сложности алгоритма в O( N * log N ) в худшем случае, что говорит о том что этот алгоритм очень эффективен, однако его существенным недостатком является необходимость выделения значительного количества дополнительной памяти.

Сортировка внешних данных.

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

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

В подобных случаях применим другой подход. Допустим, во внешнем файле имеется последовательность из M элементов, которую необходимо отсортировать. Будем считать, что в оперативной памяти можно выделить место для хранения массива из N элементов, причем N много меньше M. Кроме того, будем считать, что в нашем распоряжении есть 4 «временных» файла A, B, C, D.

 На первом шаге прочитаем N записей из исходного файла в оперативную память и отсортируем их с помощью любой подходящей «внутренней» сортировки. Этот набор из N отсортированных записей перепишем во временный файл A. Затем прочитаем следующие N записей из исходного файла, отсортируем и поместим в файл B. Этот процесс продолжается, пока не кончатся элементы в исходном файле, причем отсортированные блоки по N элементов будем записывать поочередно в файлы A и B:

 

псевдокод

CreateBlocks (N)

{

  // N - размер создаваемых блоков

  currentFile = A

  while ( не достигнут конец входного файла )

  {

     read N записей из входного файла

     sort N записей

     if ( currentFile == A )

        currentFile = B

     else

        currentFile = A

     write N записей в currentFile

  }

}

 Теперь у нас есть 2 файла A и В, содержащие отсортированные блоки по N элементов, однако о порядке элементов в любых двух различных блоках сказать ничего нельзя. Далее начинаем с чтения первых половинок первых двух блоков в файлах A и B, по N/2 элементов из каждого, так, чтобы всего в памяти оказалось не более N элементов. Теперь применим процедуру слияния к считанным половинкам блоков в файл C. Когда обработка одного из блоков будет завершена, конец второго блока перепишем в файл C. После того, как слияние первых двух отрезков из файлов A и B будет завершено, следующие два отрезка сливаются в файл D. Далее процесс слияния продолжается с попеременной записью слитых отрезков в файлы C и D. В конце этого шага получим два файла, разбитые на отсортированные блоки длины 2N. Затем процесс повторяется, причем блоки читаются из файлов C и D, а слитые блоки (длины 4N) записываются поочередно в файлы A и B. Ясно, что в конце концов отрезки сольются в одну отсортированную последовательность в одном из файлов. Всего указанная процедура потребует log2( M / N ) проходов процесса слияния. Схема алгоритма слияния приведена ниже:

псевдокод

Merge (N)

{

  // N - размер исходных блоков

  size = S

  in1 = A

  in2 = B

  currentOut = C

  while ( не конец )

  {

     while ( блоки не кончились )

     {

        слить блок длины size из файла in1

           с блоком длины size из файла in2

           записав результат в файл currentOut

        if      ( currentOut == A )

           currentOut = B

        else if ( currentOut == B )

           currentOut = A

        else if ( currentOut == C )

           currentOut = D

        else if ( currentOut == D )

           currentOut = C

     }

     size = size * 2

     if ( in1 == A )

     {

        in1 = C

        in2 = D

        currentOut = A

     }

     else

     {

        in1 = A

        in2 = B

        currentOut = C

     }

  }

}


2

5

7

10

2

1

3

3

5

7

1

2

3

3

5

5

7

7

10

12

A

B

C


 

А также другие работы, которые могут Вас заинтересовать

78497. Сенсорное развитие детей подготовительной к школе группы в продуктивных видах деятельности (рисовании) 61.93 KB
  Предмет исследования: определение уровней сформированности восприятия цвета детьми подготовительной к школе группы в рисовании. Цель объект предмет позволили определить задачи исследования: Изучить психолого-педагогическую методическую литературу по проблеме сенсорного развития детей; Описать особенности восприятия цвета детьми дошкольного возраста; Определить уровни сформированности восприятия цвета детьми подготовительной к школе группы МДОУ № 93 г. Гипотеза исследования предполагает что целенаправленная систематическая работа по...
78498. Развитие креативности у детей младшего школьного возраста 81.32 KB
  Развитие креативности у детей младшего школьного возраста Актуальность темы исследования обусловлена современным общественным развитием стремлением психолого-педагогической науки преодолеть негативные последствия как социального так и образовательного экспериментирования. Таким образом проблема развития креативности детей младшего школьного возраста занимает большое место в современной психологии и является актуальной. Цель: исследование специфики креативности детей младшего школьного возраста. Предмет исследования: процесс развития...
78499. Развитие креативности младших школьников в условиях игровой деятельности 123.53 KB
  Развитие креативности младших школьников в условиях игровой деятельности Актуальность исследования проблемы креативности детей младшего школьного возраста обусловлена необходимостью развития творческих качеств личности созданием условий для формирования основных компонентов творческого мышления. Задача развития креативности общей способности к творчеству стоит и перед первой образовательной ступенью начальной школой. Развитие креативности имеет свои особенности в каждом возрастном периоде причем различные факторы влияющие на...
78500. Арт-техники в практике индивидуальной работы психолога с подростками 1.03 MB
  Рисунок который был сделан на первой встрече называется Мое настроение рисунок. Кате сначала было сложно включиться в работу но когда она сосредоточилась то быстро изобразила рисунок на предложенную тему. Она работала старательно и помощи ей не потребовалось в течение всего занятия она ясно поняла что и как надо сделать. Рисунок полученный в результате был очень темным и скудным по своей экспрессии и имел диагностический характер.
78501. Влияние научно – исследовательской деятельности старшеклассников на развитие креативности 43.82 KB
  Влияние научно исследовательской деятельности старшеклассников на развитие креативности Креативность является сравнительно новой психологической характеристикой появившейся в психологии в начале 50х гг. Исследования креативности за рубежом начались раньше чем в России. Активно разрабатываются и адаптируются западные диагностические методики измерения креативности на российских выборках. Исследование креативности и организации школьных научных обществ с различных точек зрения больше носит теоретико-эмпирический характер и имеет...
78502. Развитие креативности в старшем школьном возрасте 67.58 KB
  Развитие креативности в старшем школьном возрасте На современном этапе в российском обществе в социально-экономической сфере науке технике происходят глобальные изменения. Научный интерес вызывают концепции креативности Дж. Цель исследования: изучение специфики и особенностей развития креативности в старшем школьном возрасте. Предмет исследования процесс развития креативности в старшем школьном возрасте.
78503. Развитие художественного интереса учащихся старших классов на материале музееведения 382.5 KB
  Вся идеология работы с подрастающим поколением должна строиться на культуре, традициях, эстетическом воспитании и художественном развитии. Очень важно, чтобы подрастающее поколение совершенствовалось и развивалось не только в музыкальном, литературно-художественном плане
78505. Психологические факторы готовности студентов к развитию интеллектуальной сферы школьников 53.43 KB
  В современных условиях интеллектуальному развитию школьников придаётся особое значение наряду с другими развивающими целями и задачами обучения. Развитие интеллектуальной сферы школьников рассматривается многими исследователями как условие пронизывающее весь учебный процесс. В этой связи своевременным становится вопрос о специальной подготовке будущих учителей к работе по развитию интеллектуальной сферы школьников.