Quicksort und Verfolgen von Indizes

Question

Ich möchte ein gegebenes Array quicksort und auch den Index verfolgen. Die Funktion sort unsorted_arr[]={3,5,6,6,7,4,5} und geben sorted_arr[]={3,4,5,5,6,6,7} und sollte auch etwas wie sorted_indices[]={0,5,1,6,2,3,4} zurückgeben.

Hier ist die Funktion

//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); 

} 

Anmerkung: Ich bin auf der Verwendung von Turbo C++ 3.0 und Arrays.

Answer 1

Richten Sie ein Array der Ganzzahl 0 .. N -1 ein.

Schreiben Sie dann Ihre schnelle Sortierung, so dass sie dieses Array als int * und das zu sortierende Array als const data_type * (const unsigned char * mit zugehöriger Datenelementbreite ist in Ordnung) verwendet.

Jetzt einfach quick_sort das Ganzzahl-Array, mit den Indizes in den Daten-Array für den Zweck des Vergleichs.