Как отсортировать массив, но сохранить положение повторяющегося элемента в C?

Итак, на самом деле мне нужно сохранить индекс старого массива после сортировки. Так, например, если я ввожу [2,4,1,5,7,9,6], то вывод будет [2,0,1,3,6,4,5]. Я уже использовал qsort, и он работает очень хорошо, если нет повторяющихся элементов.

Если есть повторяющиеся элементы, иногда первый повторяющийся элемент помещался последним. Например, если ввод [5,4,6,5,2,1,3], я хочу вывести [5,4,6,1,0,3,2]. Итак, 5 с индексом 0 ставится перед 5 с индексом 3. Но при использовании qsort иногда получается [5,4,6,1,3,0,2].

Можете ли вы помочь мне исправить это? Или я должен создать свою собственную функцию сортировки? Не могли бы вы помочь мне создать его?

Вот мой код:

#include <stdlib.h>

int* sortidx(double *X,int n)
{
    int *idx,i,j;

    int cmp(const void *a,const void *b)
    {
        return X[*(int*)a]>=X[*(int*)b]?1:-1;
    }

    idx=(int*)calloc(n,sizeof(int));

    for(i=0;i<n;i++)
    {
        idx[i]=i;
    }

    qsort(idx,n,sizeof(int),cmp);

    return idx;
}

c arrays sorting stable-sort qsort
person fahadh4ilyas    schedule 13.08.2017    source источник
comment
Кажется, вам нужно то, что называется стабильным алгоритмом сортировки. Проверьте здесь en.wikipedia.org/wiki/Sorting_algorithm#Stability значение. Затем выберите алгоритм среди тех, которые описаны как стабильные, и вы должны быть настроены.   -  person Yunnosch    schedule 13.08.2017
comment
То, что вам нужно, называется стабильной сортировкой. Поиск стабильной версии qsort c в Google дает несколько результатов; Я предлагаю вам просмотреть их.   -  person NPE    schedule 13.08.2017
comment
Кстати, просто отметим, что вы используете вложенные функции, которые являются расширением GCC.   -  person Antti Haapala    schedule 13.08.2017

Ответы (2)


arrow_upward
5
arrow_downward

Вы хотите, чтобы один элемент считался большим, чем другой, если либо его значение больше, либо если значения равны, а его индекс больше. (Это идея стабильного алгоритма сортировки.)

В этом случае вы знаете индексы сравниваемых элементов, поэтому вы можете легко добавить это к своему критерию сравнения:

int cmp(const void *a, const void *b)
{
    return X[*(int*)a] > X[*(int*)b] ||
           (X[*(int*)a] == X[*(int*)b] && *(int*)a > *(int*)b)
           ?1:-1;
}

или, возможно, более читабельно и педантично правильно (поскольку не задокументировано, что a и b гарантированно будут разными):

int cmp(const void *a, const void *b)
{
    int idxa = *(const int*)a, idxb = *(const int*)b;
    if (X[idxa] > X[idxb]) return 1;
    if (X[idxa] < X[idxb]) return -1;
    return idxa - idxb;
}

Использование вложенной функции, которая ссылается на аргумент X, является расширением gcc и может не работать с другими компиляторами. Реализация Gnu стандартной библиотеки C также содержит функцию qsort_r, которую можно использовать для передачи X процедуре сравнения, но более переносимым способом написания функции было бы использование массива указателей, а не массива индексов:

int idxcmp(const void *a,const void *b)
{
    double *ap = *(double *const*)a, *bp = *(double *const*)b;
    if (*ap > *bp) return 1;
    if (*ap < *bp) return -1;
    return ap - bp; 
}

double** sortidx(double *X, size_t n)
{
    double **idx = calloc(n, sizeof(double*));
    for (size_t i=0; i<n; ++i) idx[i] = X + i;
    qsort(idx, n, sizeof(idx[0]), idxcmp);
    return idx;
}

(Если вы действительно хотите вернуть индексы, вы можете преобразовать указатель в индекс перед возвратом.)

person rici    schedule 13.08.2017
comment
Хороший. Я также думал сравнить индекс, но я не знаю, где его лучше всего разместить. Я попробую. Спасибо большое. ^^ - person fahadh4ilyas; 13.08.2017

arrow_upward
1
arrow_downward

Вам нужен стабильный алгоритм сортировки. Вы можете стабилизировать qsort в C, но это требует дополнительной работы. В C++ существует std::stable_sort.

Если вам нужно придерживаться C, вам следует реализовать собственную стабильную сортировку. Вот список стабильных алгоритмов сортировки:

B
Block sort
Bubble sort
Bucket sort
C
Cascade merge sort
Cocktail shaker sort
Counting sort
Cubesort
G
Gnome sort
I
Insertion sort
L
Library sort
M
Merge sort
O
Odd–even sort
Oscillating merge sort
P
Pigeonhole sort
Proxmap sort
R
Radix sort
T
Timsort
person gsamaras    schedule 13.08.2017
comment
Как говорится в ответах на вопрос, который вы связали, вы можете стабилизировать qsort, используя исходные индексы для разрыва связей. - person interjay; 13.08.2017
comment
@interjay Я вижу, спасибо, ответ обновлен, что вы думаете об этом сейчас? знак равно - person gsamaras; 13.08.2017