Qsort - чередующийся порядок сортировки

У меня есть программа, которая использует (и должна продолжать использовать) старую функцию сортировки, реализующую qsort. Я также должен предоставить функции сортировки правильные данные для сортировки данных как по возрастанию (если строка содержит четные числа), так и по убыванию (если строка содержит нечетные числа).

Для этого данные должны быть изменены, функция сортировки не может быть изменена.

Код написан на C, но у меня нет соответствующего фрагмента кода для этой конкретной проблемы.

Настоящий вопрос:

Как мне преобразовать данные, чтобы результат соответствовал желаемому результату ниже?

У меня есть следующие данные (или аналогичные)

String 1
String 2
String 3
String 4
String 5
String 6

РЕДАКТИРОВАТЬ: данные представляют собой количество строк типа char **, число в каждой строке представляет собой int.

Желаемый результат

String 5
String 3
String 1
String 2
String 4
String 6

Сортировка обычно выполняется по убыванию в соответствии с вводом 1:1. Мне удалось произвести преобразование, отображающее следующий вывод, добавив 1 или 0 к числам, следующим за строкой.

Итак, внутренние данные для сортировки выглядят так

String 01
String 12
String 03
String 14
String 05
String 16

Это дает следующий вывод (преобразование используется только при сортировке и является временным).

String 1
String 3
String 5
String 2
String 4
String 6

c algorithm data-structures qsort
person Peter Lindqvist    schedule 27.12.2010    source источник

Ответы (4)


arrow_upward
3
arrow_downward

У вас должна быть структура, содержащая данные и значение:

Struct DataValue
{
   string data;
   int value;
}

например {"01", 1} Затем отсортируйте по значению и выведите данные, сортировка несложная, если вы хотите выполнить обычную сортировку: сначала отсортируйте по значению, чтобы составить список, подобный тому, что вы показали. (для значений) теперь создайте пустой массив значений данных (с размером базового массива), начните с последнего элемента и заполните его, как показано ниже:

    int j = 0;
    for (int i = a.Count - 1; i >= 0; i -= 2) // fill bottom of list
    {
        b[a.Count - 1 - j] = a[i];
        j++;
    }

    j = 0;
    for (int i = a.Count - 2; i >= 0; i -= 2)  // fill root of list
    {
        b[j] = a[i];
        j++;
    }

Наконец выведите значения.

Я написал это на С#, это не сильно отличается от С. ты получишь:

  List<int> a = new List<int>{1,2,3,4,5,6,7};

   b==> 6,4,2,1,3,5,7

and for:
  List<int> a = new List<int>{1,2,3,4,5,6};
  b==> 5,3,1,2,4,6
person Saeed Amiri    schedule 27.12.2010
comment
На самом деле это очень похоже на то, что у меня есть, разница в том, что у меня есть данные в файлах, а значение находится в моей внутренней структуре сортировки. Эм, надеюсь, это имеет смысл. - person Peter Lindqvist; 27.12.2010
comment
Это не plug and play, но это вдохновило меня, спасибо! - person Peter Lindqvist; 27.12.2010
comment
@Peter Lindqvist, если данные похожи на строку 01, вы можете обрезать их, чтобы получить 1, и выполнить сортировку в памяти, но, если размер файла большой (что вызывает исключение) и вы не можете прочитать его в памяти, вы можете использовать в методах сортировки на месте для их сортировки см. en.wikipedia.org/wiki/In-place_algorithm - person Saeed Amiri; 27.12.2010

arrow_upward
2
arrow_downward

Это можно сделать на месте (то есть с одним массивом значений и не требующим отдельного списка), используя пользовательскую процедуру сравнения. Функция ниже предполагает, что вы сортируете строки напрямую. Вероятно, лучше предварительно обработать данные, чтобы вы извлекли число из строки и поместили оба в структуру. Но это даст вам идею.

Вы должны передать указатель на эту функцию сравнения в qsort.

int Comparer(void * v1, void * v2)
{
    char *s1 = (char *)v1;
    char *s2 = (char *)v2;

    // Here, extract the numbers from the ends of the strings.
    int n1 = // extract number
    int n2 = // extract number

    // First comparison sorts odd numbers above even numbers
    if ((n1 % 2) == 1)
    {
        // first number is odd
        if ((n2 % 2) == 1)
        {
            // second number is odd, so sort the numbers ascending
            return (n1 - n2);
        }
        else
        {
            // second number is even, which is "greater than" any odd number
            return -1;
        }
    }
    else
    {
        // first number is even
        if ((n2 % 2) == 0)
        {
            // second number is even, so sort the numbers descending
            return (n2 - n1);
        }
        else
        {
            // second number is odd, which is "less than" any even number
            return 1;
        }
    }
}
person Jim Mischel    schedule 27.12.2010
comment
Это правильное решение, но я боюсь, что его нельзя применить в моей среде. - person Peter Lindqvist; 28.12.2010

arrow_upward
1
arrow_downward

Добавьте 9-i, если i нечетное. В противном случае добавьте 9.

person Oswald    schedule 27.12.2010
comment
Возможно, если я предполагаю, что 9 - это сокращение от INT_MAX - person Peter Lindqvist; 27.12.2010

arrow_upward
1
arrow_downward

  1. Предварительная обработка: поместите четные строки в список (назовем этот список _evens_) и поместите нечетные строки в отдельный список (назовем _odds_)
  2. Отсортировать оба списка
  3. Create a destination list
  4. Treat the _odds_ list as a stack: pop the top of _odds_ and place the popped element onto the *front* of the destination list.
  5. Treat the _evens_ as a queue: pop the top of the _evens_ and place the popped element at the *end* of the destination list.
person David Weiser    schedule 27.12.2010