Вы здесь

Сортировка слиянием

Исходный код на C++: 

Теория

Сортировка слиянием использует другие алгоритмы сортировки. Основная идея алгоритма сортировки: разбиение исходного массива на части; отсортировать каждую часть отдельно, использую любой алгоритм сортировки; соединить отсортированные части в целое. Приведём пример. Дан входной массив чисел 88,35,11,18,78,53,-54,-111. Разбиваем входной массив на n равных частей (значение n можно выбрать любое возьмём n=5). Создадим двухмерный массив размерностью 2*5(переменная Temp_mass) и запишем в него входной массив. В итоге получим, первая часть равна 88,35,11,18,78(Temp_mass[0]), вторую часть равна 53,-54,-111(Temp_mass[1]). Сортируем каждую часть независимо друг от друга (в качестве сортировки воспользуемся Сортировкой пузырьком). Части массива преобразуются следующим образом первая часть 88,78,35,18,11 и вторая часть 53,-54,-111. Далее нам необходимо соединить две части в единое целое (рис 1).

Создаём выходной массив
Рис 1.Сортировка слиянием Шаг 0.

Создадим массив индексов (переменная Index), который будет указывать на текущий элемент в каждой части массива. Массив индексов, в данном случае, будет содержать два элемента Index[0]=4, а Index[1]=2. На первом шаге сортировки сравниваем текущий элемент из k части массива с текущим элементом из j части массива (Temp_mass[0][Index[0]] сравниваем с Temp_mass[1][Index[1]]). Находим минимальный элемент, (Temp_mass[1][Index[1]]=-111) этот элемент будет первым в выходном массиве (рис.2). Далее уменьшаем значение Index[k]= Index[k] -1 (Index[1]=1).

После первого шага работы алгоритма
Рис 2.Сортировка слиянием Шаг 1.

После первого шага алгоритма значение Index[0]=4, а Index[1]=1. Аналогично сравниваем, текущий элемент из k части массива с текущим элементом из j части массива (Temp_mass[0][Index[0]] сравниваем с Temp_mass[1][Index[1]]). Находим минимальный элемент, (Temp_mass[1][Index[1]]=-54) этот элемент будет вторым в выходном массиве (рис.3). Далее уменьшаем значение Index[k]= Index[k] -1 (Index[1]=0).

После второго шага работы алгоритма
Рис 3.Сортировка слиянием Шаг 2.

Продолжая итерационный процесс, мы получаем отсортированный массив.

Программная реализация

Даная функция имеет два дополнительных параметра: el - количество элементов в каждом массиве; count_mass - количество массивов. Пользователь вводит данные параметры вручную, но если пользователь введёт их некорректно, программа сама попытается их посчитать или выведет сообщение ошибки.

int sort_slienie(int count,double *mass,int el/*количество элементов в каждом массиве*/,int count_mass/*количество массивов*/)
{
int i,j,k;
if(el*count_mass<count)
{
el=(count/(double)count_mass)+0.5;//количество элементов в массиве
el=el>0?el:1;
while(el*count_mass<count)count_mass++;
}
if(count_mass>count || el>count)
return 0;
double **Temp_mass=new double *[count_mass]; //создаём двухмерный массив и сохраняем в него исходный массив
for(i=0;i<count_mass;i++)Temp_mass[i]=new double [el];
int *Index=new int[count_mass];//контроль за количеством элементов в каждом массиве
for(i=count,k=0;i>0;i-=el,k++)Index[k]=i>el?el:i;
for(i=0;i<count;i++)Temp_mass[i/el][i%el]=mass[i];//копируется элементы из входного массива в двухмерный массив
for(i=count,k=0;i>0;i-=el,k++){sort(Temp_mass[k],Index[k]);}//сортируем каждый массив
//сортировка слиянием
for(i=0;i<count;i++)
{
for(k=0,j=0;j<(int)(count/(double)el)+0.5;j++)
{
if(Index[k]<=0){k++;continue;}//проверка количество элементов в массиве
if(Index[j]<=0){continue;}
if(Temp_mass[j][Index[j]-1] < Temp_mass[k][Index[k]-1])k=j;//находим наименьший
}
mass[i]=Temp_mass[k][Index[k]-1];
Index[k]--;
}
//удалить все временные переменные
delete []Index;
for(i=0;i<count_mass;i++)
delete []Temp_mass[i];
delete []Temp_mass;
}