3 Этап Составление программ

19. Методика введение понятия о методах сортировки табличной информации

3 этапа обучения: 1) Подготовительный этап предназначен для введения терминологии. 2) Этап работы с готовыми документами предназначен для осознания и усвоения учениками работы с электронными документами с использованием электронных инструментов. 3) Этап построения документа предназначен для формирования приемов построения электронных документов с использованием электронных инструментов.

1 Этап Подготовительный

Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел.

СОРТИРОВКА ОБМЕНОМ (методом "пузырька")

Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент ("всплыл" первый "пузырек"). Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O(N*N).

СОРТИРОВКА ВЫБОРОМ

Идея метода заключается в том, что находится максимальный элемент массива и меняется местами с последним элементом (с номером N). Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2.

Вычислительная сложность сортировки выбором - величина порядка N*(N-1)/2, что обычно записывают как O(N*(N-1)/2). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.

2 Этап Работа с готовыми программами

Обработка массивов

1.Сортировка методом «пузырька»

For i = 0 To p - 1

For j = 0 To p – i-1

If M(j) > M(j + 1) Then

temp = M(j)

M(j) = M(j + 1)

M(j + 1) = temp

End If

Next j

ListBox1.Items.Add(Convert.ToString(M(i)))

Next i

2.Сортировка выбором

For i = 1 To n-1

imax = i

For j = i + 1 To n

If c(j) < c(imax) Then

imax = j

End If

Next

temp = c(i)

c(i) = c(imax)

c(imax) = temp

ListBox1.Items.Add(Convert.ToString(c(i)))

Next