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

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

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

1-й проход:

for j in range(N-2, -1 ,-1):

if A[j+1]< A[j]:

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

2-й проход:

for j in range(N-2,  0 ,-1):

if A[j+1]< A[j]:

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

0

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

от N-2 до 0 шаг -1

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

for i in range(N-1):

for j in range(N-2, i-1 ,-1):

if A[j+1] < A[j]:

A[j], A[j+1] = A[j+1], A[j]

i-1

Как написать метод «камня»?

?

Как сделать рекурсивный вариант?

?

Задачи

«A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.

«B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.

«С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.



Идея: найти минимальный элемент и поставить его на первое место.

for i in range(N-1):

найти номер nMin минимального элемента из A[i]..A[N]

if i != nMin:

поменять местами A[i] и A[nMin]



for i in range(N-1):

if i!= nMin:

A[i], A[nMin] = A[nMin], A[i]

nMin = i

for j in range(i+1,N):

if A[j] < A[nMin]:

nMin = j

Задачи

«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.

Пример:

Массив:

5 3 4 2 1 6 3 2

После сортировки:

2 3 4 5 6 3 2 1

Задачи

«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем.

Пример:

Массив:

5 3 4 2 1 6 3 2 4

После сортировки:

1 2 2 3 3 4 4 5 6

Различных чисел: 5

«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

Быстрая сортировка (QuickSort)

Ч.Э.Хоар

Идея: выгоднее переставлять элементы, который находятся дальше друг от друга.

6

5

4

3

2

1

1

5

4

3

2

6

1

2

4

3

5

6

1

2

3

4

5

6

Для массива из N элементов нужно всего N/2 обменов!

!

Быстрая сортировка

Шаг 2: переставить элементы так:

при сортировке элементы не покидают « свою область»!

Шаг 1: выбрать некоторый элемент массива X

A[i] <= X

A[i] >= X

Шаг 3: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

78

6

82

67

55

44

34

Как лучше выбрать X?

?