Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка слиянием
|
|
Сортировка слиянием - этот рекурсивный алгоритм. Он, также как и быстрая сортировка(описано в первой части), делит список на две части, и затем рекурсивно вызывает сам себя для их дальнейшего упорядочивания. Она делит список на две равные части, после чего подсписки рекурсивно сортируются и сливаются для того что бы образовать полностью отсортированный список.
Процесс объединения, наверно, наиболее интересная часть алгоритма и её понять, довольно, не сложно. Подсписки объединяются в рабочий массив, а результат копируется в исходный список. Однако, следует учитывать что при сортировки слишком большого массива могут возникнуть проблемы с составлением рабочего массива. Из-за большого числа сортируемых элементов, программа может обращаться к файлу подкачки что снижает её скорость, также пагубно влияет на время копирования данных из одного массива в другой. Но время выполнения можно увеличить, если применять в связку сортировкой слиянием с другой сортировкой, например с сортировкой вставками. Для этого необходимо выбрать некоторое число элементов массива при достижении которого рекурсия будет остановлена и массив будет досортирован другим методом. Это можно сделать примерно так:
| Листинг 1.Код Delphi/Pascal |
| if(max-min)< StopIndex then begin SelctionSort(a, min, max); exit; end; |
StopIndex - это и есть то число которое Вы выбрали для остановки рекурсии.Сам алгоритм в чистом виде выглядит так:
| Листинг 2.Сортировка слиянием |
| procedureMergeSort(varar1, ar2: arrayof Integer; min, max: Integer); var middle, int1, int2, int3: Integer; begin ifmin< max then begin //в противном случае массив состоит //из 1-го элемента и упорядочен. middle: =min div2+max div2; // рекурсивно сортируем подсписки MergeSort(ar1, ar2, min, middle); MergeSort(ar1, ar2, middle+1, max); int1: =min; //указатель на 1-й массив int2: =middle+1; //указатель на 2-й массив int3: =min; //указатель на объединённый массив //объединение сортированных массивов while(int1< =middle) and (int2< =max) do begin ifar1[int1] then begin ar2[int3]: =ar1[int1]; int1: =int1+1; end else begin ar2[int3]: =ar1[int2]; int2: =int2+1; end; inc(int3); end; // очистка не пустого списка while(int1< =middle) do begin ar2[int3]: =ar1[int1]; int1: =int1+1; int3: =int3+1; end; while(int2< =middle) do begin ar2[int3]: =ar1[int2]; int2: =int2+1; int3: =int3+1; end; end; //приравнивание входящих массивов forint1: =min tomax do ar1[int1]: =ar2[int1]; end; |
Этот алгоритм работает обычно медленней, чем быстрая сортировка, однако у него есть ряд преимуществ: во первых он показывает стабильные результаты при сортировке определённого количества данных, в то время как при быстрой сортировке эти результаты могут довольно сильно различаться(см табл). Во-вторых, при большом количестве повторяющихся элементов программа не уходит в глубокую рекурсию.
Результата сравнения сортировки слиянием быстрой сортировкой приведены в таблице. Для тестов использовался компьютер с процессором Pentium-133, 16-Ram. Количество сортируемых элементов равнялось 1млн.
| Диапазон значений | Время сортировки слиянием (сек) | Время быстрой сортировки(сек) |
| 1-10млн | 4.72 | 2, 75 |
| 1-1000 | 4.67 | 16.12 |
| 1-100 | 4.75 | 194.18 |