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

Сортировка слиянием относится к типу алгоритмов “объединяй и властвуй”. Предположим, что у нас есть процедура СЛИВАЙ(i,j,k), которая два уже отсортированных сегмента a[i…j-1] и a[j…k] преобразует (сливает) в один  сегмент a[i…k], делая его полностью отсортированным. Тогда рекурсивная процедура  СОРТИРУЙ(i,j) выполняет сортировку всего сегмента a[i…k], а для сортировки всего исходного массива необходимо выполнить вызов СОРТИРУЙ(1,n).

  • Рекурсивный алгоритм

void merge_sort(const int i,const int j)

{

int m ;

if (i < j)

{

m = (i + j)/2 ;

merge_sort(i , m) ;

merge_sort((m+1) , j) ;

merge(i, m, j) ;

}

} ;

Реализация слияния

Массив sort_array  – сортируемый массив.  tmp_array – временный массив для хранения элементов с i по j.

void merge (const int i,const int m, const int j)

{

int k1 =  i, k2 = (m + 1) ;

int tmp_n = j – i + 1 ;

int l,h ;

int* tmp_array ;

tmp_array = new int[tmp_n] ;

for(l = 0 ; l < tmp_n ; ++l)

tmp_array[l] = sort_array[l + i] ;

h = 0 ;

while ((k1 <= m)&&(k2 <= j))

{

if(tmp_array[k1 - i] > tmp_array [k2 - i])

{

sort_array[i + h] = tmp_array[k1 - i] ;

++k1 ;

++h ;

}

else

{

sort_array [i + h] = tmp_array[k2 - i] ;

++k2 ;

++h ;

}

}

if (k1 <= m)

while (k1 <= m)

{

sort_array[i + h] = tmp_array[k1 - i] ;

++k1 ;

++h ;

}

else

while (k2 <= j)

{

sort_array[i + h] = tmp_array[k2 - i] ;

++k2 ;

++h ;

}

delete tmp_array ;

}

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.