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


 

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

83774. Налоговые правоотношения: понятие, признаки, структура 45.16 KB
  НК РФ законодательство о налогах и сборах регулирует властные отношения по установлению введению и взиманию налогов и сборов в РФ а также отношения возникающие в процессе осуществления налогового контроля обжалования актов налоговых органов действий бездействия их должностных лиц и привлечения к ответственности за совершение налогового правонарушения. Под воздействием правовых норм участники налоговых правоотношений наделяются правосубъектностью юридическими правами и обязанностями в налоговой сфере. Наряду с ней предпосылками...
83775. Субъекты налоговых правоотношений: общая характеристика 46.47 KB
  Точное определение субъекта налогового права имеет и практическое значение поскольку позволяет выявить круг лиц вступающих в налоговые отношения и действия которых влекут юридически значимые последствия. Наличие критериев позволяющих относить какоелибо физическое или юридическое лицо к субъектам налогового права дает возможность установить какие лица и их действия подпадают под юрисдикцию законодательства о налогах и сборах. Только субъекты налогового права могут иметь права и нести обязанности предусмотренные НК РФ и принятыми в...
83776. Правовой статус налогоплательщиков, налоговых агентов и налоговых представителей 57.26 KB
  Возникновение обстоятельств влекущих уплату суммы налога или сбора служит юридическим фактом на основании которого субъект налогового права приобретает статус участника налоговых правоотношений. 11 НК РФ указывает что физические лица осуществляющие предпринимательскую деятельность без образования юридического лица но не зарегистрировавшиеся в качестве индивидуальных предпринимателей в нарушение требований гражданского законодательства при исполнении налоговых обязанностей не вправе ссылаться на то что они не являются индивидуальными...
83777. Банки как субъекты налогового права. Иные участники налоговых отношений 49.16 KB
  Иные участники налоговых отношений. 9 НК РФ к участникам налоговых отношений регулируемых законодательством о налогах и сборах фактически они таковыми являются и обладают специальным налоговоправовым статусом. Банки являются субъектами налоговых правоотношений обеспечивающими налоговые изъятия и наделенными в связи с этим соответствующими правами и обязанностями. Участие банков в налоговых отношениях носит более сложный по сравнению с иными участниками налоговых отношений регулируемых законодательством о налогах и сборах характер.
83778. Правовой статус налоговых органов. Их права и обязанности. Обязанности должностных лиц налоговых органов 43.23 KB
  Обязанности должностных лиц налоговых органов. Правовой статус налоговых органов РФ объем и характер прав и обязанностей системы налоговых органов России строго определенных законодательством. Правовое положение налоговых органов обусловлено их местом в системе органов государственного управления страны наделением их над ведомственными полномочиями по отношению к организационно неподчиненным объектам управления по контролю за соблюдением налогового законодательства правильностью их исчисления полнотой и своевременностью внесения в...
83779. Правовой статус таможенных органов, финансовых органов, органов внутренних дел, следственных органов 44.78 KB
  Таможенные органы пользуются правами и несут обязанности налоговых органов по взиманию налогов при перемещении товаров через таможенную границу Таможенного союза в соответствии с таможенным законодательством ТС и законодательством РФ о таможенном деле. При исполнении указанных функций таможенные органы и их должностные лица реализовывают в пределах своей компетенции права и обязанности налоговых органов ст. В ходе проведения контрольных мероприятий таможенные органы вправе: запрашивать документы и сведения в том числе в форме электронных...
83780. Исполнение обязанности по уплате налогов и сборов. Объекты налогообложения. Принципы определения цены товаров, работ или услуг для целей налогообложения 44.19 KB
  Сущность исполнения налоговой обязанности заключается в уплате налога или сбора. Налоговая обязанность возникает с момента возникновения установленных налоговым законодательством обстоятельств предусматривающих уплату конкретного налога или сбора. Так вот обстоятельствами с которыми налоговое законодательство связывает возникновение налоговой обязанности являются следующие: вопервых это наличие объекта конкретного налога или сбора; вовторых это наличие непосредственной связи между этим объектом и субъектом налогоплательщиком. И...
83781. Исполнение обязанности по уплате налогов и сборов. Основания возникновения, изменения и прекращения обязанности по уплате налогов и соборов; порядок исчисления налогов; взыскание налога за счет денежных средств и иного имущества налогоплательщика 46.34 KB
  Основания возникновения изменения и прекращения обязанности по уплате налогов и соборов; порядок исчисления налогов; взыскание налога за счет денежных средств и иного имущества налогоплательщика. Возникновение обязанности по уплате налогов и сборов связано с несколькими обстоятельствами: с наличием конституционноправовой обязанности по уплате налогов по нормам законодательства о налогах и сборах в которых детализируется реализация обязанности по уплате налогов объектами налогообложения.  Основанием возникновения налогового обязательства...
83782. Изменение срока уплаты налога и сбора: общие условия изменения срока уплаты; обстоятельства исключающие изменение срока уплаты, органы, уполномоченные принимать решение об изменении сроков уплаты 41.84 KB
  Изменением срока уплаты налога и сбора признается перенос установленного срока уплаты налога и сбора на более поздний срок. Срок уплаты налога и или сбора может быть изменен в отношении всей подлежащей уплате суммы налога и или сбора либо ее части с начислением процентов на сумму задолженности. Изменение срока уплаты налога и сбора осуществляется в форме отсрочки рассрочки инвестиционного налогового кредита.