Сортировка «Простой обмен (пузырька)»

Отсортировать массив A_1, A_2,…, A_n по возрастанию.

Решение. Идея сортировки заключается в многократных попарных сравнениях рядом стоящих элементов массива и перестановке этих элементов в заданном порядке. Массив просматривают от конца к началу.

В результате первого просмотра наименьший элемент переместится на первое место. В дальнейшем просмотре этот элемент исключаем. Каждый очередной просмотр будет приводить к постановке очередного минимального элемента в левый конец массива. И в результате n-1 раз просмотров (шагов цикла) получаем упорядоченный по возрастанию массив.

Скрипт. var a = new Array ()

for (i=2; i<=n-1; i++) {

for (j= n; j>=i; j--) {

if (a[j-1] < a[j]) {

X = a[j-1];

a[j-1] = a[j];

a[j] = X;

}

} }

Контрольные вопросы

1. Что такое перестановка элементов в массиве?

2. Какие вы знаете типовые задачи перестановки элементов массива?

3. Назовите методы объекта Array, переставляющие элементы массива.

4. Какова функция метода reverse? sort? join?

5. Что значит отсортировать числовой массив?

6. Какие вы знаете алгоритмы сортировки числовых массивов?

7. Какие способы сортировки вы знаете?

8. Какова идея сортировки «Простой выбор»?

9. Какова идея сортировки «Простой обмен»?

Выводы

· Отсортировать массив строковых переменных – значит расположить элементы по алфавиту.

· Для перестановки строковых элементов массива объект Array имеет методы для сортировки – sort и обратной перестановки – reverse

· Метод join объединяет элементы в одну строку.

· Отсортировать числовой массив – значит переставить элементы массива так, чтобы они располагались либо по возрастанию, либо по убыванию.

· Идея сортировки «Простой выбор» заключается в поиске наименьшего элемента и перестановке его с первым элементом массива и т.д.

· Идея сортировки «Простой обмен» заключается в попарных сравнениях рядом стоящих элементов массива и перестановке этих элементов в заданном порядке. Массив просматривают от конца к началу. В результате первого просмотра наименьший элемент переместится на первое место и т.д.

Практическая работа “Задачи сортировки одномерных массивов”

Þ Продемонстрируйте работу программы по плану: анализ структуры программы – в Блокноте; тестирование – в броузере Internet Explorer