Получить отсортированные индексы массива с помощью быстрой сортировки

Question

Я изменил код быстрой сортировки для сортировки массива с плавающей точкой, полученного с tutorialgatway.org .Однако мне нужны отсортированные индексы.Мне известна библиотечная функция qsort, которую можно использовать для получения отсортированных индексов, и я могу это реализовать.Тем не менее, я хочу избежать стандартной библиотеки (я знаю, что это не рекомендация).Причина, по которой не используется стандартная библиотека, заключается в том, что мне нужно отсортировать большое количество массивов в цикле, которые нужно распараллелить, используя openMP, поэтому написание функции явно позволило бы мне распараллелить функцию быстрой сортировки в цикле.

/* C Program for Quick Sort */
#include <stdio.h>

void Swap(float *x, float *y) {
    float Temp;
    Temp = *x;
    *x = *y;
    *y = Temp;
}

void quickSort(float a[], int first, int last) {
    int i, j;
    int pivot;
    if (first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while (a[i] <= a[pivot] && i < last)
                i++;
            while (a[j] > a[pivot])
                j--;
            if (i < j) {
                Swap(&a[i], &a[j]);
            }
        }
        Swap(&a[pivot], &a[j]);
        quickSort(a, first, j - 1);
        quickSort(a, j + 1, last);
    }
}

int main() {
    int number, i;
    float a[100];
    printf("\n Please Enter the total Number of Elements  :  ");
    scanf("%d", &number);
    printf("\n Please Enter the Array Elements  :  ");
    for (i = 0; i < number; i++)
        scanf("%f", &a[i]);

    quickSort(a, 0, number - 1);
    printf("\n Selection Sort Result : ");
    for (i = 0; i < number; i++)  {
        printf(" %f \t", a[i]);
    }
    printf("\n");
    return 0;
}

Как я могу вернуть отсортированные индексы в коде?

Answer 1

Вам нужно сгенерировать массив индексов от 0 до size-1, затем отсортировать массив индексов по значениям массива. Таким образом, код сравнивает, используя массив [index [...]], и выполняет обмен на индекс [...].

Альтернативой является создание массива указателей от & array [0] до & array [size-1]. Когда указатели отсортированы, вы можете преобразовать их в индексы, используя: index [i] = pointer [i] - & array [0] (может использовать объединение для индексов и указателей).

---

Пример программы со стандартной версией схемы разбиения Hoare для сортировки массива индексов в I [] по значениям с плавающей запятой в A []:

#include <stdio.h>
#include <stdlib.h>

void QuickSort(float A[], size_t I[], size_t lo, size_t hi)
{
    if (lo < hi)
    {
        float pivot = A[I[lo + (hi - lo) / 2]];
        size_t t;
        size_t i = lo - 1;
        size_t j = hi + 1;
        while (1)
        {
            while (A[I[++i]] < pivot);
            while (A[I[--j]] > pivot);
            if (i >= j)
                break;
            t = I[i];
            I[i] = I[j];
            I[j] = t;
        }
        QuickSort(A, I, lo, j);
        QuickSort(A, I, j + 1, hi);
    }
}

#define COUNT (4*1024*1024)             // number of values to sort

int main(int argc, char**argv)
{
    int  r;                             // random number
    size_t i;

    float  * A = (float *)  malloc(COUNT*sizeof(float));
    size_t * I = (size_t *) malloc(COUNT*sizeof(size_t));

    for(i = 0; i < COUNT; i++){         // random floats
        r  = (((rand()>>4) & 0xff)<< 0);
        r += (((rand()>>4) & 0xff)<< 8);
        r += (((rand()>>4) & 0xff)<<16);
        r += (((rand()>>4) & 0xff)<<24);
        A[i] = (float)r;
    }

    for(i = 0; i < COUNT; i++)          // array of indexes
        I[i] = i;

    QuickSort(A, I, 0, COUNT-1);

    for(i = 1; i < COUNT; i++){
        if(A[I[i-1]] > A[I[i]]){
            printf("error\n");
            break;
        }
    }

    free(I);
    free(A);

    return(0);
}

---

Эта версия быстрой сортировки позволяет избежать переполнения стека, используя только рекурсию меньшей части раздела. В худшем случае временная сложность все равно будет O (n ^ 2), но сложность стекового пространства ограничена O (log (n)).

void QuickSort(float A[], size_t I[], size_t lo, size_t hi)
{
    while (lo < hi)
    {
        float pivot = A[I[lo + (hi - lo) / 2]];
        size_t t;
        size_t i = lo - 1;
        size_t j = hi + 1;
        while (1)
        {
            while (A[I[++i]] < pivot);
            while (A[I[--j]] > pivot);
            if (i >= j)
                break;
            t = I[i];
            I[i] = I[j];
            I[j] = t;
        }
        /* avoid stack overflow */
        if((j - lo) < (hi - j)){
            QuickSort(A, I, lo, j);
            lo = j+1;
        } else {
            QuickSort(A, I, j + 1, hi);
            hi = j;
        }
    }
}