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


 

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

24608. Облік готової продукції та її реалізації 27.5 KB
  Облік готової продукції та її реалізації До готової продукції належить продя обробка якої закінчена та яка пройшла випробування приймання укомплектування згідно з умовами договорів відповідає затвердженим стандартам пройшла технічний контроль та здана на склад або замовнику. продя має вартісну характеристику у гривневому еквіваленті. Супутня продя продя отримана в одному технологічному циклі одночасно з основною. Побічна продя – яка утворюється паралельно з основною і не потребує додаткових витрат.
24609. Облік фінансових інвестицій 36 KB
  Фінансова інвестиції – активи які утримуються підприємством з метою збільшення прибутку зростання вартості капіталу. первісно оцінюються за собівартістю з:ціни придбання комісійних винагород мита податків зборів та ін. за Дт придбання Кт зменшення їх вартості та вибуття.35 за варт.
24610. Облік власного капіталу 44.5 KB
  Облік власного капіталу В момент створення підпрва його страховий капітал втілюється в активах інвестованих засновниками і представляє собою варт. Власний капітал ВК – частина в активах підпрва яка залишається після вирахування всіх його зобов’язань К=АЗ. Складові: статутний капітал рах. капіт.
24611. Облік розрахунків векселями 38.5 KB
  Облік розрахунків векселями Облік розрахунків за векселями регламентується постановою Верховної Ради України Про застосування векселів в господарському обороті України. Вексель являє собою письмове боргове зобов'язання векселедавця сплатити векселедержцю власнику векселя по настанні строку суму вказану у векселі.Розрізняють векселі прості і переказні. У простому векселі беруть участь дві сторони: векселедавець І векселедержєць.
24612. Облік кредитів банку 41.5 KB
  Синтетичний облік розрахунків по банківських кредитах здійснюється на пасивних рахунках 60 Короткострокові позики 50 Довгострокові позики. На рахунку 60 Короткострокові позики ведеться облік розрахунків у національній і іноземній валюті по кредитах банків строк повернення яких не перевищує 12 місяців з дати балансу та за позиками строк погашення яких минув.По кредиту рахунка 60 Короткострокові позики відображаються суми одержаних кредитів позик по дебету сума їх погашення та переведення до довгострокових зобов'язань у разі...
24613. Облік фінансових результатів діяльності підприємства 39 KB
  Облік фінансових результатів діяльності підприємства Формування доходів і витрат за видами діяльності і функціями. Фінансові результати за видами діяльності в результаті яких вони виникають поділяються на прибуток збиток від звичайної діяльності та від надзвичайних подій.Під звичайною діяльністю розуміють будьяку діяльність підприємства а також операції які забезпечують її або які виникають внаслідок здійснення такої діяльності.Прикладом звичайної діяльності є виробництво і реалізація продукції робіт послуг розрахунки з...
24614. Склад та призначення фінансової звітності підприємства 37 KB
  Склад та призначення фінансової звітності підприємства За видами звітність поділяється на бухгалтерську статистичну та оперативну. Бухгалтерська звітність містить показники виробничофінансової діяльності підприємства. Оперативна звітність призначена для поточного контролю та управління всередині підприємства на момент здійснення господарських операцій або одразу ж після їх завершення. В ній містяться дані про виконання плану поставок матеріалів виробництва продукції а також про дотримання укладених договорів та фінансовий стан підприємства...
24615. Облік дебіторської заборгованості за товари, роботи, послуги. Резерв сумнівних боргів 35.5 KB
  Облік дебіторської заборгованості за товари роботи послуги. Резерв сумнівних боргів Дебіторська заборгованість за продукцію товари роботи послуги це заборгованість покупців або замовників за надані їм продукцію товари роботи або послуги.Дебіторська заборгованість за продукцію товари роботи послуги виникає коли підприємство реалізує продукцію товари роботи послуги в кредит з відстрочкою платежу.Таким чином для визнання поточної дебіторської заборгованості за продукцію товари роботи послуги необхідно щоб виконувалися...
24616. Облік розрахунків з підзвітними особами: нормативні вимоги то особливості обліку 31.5 KB
  Облік розрахунків з підзвітними особами: нормативні вимоги то особливості обліку Готівка видається працівникам підприємства підзвіт на відрядження та на господарські потреби за розпорядженням керівника підприємства за умови що у працівника немає заборгованості по раніше виданих авансах.Службове відрядження поїздка на визначений строк в іншу місцевість для виконання службових обов'язків.Термін відрядження не може перевищувати 30 календарних днів у межах України і 60 днів при відрядженні за кордон.Термін відрядження визначається за відмітками...