Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID. Но по времени не укладываюсь в рамки

Здравствуйте, Glas, Вы писали:

G>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID. Но по времени не укладываюсь в рамки

ID уникальны? Составной ключ?

Здравствуйте, Glas, Вы писали:

G>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID.

В функции сравнения сначала сравниваются значения, а при их равенстве — id. Тогда одной сортировки хватит

Здравствуйте, VEAPUK, Вы писали:

VEA>ID уникальны? Составной ключ?

Да, для каждого значения ID уникален, по сути это позиция.

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, Glas, Вы писали:

G>>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID.

MBo>В функции сравнения сначала сравниваются значения, а при их равенстве — id. Тогда одной сортировки хватит

Если подскажете как это реализовать для алгоритма quicksort, буду премного благодарен.

Здравствуйте, Glas, Вы писали:

G>Здравствуйте, VEAPUK, Вы писали:

VEA>>ID уникальны? Составной ключ?

G>Да, для каждого значения ID уникален, по сути это позиция.

В смысле?

Так:

ID    Значение
1    2
2    3
1    2
3    5

или

ID    Значение
1    2
2    3
3    2
4    5

std::vector< std::pair< Value, Id > > vector;
............
std::sort(vector.begin(), vector.end());

Здравствуйте, Glas, Вы писали:

MBo>>В функции сравнения сначала сравниваются значения, а при их равенстве — id. Тогда одной сортировки хватит

G>Если подскажете как это реализовать для алгоритма quicksort, буду премного благодарен.

"алгоритм quicksort" функцию сравнения принимает? Вот тогда и передавай в него функцию, работающую по описанной схеме.

Так

VEA>

VEA>ID    Значение
VEA>1    2
VEA>2    3
VEA>3    2
VEA>4    5
VEA>

Здравствуйте, Lloyd, Вы писали:

вот реализация алгоритма, int * idx массив ID, куда вставить сравнение?

void Matrix::QuickSort(Matrix matrix, int * idx, int first, int last)
{
    double p = *matrix((last - first) / 2 + first);
    double temp;
    int idxTemp;
    int i = first;
    int j = last;
    while (i <= j)
    {
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
        if (i <= j)
        {
            temp = *matrix(i);
            idxTemp = idx[i - 1];
            *matrix(i) = *matrix(j);
            *matrix(j) = temp;
            idx[i - 1] = idx[j - 1];
            idx[j - 1] = idxTemp;
            ++i; --j;
        }
    }
    if (j > first) QuickSort(matrix, idx, first, j);
    if (i < last) QuickSort(matrix, idx, i, last);
}

Здравствуйте, dilmah, Вы писали:

D>std::vector< std::pair< Value, Id > > vector;
D>............
D>std::sort(vector.begin(), vector.end());

динамические массивы меня вообще разочаровали. Там только на вставке значение по времени потери чего стоят.

G>вот реализация алгоритма, int * idx массив ID, куда вставить сравнение?

void Matrix::QuickSort(Matrix matrix, int * idx, int first, int last)
{
//...
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
//...
}

Здравствуйте, Glas, Вы писали:

G>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID. Но по времени не укладываюсь в рамки

Мда, а причина то оказывается не в том, что сортировка в 2 прохода Тупо все циклы занимают 50% времени, 45% на перемещение данных и 5% на досортировку ID.

Здравствуйте, Glas, Вы писали:

G>Да, для каждого значения ID уникален, по сути это позиция.

1. Если ID — это позиция, значит нельзя менять порядок равных элементов. Т.е. равные элементы остаются в том порядке, в котором они были в исходном массиве. Называется это дело "stable sort" (устойчивая или стабильная сортировка).

2. STL содержит функцию stable_sort(), которая решает данную задачу. http://www.cplusplus.com/reference/algorithm/stable_sort/

3. Некоторые алгоритмы сортировки изначально являются стабильными. Обычный quicksort к таким не относится. Можно выбрать другой: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms — смотреть столбец "stable"

4. Алгоритм quicksort можно сделать стабильным. Нужно выбирать такой опорный элемент, чтобы правее него не было других равных ему элементов.

Здравствуйте, Glas, Вы писали:

G>динамические массивы меня вообще разочаровали. Там только на вставке значение по времени потери чего стоят.

Дык, если знаешь количество элементов заранее, то reserve(). Не?
Ну и #define _SECURE_SCL 0, если пользуешься stl'ем из VisualStudio.

Здравствуйте, Буравчик, Вы писали:

Б>1. Если ID — это позиция, значит нельзя менять порядок равных элементов. Т.е. равные элементы остаются в том порядке, в котором они были в исходном массиве. Называется это дело "stable sort" (устойчивая или стабильная сортировка).

Б>2. STL содержит функцию stable_sort(), которая решает данную задачу. http://www.cplusplus.com/reference/algorithm/stable_sort/

Б>3. Некоторые алгоритмы сортировки изначально являются стабильными. Обычный quicksort к таким не относится. Можно выбрать другой: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms — смотреть столбец "stable"

Б>4. Алгоритм quicksort можно сделать стабильным. Нужно выбирать такой опорный элемент, чтобы правее него не было других равных ему элементов.

1. да я в терминологии ноль
2. не подходит, так как массив внутри класса.
3. Спасибо за табличку, сейчас себе попробую, что-нибудь подобрать, хотя heapsort почему-то оказался хуже
4. В массиве множество повторяющихся элементов, не подобрать такой элемент.

Реализация кстати довольно слабая, может возьмете готовую ? может даже intro_sort ?

Здравствуйте, Glas, Вы писали:

G>Здравствуйте, Glas, Вы писали:

G>>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID. Но по времени не укладываюсь в рамки

G>Мда, а причина то оказывается не в том, что сортировка в 2 прохода Тупо все циклы занимают 50% времени, 45% на перемещение данных и 5% на досортировку ID.

Тогда сортиру только внешний массив с индексами перестановок.

Здравствуйте, minorlogic, Вы писали:

M>Реализация кстати довольно слабая, может возьмете готовую ? может даже intro_sort ?
Я сейчас все сортировки перебирать буду. Вообще из matlaba бы реализацию вытащить. Там этот массив быстрее на порядок сортируется.

Здравствуйте, Glas, Вы писали:

G>Здравствуйте, Буравчик, Вы писали:

Б>>2. STL содержит функцию stable_sort(), которая решает данную задачу. http://www.cplusplus.com/reference/algorithm/stable_sort/

G>2. не подходит, так как массив внутри класса.


Не вижу логической связи. Подробнее ?