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
А также другие работы, которые могут Вас заинтересовать | |||
3804. | Боевые графические документы | 559.16 KB | |
Боевые графические документы Введение Карта это основное средство ориентирования. Топографическая карта была и остается надежным путеводителем по незнакомой местности. С помощью карты можно быстро и точно определить свое местоположение, указать обна... | |||
3805. | Республика Боливия | 227 KB | |
Республика Боливия (Republica de Bolivia) это окруженная сушей страна в Южной Америке с площадью 424,164 квадратных миль (1,098,581 квадратных километров). Страна стала окруженной сушей с тех пор, как потеряла свое тихоокеанское побережье, которое от... | |||
3806. | Атестація робочого міста | 206.5 KB | |
Атестація робочого міста 1. Охорона праці на підприємстві. В умовах сучасного виробництва окремі приватні заходи щодо поліпшення умов праці, для попередження травматизации є неефективними. Тому їх здійснюють комплексно, створюючи в загальній системі... | |||
3807. | Анализ опасных и вредных факторов, воздействующих на программиста при разработке системы | 158 KB | |
Безопасность жизнедеятельности. Вопросы безопасной жизнедеятельности человека необходимо решать на всех стадиях жизненного цикла, будь то разработка, внедрение в жизнь или эксплуатация программы. Обеспечение безопасной жизнедеятельности челове... | |||
3808. | Движение центра масс МКА под действием различных возмущающих ускорений | 432 KB | |
Введение В данной работе проводится исследование движения центра масс МКА под действием различных возмущающих ускорений (от нецентральности гравитационного поля Земли, сопротивления атмосферы, притяжения Солнца и Луны, из-за давления солнечных лучей... | |||
3809. | Маржинализм и теория предельной полезности | 101 KB | |
Маржинализм и теория предельной полезности. Явная неспособность новой исторической школы с её крайним эмпиризмом и националистической ориентацией противопоставить марксизму общую теоретическую систему привела к появлению и распространению в 70-90-х ... | |||
3810. | Анализ финансового состояния и бухгалтерского баланса предприятия | 549.5 KB | |
Введение Переход к рыночной экономике требует от предприятия повышения эффективности производства, конкурентоспособности продукции и услуг на основе внедрения достижений научно-технического прогресса, эффективных форм хозяйствования и управления про... | |||
3811. | Костенко Ліна Василівна | 71.5 KB | |
Костенко Ліна Василівна народилася 19 березня 1930 року в містечку Ржищеві на Київщині. З 1936 року живе в Києві. Тут закінчила середню школу, вчилася у педагогічному інституті. Але в 1952 році вступила до Московського літературного інституту ім. О.... | |||
3812. | Показатели качества торговых услуг и методы их оценки | 307.5 KB | |
Показатели качества торговых услуг и методы их оценки Введение Современный этап экономического развития, переживаемый Россией, характеризуется достаточно устойчивым ростом экономики, сопровождающимся изменением структуры ВВП. Данные среднегодовых те... | |||