Как узнать, когда ShearSorting сделан
В настоящее время я занимаюсь сортировкой shearSorting и не могу понять, когда эта операция должна выполняться с матрицей nxn.
В настоящее время я копирую матрицу в начале каждой итерации цикла во временную матрицу, а затем в конце каждой итерации цикла сравниваю исходную и временную матрицы, и если они одинаковые, тогда я вырываюсь из цикла и выхожу. Мне не нравится этот подход, так как мы всегда заканчиваем одну дополнительную итерацию после сортировки и выполнения матрицы, что является пустой тратой процессорного времени и циклов.
Там должен быть лучший способ сделать эту проверку. Я продолжаю находить ссылки на log(n), чтобы указать, сколько итераций нам нужно, но я не верю, что они означают фактический log(n) как log(5) для матрицы 5x5 в 0,69, что невозможно для числа итераций.
Какие-либо предложения?
1 ответ
Так что я знаю, что shearSort берет итерации журнала (n) для завершения, поэтому для случая матрицы 5x5 у нас будет 3 прогона для строк и 3 прогона для столбцов. Но что, если матрица 5x5, которую мне дали, в некотором роде почти отсортирована, и для ее завершения требуется всего одна или две итерации, в этом случае я не вижу смысла повторять ее 6 раз, поскольку это будет считаться пустой тратой мощности процессора и циклы.
Также у нас есть следующее решение: если мы копируем матрицу в начале каждой итерации функции shearSort во временную матрицу, а в конце каждой итерации мы сравниваем 2 матрицы вместе, и они совпадают, то мы знаем, что мы закончили (Обратите внимание, что итерация будет означать сортировку как строки, так и столбца, так как матрица может сначала не нуждаться в сортировке строк, но после нее потребуется сортировка столбцов). В этом случае мы сохраним циклы ЦП, если матрица не нуждается в N + 1 итерациях, но это решение создаст проблему, которая заключается в том, что когда требуется N + 1 итераций, мы выполняем N + 3 итерации для завершения (дополнительные 2 итерации - это одна, чтобы проверить, совпадают ли 2 матрицы для строки и одна для столбца).
Чтобы решить эту проблему, мы должны использовать комбинацию обоих решений:
мы все равно будем копировать матрицу в начале и сравнивать ее с временной матрицей в конце, и если они равны, прежде чем мы перейдем к итерациям N + 1, то все готово, и нам не нужно идти дальше, и если они затем мы переходим к N + 1 итерации и останавливаемся после того, как мы знаем, что в этот момент матрица должна быть отсортирована после N + 1 итерации.