Вариант сортировки слияния: использование массива ссылок

Я искал варианты Merge Sort. Поэтому в моем учебнике говорится:

Вариант функции Merge, в котором нет записей вообще не нужно перемещать, может быть реализован с использованием вспомогательных ссылок на массив.

Во-первых, я хотел бы указать код.

Algo MergeSort(low,high)
{

// a is the array to be sorted using auxiliary array link. 

if(high-low<15)
return InsertionSort1(a,link,low,high);

else
{

 mid = (low+high)/2;
 q=MergeSort(low,mid);
 r=MergeSort(mid+1,high);
 return Merge1(q,r);

}

}

// The function Merge1 is as defined:

function Merge1(q,r)
{

// q and r are pointers to list contained in the global array link[0:n], the lists pointed at by q //and r are merged and a pointer to the beginning of the merged list is returned.

 i=q;
 j=r;
 k=0;

while(i!=0 && j!=0) 
{ 
 if(a[i]<=a[j])
 {
 link[k]=i;
 k=i;
 i=link[i];
 }

 else
 {

 link[k]=j;
 k=j;
 j=link[j];
 }
} // end of while

if(i=0) 
 link[k]=j;

else
 link[k]=i;

return link[0];
}

Хорошо, так что я понял алгоритм:

  1. Если количество элементов меньше 15, примените сортировку вставки и отсортируйте эти элементы.
  2. Таким образом, мы получим много списков, которые будут отсортированы сами по себе, но весь массив не будет сортироваться как таковой.
  3. Для сортировки всего массива используется функция Merge.

Мой вопрос в том,

Как функция Merge объединяет разные отсортированные списки в один отсортированный список?Я понятия не имею о концепции массива link.

Извините, но я очень старался понять, но я не понимаю, как массив результатов сортируется?

Любой пример поможет. Спасибо.

1 ответ

Я очистил код, а также добавил нижнюю версию, в которой используется массив начальных индексов (см. Ниже). Я сменил high в MergeSort() до конца, так что теперь вызов MergeSort (0, SIZE). я = MergeSort() возвращает индекс наименьшего значения в [], тогда я = link [i] является вторым элементом, я = ссылка [i] является третьим элементом, пока я = -1. Вместо того, чтобы использовать сортировку вставки, MergeSort() напрямую сортирует группы размером == 1 или size == 2 и инициализирует ссылку [].

MergeLists() использует head для начала списка (старый код использует ссылку [0]) и -1 для конца списка (старый код использует 0). Это позволяет сортировать [0] до [n -1] (старый код сортировал [1] с [n], а [0] не использовался).

Если a [] = {5,4,8,7}, MergeSort() возвращает 1, а ссылка [] = {3,0, -1, 2}, ссылка [1] = 0, ссылка [0 ] = 3, link [3] = 2, link [2] = -1, поэтому порядок - это [1], a [0], a [3], a [2].

#define SIZE 4
static unsigned int a[SIZE] = {5,8,4,7};
static size_t link[SIZE]; /* index to next element */

size_t MergeLists(size_t i, size_t j)
{
size_t head;
size_t *pprev = &head; /* ptr: head or link[] */
 while((i != -1) && (j != -1)){ /* while not end lists */
 if(a[i] <= a[j]){ /* if i < j */
 *pprev = i; /* link to i */
 pprev = &link[i]; /* advance pprev */
 i=*pprev; /* advance i */
 } else { /* else */
 *pprev = j; /* link to j */
 pprev = &link[j]; /* advance pprev */
 j=*pprev; /* advance j */
 }
 }
 if(i == -1) /* if end of i list */
 *pprev=j; /* link to rest of j */
 else /* else */
 *pprev=i; /* link to rest of i */
 return head;
}

size_t MergeSort(size_t low, size_t end)
{
size_t mid, i, j;
 if((end - low) == 0){ /* if size == 0 */
 return low; /* (only on first call) */
 }
 if((end - low) == 1){ /* if size == 1 */
 link[low] = -1; /* initialize link[] */
 return low; /* return index */
 }
 if((end - low) == 2){ /* if size == 2 */
 if(a[low] <= a[end-1]){ /* if in order */
 link[low] = end-1; /* initialize link[] */
 link[end-1] = -1;
 return low; /* return index */
 } else { /* else */
 link[end-1] = low; /* initialize link[] */
 link[low] = -1;
 return end-1; /* return index */
 }
 }
 mid = (low+end)/2; /* size > 2, recursively */
 i = MergeSort(low, mid); /* split lists until */
 j = MergeSort(mid, end); /* size <= 2 */
 return MergeLists(i, j); /* merge a pair of lists */
}

int main(void)
{
size_t i;
 i = MergeSort(0, SIZE);
 do{
 printf("%3d", a[i]);
 i = link[i];
 }while(i != -1);
 return 0;
}

Это нерекурсивный пример. Он использует массив начальных индексов S []. N [] является тем же самым ссылкой [] выше, и MergeLists() аналогична предыдущей. S [0] указывает на списки размером 1, S [1] указывает на списки размера 2, S [2] указывает на списки размера 4,... S [i] указывает на списки размером 2 ^ я (2 к мощности i). S [31] указывает на список неограниченного размера. Элементы объединяются в массив по одному, затем списки массивов объединяются для формирования единого списка.

#define NUMIDX (32) // number of indexes in array

// A[] is array to be sorted
// N[] is array of indexes to next index
// l is index of N[] to left list
// r is index of N[] to right list
// returns starting index (l or r) for merged list

size_t MergeLists(int A[], size_t N[], size_t l, size_t r)
{
size_t head;
size_t *pprev = &head; // ptr: head or N[]
 while((l != -1) && (r != -1)){ // while not end lists
 if(A[l] <= A[r]){ // if l <= r
 *pprev = l; // link to l
 pprev = &N[l]; // advance pprev
 l=*pprev; // advance l
 } else { // else
 *pprev = r; // link to r
 pprev = &N[r]; // advance pprev
 r=*pprev; // advance r
 }
 }
 if(l == -1) // if end of l list
 *pprev=r; // link to rest of r
 else // else
 *pprev=l; // link to rest of l
 return head;
}

// A[] is array to be sorted
// N[] is set to array of indexes to next index (-1 = end list)
// low is starting index of A[]
// end is ending index of A[] (1 past last)
// returns starting index of N[] for merged list
// S[] is array of starting indexes in N[]
// S[i] is starting index of list of size pow(2,i)

size_t MergeSort(int A[], size_t N[], size_t low, size_t end)
{
size_t S[NUMIDX]; // array of starting indexes
size_t i,j;
 if((end - low) == 0){ // if size == 0
 return low; // (only on first call)
 }
 for(i = 0; i < (end-low); i++) // init N[]
 N[i] = -1;
 for(i = 0; i < NUMIDX; i++) // init S[]
 S[i] = -1;
 for(j = low; j < end; j++){ // merge index lists into S[], N[]
 low = j;
 for(i = 0; (i < NUMIDX) && (S[i] != -1); i++){
 low = MergeLists(A, N, S[i], low);
 S[i] = -1;
 }
 if(i == NUMIDX)
 i--;
 S[i] = low;
 }
 low = -1; // merge S[] lists to one list in N[]
 for(i = 0; i < NUMIDX; i++)
 low = MergeLists(A, N, S[i], low);
 return low;
}

licensed under cc by-sa 3.0 with attribution.