Сортировка массива

Программирование на языке

Python

К.Ю.Поляков

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

1

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

2

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

порядке.

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

Алгоритмы:
• простые и понятные, но неэффективные для больших

массивов
▫ метод пузырька
▫ метод выбора

• сложные, но эффективные

▫ «быстрая сортировка» (QuickSort)
▫ сортировка «кучей» (HeapSort)
▫ сортировка слиянием (MergeSort)
▫ пирамидальная сортировка

время
работы

N

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

3

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

дна вверх.

Для массивов – самый маленький («легкий» элемент

перемещается вверх («всплывает»).

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

4

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
элементов).

!

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

5

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

единственное

отличие!

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

6

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

7

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Метод выбора (минимального элемента)

8

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

первое место.

for i in range(N-1):

найти номер nMin минимального

элемента из A[i]..A[N]

if i != nMin:

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Метод выбора (минимального элемента)

9

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

10

Ч.Э.Хоар

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

который находятся дальше друг от друга.

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

11

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

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

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

A[i] <= X

A[i] >= X

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

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

Медиана – такое значение X, что слева и справа от него в

отсортированном массиве стоит одинаковое число
элементов (для этого надо отсортировать массив…).

78

6

82

67

55

44

34

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

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

12

Разделение:
1) выбрать любой элемент массива (X=67)

2) установить L = 1, R = N
3) увеличивая L, найти первый элемент A[L],

который >= X (должен стоять справа)

4) уменьшая R, найти первый элемент A[R],

который <= X (должен стоять слева)

5) если L<=R то поменять местами A[L] и A[R]

и перейти к п. 3

иначе стоп.

78

6

82

67

55

44

34

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

13

78

6

82

67

55

44

34

L

R

34

6

82

67

55

44

78

L

R

34

6

44

67

55

82

78

L

R

34

6

44

55

67

82

78

R

L

L > R : разделение закончено!
!

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

14

N = 7
A = [0]*N
# заполнить массив
qSort( A, 0, N-1 ) # сортировка
# вывести результат

Основная программа:

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

15

def qSort ( A, nStart, nEnd ):

if nStart >= nEnd: return
L = nStart; R = nEnd
X = A[(L+R)//2]
while L <= R:

while A[L] < X: L += 1
while A[R] > X: R -= 1
if L <= R:

A[L], A[R] = A[R], A[L]
L += 1; R -= 1

qSort ( A, nStart, R )
qSort ( A, L, nEnd )

рекурсивные

вызовы

while A[L] < X: L += 1
while A[R] > X: R -= 1

разделение на

2 части

массив

начало

конец

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

16

Случайный выбор элемента-разделителя:

from random import randint
def qSort ( A, nStart, nEnd ):

...
X = A[randint(L,R)]
...

или так:

from random import choice
def qSort ( A, nStart, nEnd ):

...
X = choice ( A[L:R+1] )
...

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

17

В стиле Python:

from random import choice
def qSort ( A ):

if len(A) <= 1: return A
X = choice(A)
B1 = [ b for b in A

if b < X ]

BX = [ b for b in A

if b == X ]

B2 = [ b for b in A

if b > X ]

return qSort(B1) + BX + qSort(B2)

рекурсивные вызовы

Что плохо?
?

окончание
рекурсии

Asort = qSort( A )

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

18

N

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

метод
выбора

быстрая

сортировка

1000

0,09 с

0,05 с

0,002 с

5000

2,4 с

1,2 с

0,014 с

15000

22 с

11 с

0,046 с

Сортировка массива случайных значений:

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Сортировка в Python

19

B = sorted( A )

алгоритм
Timsort

По возрастанию:

B = sorted( A, reverse = True )

По убыванию:

По последней цифре:

def lastDigit ( n ):

return n % 10

B = sorted( A, key = lastDigit )

или так:

B = sorted( A, key = lambda x: x % 10

)

«лямбда»-функция
(функция без имени)

Алгоритмизация и программирование, язык Python, 10 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Сортировка в Python – на месте

20

A.sort()

По возрастанию:

A.sort ( reverse = True )

По убыванию:

По последней цифре:

def lastDigit ( n ):

return n % 10

A.sort ( key = lastDigit )

или так:

A.sort( key = lambda x: x % 10

)

Multiple Choice

Дана последовательность чисел a1,a2,...an. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый - на место наибольшего. Затем, начиная со второго, эта процедура повторяется.

• сортировка выбором

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

• сортировка вставками

• все ответы правильные

Fill in the Blank

Сколько обменов будет совершено при пузырьковой сортировке массива

3 6 4 1 2 5

по возрастанию?

Fill in the Blank

Производится сортировка по возрастанию массива

3 6 4 1 2 5

методом выбора минимального элемента. Каким станет массив после трех шагов сортировки (трех обменов)?

В ответ запишите элементы массива через пробел.

Multiple Choice

Дана последовательность чисел a1, a2,...an. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа ai и ai+1. Если ai>ai+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не окажутся расположенными в порядке возрастания.

• сортировка выбором

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

• сортировка вставками

• сортировка Шелла

Multiple Select

Какие из приведенных фрагментов корректно выполняют пузырьковую сортировку списка data длины n по возрастанию?

Multiple Choice

Укажите какой сортировке принадлежит фрагмент:

for k in range (k < n - 1):

nmax = k;

for i in range( k + 1, i < n):

if (a[i] > a[nmax])

nmax = i;

if i!= nMin:

a[k], a[nmax] = a[nmax], a[k]

• сортировка выбором

• сортировка обменами

• сортировка вставками

• все варианты верные