Программирование. Программирование на языке Python (Полякова К.Ю.). Общие сведения о языке Python История

• Название: Общие сведения о языке Python История
• Анкор: Программирование
• Дата: 27.02.2023
• Размер: 5.72 Mb.
• Имя файла: Программирование на языке Python (Полякова К.Ю.).ppt
• Тип: Документы; #956875
• страница: 16 из 18

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

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


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

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

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 обменов!


!