Сохранение исходных индексов при сортировке с помощью Merge Sort in c

Question

Я пытаюсь сортировать список с помощью Merge Sort algoritm, сохраняя его исходные индексы. Мне сказали, что прямолинейное решение состоит в том, чтобы использовать массив индексов (очевидно, он будет инициализирован 0 1 2 3 ...) и изменить его внутри сортировки слияния, поскольку я изменяю соответствующие значения в оригинале массив. Дело в том, что я не могу найти способ заставить его работать, потому что сортировка слияния не использует индексы исходного массива, а скорее индексы небольших массивов, в которые разбивается исходный массив. Наверное, я что-то пропустил ... решение, о котором я думал до сих пор, состояло в том, чтобы обрабатывать массив индексов точно так же, как и исходный, я имею в виду разбить его на меньшие массивы, объявить «helperIndexArray» для новых индексов, вызвать слияние с этими переменными и т. д. Но это кажется действительно неэффективным. Разве нет лучшего способа? Буду признателен за любые советы, спасибо!

void internalMsort(int array[], int size, int helperArray[], int index[]) { 
    int left = size/2, right = size - left; 
    if (size < 2) 
     return; 
    internalMsort(array, left, helperArray); 
    internalMsort(array + left, right, helperArray); 
    merge(array, left, array + left, right, helperArray, index); 
    memCpy(array, helperArray, size); 
} 

void merge(int a[], int na, int b[], int nb, int c[], index[]) { 
int ia, ib, ic; 
    for(ia = ib = ic = 0; (ia < na) && (ib < nb); ic++) 
    { 
     if(a[ia] < b[ib]) { 
      c[ic] = a[ia]; 
      ia++; 
      // here I was trying to swap index[ic] with index[ia] but it didn't work 
     } 
     else { 
      c[ic] = b[ib]; 
      ib++; 
     } 
    } 
    for(;ia < na; ia++, ic++){ c[ic] = a[ia]; } 
    for(;ib < nb; ib++, ic++) { c[ic] = b[ib]; } 
} 

Answer 1

Определение нового типа под названием кортеж:

typedef struct 
{ 
    int value; 
    size_t index; 
} tuple; 

Создать массив кортежей, заполнить его значениями, и установить индексы в порядке, от 0 до размера-1.

Затем сортируйте массив, используя значение элемента, и игнорируйте индекс участника.

Результирующий массив будет отсортирован, и его элементы будут содержать исходный индекс в индексе члена.

Answer 2

Это довольно просто (и не относится к mergesort). Просто создать массив

struct element_and_index_st  { 
    int element; 
    size_t original_index; // could be an `int` or an `unsigned` 
}; 

и отсортировать этот массив, обеспечивая функцию сравнения, которая только сравнивает element поле.

^{(если ваш массив не огромен, вы практически можете иметь original_index быть некоторые int или некоторые unsigned на текущих компьютерах и ноутбуках, где int s имеют 32 бита, по крайней мере)}

Но вы не говорите почему вам нужны исходные индексы и как вы сможете вернуть их своему абоненту?

Возможно, вы просто хотите получить stable sort?

Answer 3

Первый сортировать индексы в соответствии с массивом (сравнить массив [index [ia]] < = array [index [ic]] для сортировки индекса []. Использовать вспомогательный массив как второй массив для индексов. массив и индексы являются целыми числами, вы можете использовать вспомогательный массив для сортировки массива после сортировки индексов:

for(i = 0; i < size; i++) 
     helperArray = array[index[i]]; 
    for(i = 0; i < size; i++) 
     array[i] = helperArray[i];