Самый эффективный способ сортировки параллельных массивов на языке с ограниченными возможностями

Question

Среда: я работаю на проприетарном языке сценариев, где нет такой вещи, как пользовательская функция. У меня есть различные циклы и локальные переменные примитивных типов, которые я могу создавать и использовать.

У меня есть два связанных массива: «times» и «values». Они оба содержат значения с плавающей запятой. Я хочу численно отсортировать массив «times», но должен быть уверен, что те же операции применяются к массиву «values». Какой самый эффективный способ сделать это без таких преимуществ, как рекурсия?

Answer 1

Вы можете вести таблицу индексов и сортировать таблицу индексов.

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

И когда вам нужно отсортированное значение, вы можете искать по отсортированному индексу.

И если в будущем вы решили, что будет третье значение, код сортировки не потребует никаких изменений.

Вот пример на C #, но его нетрудно адаптировать к вашему языку сценариев:

static void Main() {

    var r = new Random();

    // initialize random data
    var index = new int[10];      // the index table
    var times = new double[10];   // times 
    var values = new double[10];  // values

    for (int i = 0; i < 10; i++) {
        index[i] = i;
        times[i] = r.NextDouble();
        values[i] = r.NextDouble();
    }

    // a naive bubble sort
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)

            // compare time value at current index
            if (times[index[i]] < times[index[j]]) {

                // swap index value (times and values remain unchanged)
                var temp = index[i];
                index[i] = index[j];
                index[j] = temp;
            }

    // check if the result is correct
    for (int i = 0; i < 10; i++)
        Console.WriteLine(times[index[i]]);

    Console.ReadKey();

}

Примечание: я использовал наивный вид пузырьков, осторожно. В вашем случае, вставка сортировки, вероятно, является хорошим кандидатом. Поскольку вам не нужны сложные рекурсии.

Answer 2

Взгляните на Bottom-Up mergesort в Algorithmist . Это нерекурсивный способ выполнения слияния. Представленная там версия использует вызовы функций, но их можно легко встроить.

Как сказал Мартинус, каждый раз, когда вы меняете значение в одном массиве, делайте то же самое в параллельном массиве.

Вот C-подобная версия стабильной нерекурсивной сортировки слиянием, которая не вызывает функции и не использует рекурсию.

const int arrayLength = 40;
float times_array[arrayLength];
float values_array[arrayLength];

// Fill the two arrays....

// Allocate two buffers
float times_buffer[arrayLength];
float values_buffer[arrayLength];
int blockSize = 1;

while (blockSize <= arrayLength)
{
    int i = 0;
    while (i < arrayLength-blockSize)
    {
        int begin1 = i;
        int end1 = begin1 + blockSize;
        int begin2 = end1;
        int end2 = begin2 + blockSize;

        int bufferIndex = begin1;
        while (begin1 < end1 && begin2 < end2)
        {
            if ( values_array[begin1] > times_array[begin2] )
            {
                times_buffer[bufferIndex] = times_array[begin2];
                values_buffer[bufferIndex++] = values_array[begin2++];
            }
            else
            {
                times_buffer[bufferIndex] = times_array[begin1];
                values_buffer[bufferIndex++] = values_array[begin1++];
            }
        }
        while ( begin1 < end1 )
        {
            times_buffer[bufferIndex] = times_array[begin1];
            values_buffer[bufferIndex++] = values_array[begin1++];
        }
        while ( begin2 < end2 )
        {
            times_buffer[bufferIndex] = times_array[begin2];
            values_buffer[bufferIndex++] = values_array[begin2++];
        }

        for (int k = i; k < i + 2 * blockSize; ++k)
        {
            times_array[k] = times_buffer[k];
            values_array[k] = values_buffer[k];
        }

        i += 2 * blockSize;
    }
    blockSize *= 2;
}

Answer 3

Просто возьмите свой любимый алгоритм сортировки (например, Quicksort или Mergesort) и используйте его для сортировки массива «values». Всякий раз, когда два значения меняются местами в «значениях», также меняйте местами значения с одинаковыми индексами в массиве «times».

Таким образом, вы можете использовать любой алгоритм быстрой сортировки и изменить операцию swap (), чтобы элементы в обоих массивах были поменяны местами.

Answer 4

Я бы не советовал писать собственную процедуру сортировки, поскольку процедуры сортировки, предоставляемые как часть языка Java, хорошо оптимизированы.

Чтобы решить эту проблему, скопируйте код из класса java.util.Arrays в свой собственный класс, т.е. org.mydomain.util.Arrays. И добавьте несколько комментариев, говорящих себе не использовать класс, за исключением случаев, когда вы должны иметь дополнительные функциональные возможности, которые вы собираетесь добавить. Класс Arrays довольно стабилен, поэтому он менее, менее идеален, чем может показаться, но все же он не идеален. Однако методы, которые вам нужно изменить, являются закрытыми, поэтому у вас нет реального выбора.

Затем вы хотите создать интерфейс в соответствии с:
public static interface SwapHook {<br /> void swap(int a, int b);<br /> }<br /></p> <p>You then need to add this to the sort method you're going to use, and to every subordinate method called in the sorting procedure, which swaps elements in your primary array. You arrange for the hook to get called by your modified sorting routine, and you can then implement the SortHook interface to achieve the behaviour you want in any secondary (e.g. parallel) arrays.</p> <p>HTH.