Нас просят привести одну последовательность (исходную) к другой (целевой). То есть логично предположить, что одна последовательность в нужном порядке (целевая), а вторая (исходная) - нет. Так надо просто отсортировать исходную последовательность "в целевую".
Так как целевая последовательность по условию не обязательно отсортированная, то при сортировке "к ней" нельзя просто сравнивать элементы исходной последовательности на больше/меньше, так как в этом случае мы получим на выходе сортировку по правилам системы исчисления. В нашем случае надо принять, что целевая последовательность и есть эталонный отсортированный алфавит, и он задает правила сортировки. При сравнении значений из этого алфавита надо понять, в какой позиции алфавита находится значение и использовать его индекс как ключ сортировки (функция less()).
Теперь, а какой алгоритм сортировки использовать, чтобы для перемещения элементов использовать только обмен соседних элементов (функция swap())? Подходит сортировка вставками, когда на каждом шаге неотсортированный элемент последовательно "пропихивается" вниз к отсортированным. Тут как раз можно обойтись только обменом соседних элементов. Сама функция insertion_sort() является универальной и не зависит от компаратора is_less().
#include <stdlib.h>
#include <stdio.h>
void swap(int* a, int i) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
#define N 8
const int etalon[] = { 1, 5, 7, 4, 2, 9, 8, 6 };
int from[N] = { 8, 1, 4, 2, 5, 6, 9, 7 };
void insertion_sort(int* a, int n, int (*is_less)(int, int)) {
int i, j;
for (i = 1; i < n; ++i)
for (j = i - 1; j >= 0 && is_less(a[j + 1], a[j]); j--)
swap(a, j);
}
void print_array(const char* title, const int* a, int n) {
int i;
printf("%9s: ", title);
for (i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
int less(int a, int b) {
int ia = -1, ib = -1;
int i;
for (i = 0; i < N; ++i) {
if (etalon[i] == a) ia = i;
if (etalon[i] == b) ib = i;
if (ia >= 0 && ib >= 0) break;
}
return ia < ib;
}
int main() {
int i, j;
print_array("Original", from, N);
insertion_sort(from, N, less);
print_array("Converted", from, N);
print_array("Etalon", etalon, N);
return 0;
}Запускаем:
Original: 8 1 4 2 5 6 9 7
Converted: 1 5 7 4 2 9 8 6
Etalon: 1 5 7 4 2 9 8 6 Вроде работает.
Теперь что со сложностью. Принято считать, что сортировка вставками - это O(N^2) для худшего случая. Так как для сравнения элементов нам приходится искать линейно по эталонной последовательности на каждом шаге, то это еще O(N). В этоге: O(N^3).
Как вариант ускорения, можно изначально сделать отсортированную по значениям копию эталонной последовательности, и хранить не только значение, но его индекс. В этом случае поиск элемента будет уже занимать не O(N), а O(log(N)), и общая сложность будет O(log(N)*N^2).
В целом, все это не обязательно писать или помнить точную программу. Достаточно запомнить два вывода: алгоритм сортировки, использующий только обмен соседних элементов - это сортировка вставками, а ключ сортировки может быть далеко нетривиальной функцией.
Указание на эти два факта лично я счел бы на однозначно достаточный ответ.
Сообщения
