Как отсортировать один массив на основе порядка его объекта в другом массиве в target-c?

Question

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

Пример
oldElementList: [1, 4, 2, 8] ---> пользователь установил этот порядок
newElementList: [1, 4, 3, 8]

В качестве вывода я хочу получить: [1, 4, 8, 3]

На самом деле элементы - это не числа, а объекты. и когда они получены с сервера, некоторые значения их свойств могли измениться.

Мой ответ:

for (ElementModel *oldElement in oldElementList) {
            for (ElementModel * newElement in newElementList) {
                if ([newElement.number isEqualToString: oldElement.number]) {
                    [sortedArray addObject: newElement];
                    [newElementList removeObject: newElement];

                    break;
                }
            }
        }

        for (ElementModel *newElement in newElementList) {
            [sortedArray addObject: newElement];
        }

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

Answer 1

Какой алгоритм сортировки является подходящим, в значительной степени зависит от ваших данных, например:
- Является ли набор данных, подлежащий сортировке, большим (только тогда сложные алгоритмы могут окупиться)?
- Является ли набор данных равнымбыть отсортированы полностью случайным образом или предварительно отсортированы?
Из вашего описания мне кажется, что у вас большой набор данных (в противном случае любые алгоритмы, дающие правильный результат, вероятно, подойдут, включая ваш собственный, имеющий сложность O (n ^ 2)) и что он предварительно отсортирован, т. е. имеется только несколько добавлений и удалений (в противном случае сохранение исходной сортировки может быть не столь важным).
Если да, то как насчет следующего алгоритма (извините, он вБыстро, но, несомненно, может быть легко преобразовано в Obj-C):

let old = [1, 4, 2, 7, 8]
let new = [1, 4, 3, 8, 2]

var oldIndexed: [Int: Int] = [:]
for i in 0 ..< old.count {
    oldIndexed[old[i]] = i
}
var newIndexed: [Int: Int] = [:]
for i in 0 ..< new.count {
    newIndexed[new[i]] = oldIndexed[new[i]] ?? old.count
}
var resultArray: [(Int, Int)] = []
for (key, value) in newIndexed {
    resultArray.append((key, value))
}
resultArray = resultArray.sorted { (first, second) -> Bool in
    first.1 < second.1
}
let result = resultArray.map{ $0.0 } // Here: [1, 4, 2, 8, 3]

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

РЕДАКТИРОВАТЬ:

Я долгое время не программировал в Obj-C, но попробовал еще раз просто для развлечения:

NSArray *old = @[@1, @4, @2, @7, @8];
NSArray *new = @[@1, @4, @3, @8, @2];

NSMutableDictionary *oldIndexed = [[NSMutableDictionary alloc] init];
for (int i = 0; i < old.count; i++) {
    [oldIndexed setValue:[NSNumber numberWithInt: i] forKey: old[i]];
}

NSMutableDictionary *newIndexed = [[NSMutableDictionary alloc] init];
long counter = old.count;
for (int i = 0; i < old.count; i++) {
    NSNumber *oldIndexOfNewValue = oldIndexed[new[i]];
    NSNumber *newIndex;
    if (oldIndexOfNewValue != nil) {
        newIndex = oldIndexOfNewValue;
    } else {
        newIndex = [NSNumber numberWithLong: counter];
        counter++;
    }
    [newIndexed setValue: newIndex forKey: new[i]];
}

NSMutableArray *resultArray = [[NSMutableArray alloc] init];
NSArray *allKeysInNewIndexed = newIndexed.allKeys;
for (int i = 0; i < allKeysInNewIndexed.count; i++) {
    NSNumber *nextKey = allKeysInNewIndexed[i];
    NSArray *nextPair = @[nextKey, newIndexed[nextKey]];
    [resultArray addObject: nextPair];
}

NSArray *sortedResultArray;
sortedResultArray = [resultArray sortedArrayUsingComparator: ^NSComparisonResult(NSArray *first, NSArray *second) {
    NSNumber *firstIndex = first[1];
    NSNumber *secondIndex = second[1];
    return [firstIndex compare: secondIndex];
}];

NSMutableArray * result = [[NSMutableArray alloc] init];
for (int i = 0; i < sortedResultArray.count; i++) {
    [result addObject: sortedResultArray[i][0]];
}