СОРТИРОВКА МАССИВА МЕТОДОМ ВСТАВОК (insertion sort). Проект подготовили ученицы 11 «А» класса Тян Анастасия Ежевская Дарья Муниципальное общеобразовательное учреждение средняя общеобразовательная школа 45 Информационно-обзорный проект по информатике по теме: г. Калининград 2008 г.

ЦЕЛИ: освоить метод сортировки массива вставками ; научиться применять этот метод ; научиться применять этот метод ; узнать эффективность этого метода. узнать эффективность этого метода.

При сортировке вставками из массива берется очередной элемент и движется вдоль массива к его началу до тех пор, пока не дойдет до большего себя, а затем становится перед этим большим элементом, передвигая участок массива. Покажем этот метод на примере сортировки массива А(5) А индекс элемента значение элемента

пример: Вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз – до тех пор, пока не найдем место куда нужно вставить число 3.

Этот процесс продолжается для числа 1.

Завершаем сортировку, поместив число 2 на нужное место.

Постановка задачи: Дано: неупорядоченный числовой массив; A – имя массива; n - размер массива; i – индекс элемента; m – элемент массива, с которым работаем (начиная со второго); k – индекс элемента, стоящего перед элементом m. Требуется: упорядочить числовой массив по возрастанию.

нет да i = 2 a (k + 1) = m i = i + 1 m a (k) k>=1 i n a (k + 1) = a (k) m = a (i) K = i - 1 k = k - 1 Блок схема

I = 2 пока I<=N нц k = I-1 M= A(I) пока M =1 нц A(k+1)=A(k) k=k-1 кц A(k+1) = M I = I+1 кц

FOR i = 2 TO n m=a(i) m=a(i) k=i-1 k=i-1 WHILE (k>=1) AND a(k)>m WHILE (k>=1) AND a(k)>m a(k+1)=a(k) a(k+1)=a(k) k=k-1 k=k-1 WEND WEND a(k+1)=m a(k+1)=m NEXT i

МЕТОД В ЖИЗНИ: В обычной жизни мы сталкиваемся с этим методом при игре в карты. Большинство картежников, сами того не сознавая, пользуются именно таким методом сортировки для упорядочения пришедших им карт. Когда игрок получает очередную карту, все предыдущие уже отсортированы, поэтому он просто вставляет ее в нужное место.

ПРЕИМУЩЕСТВА: прост в реализации; прост в реализации; не требует дополнительной памяти; не требует дополнительной памяти; эффективен на небольших наборах данных; эффективен на небольших наборах данных; эффективен на наборах данных, которые уже частично отсортированы; эффективен на наборах данных, которые уже частично отсортированы; это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы); может сортировать список по мере его получения. может сортировать список по мере его получения. Основной недостаток: необходимость многократного сдвига элементов.

Использованные ресурсы: