0

Нужно написать тимсорт на c#. Прочитав алгоритм, я начал реализовывать его, но столкнулся с проблемой. Как мне разбить массив на подмассивы?

Кто не знает принцип работы тимсорта: Берётся массив, и идёт проверка на отсортированные части в массиве, и разбиваются на подмассивы.

Пример:
Входной массив: [1, 5, 8, 4, 3, 0, 7, 3, 2]
Получившиеся подмассивы: [1, 5, 8], [4, 3, 0], [7, 3, 2]

4
  • Во-первых, это описывалось в статье на хабре. Во-вторых, если вы не понимаете как разбить -- то вы можете просто разбить "абы как" для начала, а потом уже улучшать неясные места в алгоритме. Просто пишите код, а не бросайте на очередной трудности. Вот и сейчас - могли бы приложить код, есть он у вас?
    – A K
    31 мая 2021 в 9:39
  • @AK Я читал эту статью. Я не понимаю как мне разбить. Кода у меня нет, т.к. я не совсем понимаю алгоритм. В моём представлении код выглядел так: бежим по массиву, если элемент по индексу i < i + 1 или i >= i + 1, то мы создаём новый массив и добавляем в него элемент, дальше идёт проверка на длину... Но проблема в том, что каждый раз будет создаваться массив с 1 элементом, а заранее создать массивы нельзя, т.к. мы не знаем сколько их будет. Да и по условия в массив будут добавлены все элементы, так что придётся создавать 2 условия.
    – garab00mba
    31 мая 2021 в 9:50
  • 1
    Вам не нужно создавать массивы. Пользуйтесь вместо этого исходным массивом, и запоминайте индексы начала и конца.
    – VladD
    31 мая 2021 в 10:00
  • Тимсорт - это про скорость. Создание подмассивов тут абсолютно не нужно. Пусть ваши методы принимают на входе исходный массив и диапазон индексов, с которым работать. Поглядите реализацию сортировки слиянием (или другой аналогичной), там подобный подход.
    – tym32167
    31 мая 2021 в 14:17

1 ответ 1

0

Я не подскажу вам как реализовать алгоритм, но разбить массив на подмассивы можно с помощью LINQ:

var array = new int[] { 5, 3, 8, 9, 6 ,4};
var subarrays = array
    .Select((s, i) => new { Value = s, Index = i })
    .GroupBy(x => x.Index / 3) // тут 3 - это длинна одного подмассива
    .Select(grp => grp.Select(x => x.Value).ToArray())
    .ToArray();
    
subarrays
    .ToList()
    .ForEach(subarray => Console.WriteLine("[" + string.Join(",", subarray) + "]"));

Вывод:

[5,3,8]
[9,6,4]
5
  • чет лично я как-то не особо понимаю как именно работает строка GroupBy в даном случае. Можешь обьяснить? 31 мая 2021 в 12:05
  • 1
    А, понял. 1,2,3 при делении на 3 будет 1; 3,4,5 при делении на 3 будет 2, И по этим значениям мы групируем. Блин, прикольно 31 мая 2021 в 12:08
  • @Andrew практически. 0, 1 и 2 при делении на 3 будет 0 (округляется до целых), 3, 4, 5 / 3 = 1 и т.д. 31 мая 2021 в 12:12
  • а ну да, округление до меньшего) 31 мая 2021 в 12:30
  • Да в принципе этот линковский алгоритм можно и буквально слизать и получить тот же результат без линка вообще не думая) 31 мая 2021 в 12:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.