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


 

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

35601. Понятие о геосинклиналях 15.47 KB
  В начальных стадиях развития Геосинклиналей преобладает погружение всей зоны и накопление внутри нее мощных толщ преимущественно обломочных и нередко основных эффузивных пород. В дальнейшем процессе развития Геосинклиналей усиливается интрузивная деятельность а в отдельных местах происходит образование складок завершающееся поднятием а затем новым погружением этих участков что обусловливает перерывы в осадконакоплении в различных местах. Заключительные этапы развития Геосинклиналей связаны с усилением складкообразования и обычно с...
35602. Этапы развития земной коры 15.45 KB
  Важным фактором развития Земли на этом этапе и несколько позднее по аналогии с Луной принимается предполагаемая метеоритная бомбардировка спровоцировавшая разогрев и интенсивный базальтовый вулканизм. На этом этапе развития началось расслоение Земли на оболочки ядро внутреннее и возможно внешнее мантию кору и атмосферу. Раннеархейский этап 4035 млрд.
35603. Ответы к зачету по геологии 113.87 KB
  Кювье применили палеонтологические методы определения возраста горных пород что позволило установить основные этапы развития Земли и земной коры. Основу геологических знаний дают полевые исследования местности где изучаются геологические породы особенности залегания слоев и геологических тел которые можно изучить в естественных обнажениях шурфах и искусственных карьерах. В витринах к данным стендам представлены образцы разнообразных микроразрывов зеркал скольжения кливажа складок разной формы различных пород. По занимаемому в составе...
35604. Физика. Модели в механике 2.06 MB
  Под воздействием тел друг на друга тела могут деформироваться т. Абсолютно твердым телом называется тело которое ни при каких условиях не может деформироваться и при всех условиях расстояние между двумя точками или точнее между двумя частицами этого тела остается постоянным. Любое движение твердого тела можно представить как комбинацию поступательного и вращательного движений. Вращательное движение это движение при котором все точки тела движутся по окружностям центры которых лежат на одной и той же прямой называемой осью вращения.
35605. Магнитики из гипса. Мастер-класс 760 KB
  Мастеркласс Вы видите эти магнитики на холодильник А знаете из чего они Ответ прост: из гипса. Итак нам понадобится: гипс; собственно сами магниты; формы для отливки; акриловые краски; универсальный клей. Где всё это искать Гипс как и магниты можно найти в магазинах для рукоделия.
35606. Магнитики на холодильник 26.5 KB
  Магнитики на холодильник могут наклеиваться с практической целью чтобы например оставлять заметки на видном месте или научить ребенка читать или считать. В других случаях многочисленные магнитики могут рассказать о продуктах которые съели их хозяева или о местах где они побывали. Очень интересно будет смотреться если вы сделаете магнитики на холодильник своими руками. Это достаточно творческое развивающее фантазию занятие которое может превратить ваши магнитики на холодильник в поистине уникальные если можно так сказать дизайнерские...
35607. Магнітики на холодильник із гіпса 14.55 MB
  Перший етап роботи Спочатку потрібно підготувати місце для роботи і застилити стіл газетами і надіти фартух щоб не забруднитися. Розчин готовий Другий етап роботи Тепер можна заливати готовий розчин у формочки мишізмії та єнота. Третій етап роботи Минув день.
35608. Весна пришла 21.68 KB
  Дети смотрят на рабочий стол и выполняют просьбу учителя.Блок биография Дети выходят к доске и рассказывают стихотворение которое было задано в д з 2 Дети слушают биографию А. Дети следят за учителем и выделяют незнакомые слова. Далее дети разбирают незнакомые слова.
35609. Проект «Творческая весна» 35.5 KB
  Развитие творчества и любознательности детей является весьма актуальной темой в период обучения. формирование уважительного отношения к одноклассникам Воспитательные способствование установлению доброжелательных взаимоотношений между участниками образовательного процесса воспитание самостоятельности аккуратности развитие навыков сотрудничества между одноклассниками развитие художественного вкуса детей Развивающие развитие у школьников черт культурной личности: оценивать художественные произведения музыкальные и литературные ...