Вот проблема
Сортировка неисправностей
Основная операция стандартного алгоритма пузырьковой сортировки заключается в проверке пары соседних чисел и обратномпара, если левое число больше правого. Но наш алгоритм проверяет группу из трех смежных чисел, и если крайнее левое число больше, чем крайнее правое число, оно переворачивает всю эту группу.
Поскольку наш алгоритм является «триплетной сортировкой пузырьков», для краткости мы назвали его «Сортировка неисправностей».
Например, для L = 5 6 6 4 3, Сортировка неисправностей будет выполняться следующим образом:
- Первый проход:
- проверить 5 6 6, ничего не делать: 5 6 6 4 3
- проверить 6 6 4, см. 6> 4, обратный ходтриплет: 5 4 6 6 3
- осмотрите 6 6 3, посмотрите, что 6> 3, переверните триплет: 5 4 3 6 6
- Второй проход:
- осмотреть 5 4 3, увидеть, что 5> 3, перевернуть триплет: 3 4 5 6 6
- осмотреть 4 5 6, ничего не делать: 3 4 5 6 6
- осмотреть 5 6 6, ничего не делать: 3 4 5 6 6
- Затем третий проход проверяет три триплета и ничего не делает, поэтому алгоритм завершается.
Возможно, что Trouble Sort неправильно сортирует список! Рассмотрим, например, список 8 9 7.
Учитывая список из N целых чисел, определите, будет ли функция сортировки по неисправностям успешно отсортировать список в неубывающем порядке. Если этого не произойдет, найдите индекс (начиная с 0) первой ошибки сортировки после завершения алгоритма: то есть первое значение, превышающее значение, которое следует сразу после него, когда алгоритм будет выполнен.
Вход
В первой строке ввода указано количество тестов, T . T . Каждый тестовый пример состоит из двух строк: одна строка с целым числом N , количество значений в списке, а затем другая строка с N целыми числами V i, список значений.
Выход
Для каждого теста выведите одну строку, содержащую Case #x: y, где x - номер теста (начиная с1) и y равно OK, если при сортировке по ошибкам правильно сортируется список или индекс (начиная с 0) первой ошибки сортировки, как описано выше.
Пример
Input | Output
-----------+-------------
2 |
5 |
5 6 8 4 3 | Case #1: OK
3 |
8 9 7 | Case #2: 1
Пример варианта № 1 аналогичен первому, описанному в формулировке проблемы. Функция «Сортировка по ошибкам» правильно сортирует этот список, поэтому ответ «ОК».
Пример 2 - это второй случай, описанный в формулировке проблемы. Trouble Sort неправильно сортирует этот список, так как он заканчивается списком 7 9 8. 9 - это первое значение в списке, которое больше следующего значения, поэтому индекс первой ошибки сортировки равен 1.
Набор тестов 1 Подобно пузырьковой сортировке, Trouble Sort имеет сложность времени O (N2);доказательство объяснено ниже. С N ≤ 100 для тестового набора 1 мы можем запустить Trouble Sort до завершения и просто выполнить итерацию по списку результатов, чтобы найти первую ошибку сортировки, если она есть (то есть значение, которое больше, чем значение, следующее за ним в списке).
Тестовый набор 2 Выполняется O (N2) Неполадка Сортировка до завершения выполняется слишком медленно для N ≤ 105.
Вместо этого давайте разберемся, что именно делает Сортировка неисправностей на каждом шаге. Рассмотрим входной список из 6 элементов. При сортировке по ошибкам при каждом проходе массива выполняется следующее сравнение:
элемент 0 ↔ элемент 2 элемент 1 ↔ элемент 3 элемент 2 ↔ элемент 4 элемент 3 ↔ элемент 5 Независимо отДля длины списка эта таблица иллюстрирует фундаментальный недостаток в сортировке неисправностей: элементы четного индекса сравниваются с другими элементами четного индекса, а элементы нечетного индекса сравниваются с другими элементами нечетного индекса, но четного индекса и нечетного-индексные элементы никогда не сравниваются друг с другом! Это означает, что Trouble Sort - это просто пузырьковая сортировка, запускаемая отдельно для элементов четного индекса и элементов нечетного индекса, чередуя их в выходном списке. Сортировка неисправностей является правильной только в том случае, если при чередовании двух подсписков (список четных индексов и список нечетных индексов) получается другой отсортированный список. Поскольку имеются элементы четного индекса O (N) и нечетного индекса O (N), а сортировка пузырьков - это O (N2), сортировка неисправностей также равна O (N2).
Для решения тестового набора 2мы можем запустить наш любимый алгоритм сортировки O (N log N) независимо в двух подсписках, описанных выше, чередовать отсортированные подсписки, а затем найти первую ошибку сортировки, как в нашем решении для тестового набора 1.
То, что я уже пробовал, - это минимизировать использование вложенных для, чтобы уменьшить сложность времени, и я не смог найти другой способ проверить, отсортирован ли мой массив, кроме проверки всех мест и возврата индекса, алгоритм сортировки неработа
Вот полный код, и я правильно его реализую, потому что, когда дается первый тестовый пример, он дает результат, но затем он превышает время, составляющее 20 секунд, idk, если есть другое решение для этого.
import 'dart:io';
import 'dart:math' as math;
import 'dart:async';
import 'dart:convert';
Stream<String> readLine() => stdin
.transform(utf8.decoder)
.transform(const LineSplitter());
main() {
String stringCase;
//List<String> results =[];
int numberOfCases = int.parse(stdin.readLineSync());
stdout.flush();
// we read the input as google wants,
BytesBuilder builder = new BytesBuilder();
for (int i = 1; i <= numberOfCases; i++) {
int size = int.parse(stdin.readLineSync());
List<int> lint = new List(size);
for (int j = 0; j < size; j++) {
int char = stdin.readByteSync();
while (char >= 48 && char <= 57) {
builder.addByte(char);
char = stdin.readByteSync();
}
lint[j] = int.parse(String.fromCharCodes(builder.takeBytes()));
}
//print(lint);
if(lint.length > 1 && lint.length <= math.pow(10, 9)){
print("Case #${i}: ${separateArray(lint)}");
stdout.flush();
}
}
return 0;
}
separateArray(array){
List<int> odds = new List((array.length / 2).floor());
List<int> evens= new List(array.length - odds.length);
int m, n;
m = 0;
n = 0;
for(var i = 0; i<array.length; i++){
if(i%2==0){
evens[n] = array[i];
n++;
}
if(i%2!=0){
odds[m] = array[i];
m++;
}
}
evens = evens..sort();
odds = odds..sort();
var j=0,k=0;
for(var i=0; i<array.length-1;i++){
if(i%2==0){
if (evens[j] > odds[k]) {
return i;
}
j++;
}else{
if (odds[k] > evens[j]) {
return i;
}
k++;
}
}
return "OK";
}
ИДК Если вы, ребята, видите что-нибудь, я не вижу. Буду признателен за помощь