62. Массивы 63. Алгоритмы обработки массивов

• Название: 62. Массивы 63. Алгоритмы обработки массивов
• Дата: 28.04.2023
• Размер: 1.09 Mb.
• Имя файла: programmirovanie-na-yazyke-python.pptx
• Тип: Документы; #1095573
• страница: 6 из 16

§ 64. Сортировка

Что такое сортировка?

Сортировка – это расстановка элементов массива в заданном порядке.

…по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …

Алгоритмы:

• простые и понятные, но неэффективные для больших массивов
• метод пузырька
• метод выбора
• сложные, но эффективные
• «быстрая сортировка» (QuickSort)
• сортировка «кучей» (HeapSort)
• сортировка слиянием (MergeSort)
• пирамидальная сортировка

время

работы

N

Метод пузырька (сортировка обменами)

Идея: пузырек воздуха в стакане воды поднимается со дна вверх.

Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

4

5

2

1

3

4

5

2

1

3

4

5

1

2

3

1

4

5

2

3

• сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
• за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-й проход:

4

1

5

2

3

Метод пузырька

1

4

5

2

3

1

4

5

2

3

1

4

2

5

3

2-й проход:

3-й проход:

1

2

4

5

3

1

2

3

4

5

1

2

4

5

3

4-й проход:

1

2

3

4

5

1

2

3

4

5

1

2

4

3

5

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

!

Метод пузырька

1-й проход:

сделать для j от N-2 до 0 шаг -1

если A[j+1]< A[j] то

# поменять местами A[j] и A[j+1]

2-й проход:

сделать для j от N-2 до 1 шаг -1

если A[j+1]< A[j] то

# поменять местами A[j] и A[j+1]

1

единственное отличие!