Быстрый поиск и отслеживание индексов

Question

Я хочу, чтобы quciksort задал массив, а также отслеживать индекс. Функция сортировка unsorted_arr[]={3,5,6,6,7,4,5} и дать sorted_arr[]={3,4,5,5,6,6,7}, а также вернуть что-то вроде sorted_indices[]={0,5,1,6,2,3,4}.

Вот функция

//int unsorted_arr[],sorted_arr[],sorted_indices[]; 
void quickSort(int arr[], int left, int right) 
{ 

     int i = left, j = right; 
     sorted_indices[i]=left;sorted_indices[j]=right; 
     int tmp; 

     int pivot = arr[(left + right)/2]; 



     /* partition */ 

     while (i <= j) { 

     while (arr[i] < pivot) 
      {sorted_indices[i]=i; 
      i++;  } 

     while (arr[j] > pivot) 
      {sorted_indices[j]=j; 
      j--;    } 

     if (i <= j) { 

      tmp = arr[i]; 

      arr[i] = arr[j]; 
      sorted_indices[i]=j; 
      sorted_indices[j]=i; 
      arr[j] = tmp; 

      i++; 

      j--; 

     } 

     }; 



     /* recursion */ 

     if (left < j) 

     quickSort(arr, left, j); 

     if (i < right) 

     quickSort(arr, i, right); 

} 

Примечание: Я ограничен использованием Turbo C++ 3.0 и массивы.

Answer 1

Настройте массив целых чисел 0 .. N -1.

Затем напишите свой быстрый вид, чтобы он взял этот массив, как int *, и массив для сортировки, как const data_type * (const unsigned char * с соответствующей шириной элемента данных).

Теперь просто quick_sort целочисленный массив, используя индексы в массиве данных для целей сравнения.