Результат: ученик безопасно работает с массивом фиксированной длины, проектирует линейные и сортировочные алгоритмы, выбирает изменение на месте или новый результат и использует упорядоченность как предусловие поиска.

Содержание:

  1. Понять объект одномерного массива

    • тип T[];
    • фиксированная длина после создания;
    • создание через new и инициализатор;
    • значения элементов по умолчанию;
    • пустой массив как корректный объект;
    • Length как число элементов.

  2. Работать с допустимыми индексами

    • полуинтервал [0, Length);
    • первый и последний индекс;
    • проверка непустоты перед доступом к краевому элементу;
    • IndexOutOfRangeException как следствие недопустимой координаты;
    • различие длины и последнего индекса.

  3. Выбирать способ обхода

    • цикл по индексам;
    • foreach для последовательного чтения;
    • прямой и обратный обход;
    • согласованное движение двух индексов;
    • обработанный префикс и непросмотренный суффикс;
    • ограничения изменения элемента через переменную foreach.

  4. Реализовывать линейные агрегаты

    • сумма, произведение и счётчик;
    • первое и последнее вхождение;
    • минимум и максимум;
    • одновременное вычисление нескольких характеристик;
    • нейтральное значение и затравка первым элементом;
    • контракт пустого входа.

  5. Реализовывать линейные преобразования

    • сдвиг;
    • разворот;
    • замена;
    • фильтрация;
    • уплотнение активного префикса;
    • удаление и вставка при фиксированной вместимости;
    • слияние двух последовательностей.

  6. Выбирать модель изменения

    • мутация исходного массива;
    • создание независимого результата;
    • частичное изменение;
    • логическая длина внутри физического массива;
    • дополнительная память;
    • инвариант преобразования на месте.

  7. Передавать массивы методам

    • копирование ссылки при обычной передаче;
    • изменение элементов общего объекта;
    • локальная замена параметра;
    • массив как возвращаемый результат;
    • создание нового объекта;
    • params как специальная форма массива параметров.

  8. Работать с параллельными массивами

    • одинаковая длина;
    • общий индекс как связь полей;
    • согласованная перестановка;
    • согласованная фильтрация;
    • риск нарушения связи;
    • переход к struct после введения собственного типа.

  9. Освоить простые сортировки

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

  10. Освоить сортировку слиянием

    • разделение диапазона;
    • слияние двух упорядоченных частей;
    • дополнительный буфер;
    • O(n log n) времени;
    • устойчивость при правильном выборе равных элементов;
    • сравнение с простой сортировкой.

  11. Понимать контракт Array.Sort

    • сортировка массива на месте;
    • ожидаемый порядок O(n log n) в учебной модели;
    • отсутствие права предполагать устойчивость;
    • необходимость копии для сохранения исходного порядка;
    • сравнение библиотечной операции с собственным алгоритмом.

  12. Реализовывать бинарный поиск

    • обязательная упорядоченность;
    • закрытая или полуоткрытая модель границ;
    • средний индекс без переполнения;
    • сокращение диапазона кандидатов;
    • поиск первого и следующего за последним вхождения;
    • LowerBound и UpperBound;
    • O(log n) сравнений.

  13. Сравнивать альтернативы

    • один проход и несколько проходов;
    • время против дополнительной памяти;
    • линейный поиск против предварительной сортировки и бинарного поиска;
    • сохранение порядка;
    • устойчивость;
    • доказательство инварианта и оценка класса роста.