Chapter 17: Сортировка

Бинарный поиск работает только с отсортированными списками. Так как же программы приводят списки в порядок? Как программа сортирует список с элементами, когда пользователь щёлкает на заголовке столбца или в каком-либо другом случае?

Существует несколько алгоритмов, делающих это. Два простейших алгоритма - сортировка выбором, а также сортировка вставками. Существуют и другие алгоритмы, такие как сортировка Шелла, слиянием, пирамидальная, а также быстрая сортировки.

Чтобы увидеть основные алгоритмы сортировки в действии, посетите страничку:
http://www.sorting-algorithms.com/

Каждая сортировка содержит в себе свои преимущества и недостатки. Некоторые сортируют списки быстрее, если список с самого начала находится в практически отсортированном состоянии. Некоторые сортируют список быстрее, если элементы списока находится в полностью случайной последовательности. Другие списки сортируют быстро, но требуют много памяти.

17.1 Обмен значениями

Обменивать два значения в массиве местами - обычная операция для многих алгоритмов сортировки. Например, предположим, что у программы есть список, выглядящий следующим образом:

list = [15,57,14,33,72,79,26,56,42,40]

Разработчик хочет поменять местами позиции 0 и 2, которые содержат числа 15 и 14 соответственно.

Первая попытка написания кода может выглядеть чем-то вроде:

list[0] = list[2]
list[2] = list[0]

Очевидно, это не работает. Первое присвоение list[0] = list[2] заставляет значение 15, существующее на позиции 0, быть переписанным числом 14 из позиции 2, тем самым невосстановимо теряясь. Следующая строка, list[2] = list[0] просто копирует 14 обратно в ячейку 2, в которой уже хранится 14.

Для починки этой проблемы, смена значений внутри массива должно осуществляться за три шага. Нужно создать временную переменную, хранящую информацию во время процедуры обмена. Код обмена выглядит следующим образом:

temp = list[0]
list[0] = list[2]
list[2] = temp

Первая строка копирует значение из ячейки 0 в переменную temp. Это позволяет коду перезаписать значение в ячейке 0 значением из ячейки 2 без потери данных. Последняя строка берёт старое значение из 0й ячейки, содержащееся в переменной temp и сохраняет его в ячейку 2.

17.2 Сортировка выбором

The selection sort starts at the beginning of the list. Then code next scans the rest of the list to find the smallest number. The smallest number is swapped into location. The code then moves on to the next number. Graphically, the sort looks like the following image:

Код для сортировки выбором включает в себя два гнездящихся цикла. Внешний цикл следит за текущей позицией, в которую мы хотим записать меньшее значение, осуществив тем самым обмен двух ячеек. Внутренний цикл начинает в текущей позиции и проверяет значения справа, ища наименьшее. Когда он находит минимальное значение, происходит обмен.

# Сортировка выбором
def selection_sort(list):
    # Пройти через весь массив
    for curPos in range( len(list) ):
		# Найти позицию с минимальным числом
		# Начать с текущей позиции
        minPos = curPos
		# Сканировать правую часть
        for scanPos in range(curPos+1, len(list) ):
			# Эта позиция наименьшая?
            if list[scanPos] < list[minPos]:
				# Да, отметим эту позицию как наименьшую
                minPos = scanPos
        
        # Поменять местами два значения
        temp = list[minPos]
        list[minPos] = list[curPos]
        list[curPos] = temp

Внешний цикл всегда будет идти $n$ раз. Внутренний цикл будет идти $n/2$ раз. Так будет всегда, вне зависимости от того, находится ли список в порядке или нет. Эффективность циклов может быть улучшена, если мы будем проверять, равны ли minPos и curPos на 16й строке. Если они равны, нет надобности выполнять три строки по обмену значений переменных.

Для проверки работы вышеприведённого кода сортировки выбором, можно использовать следующий код. Первая функция выведет список. Следующий код создать список случайных чисел, выведет его, отсортирует, а затем выведет его снова.

def print_list(list):
    for item in list:
        print( "%3d" % item,end="" )
    print()
	
# Создать список случайных чисел
list = []
for i in range(10):
    list.append(random.randrange(100))

# Проверить сортировку
print_list(list)
selection_sort(list)		
print_list(list)

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

Сортировка вставками разбивает список на два отрезка, “отсортированная” и “неотсортированная” части. В каждой итерации внешнего цикла, алгоритм возьмёт следующий неотсортированный элемент и поставит его в отсортированную часть.

В нижеприведённом коде, keyPos означает границу между отсортированной и неотсортированной частью списка. Алгоритм проверяет левую часть от keyPos используя переменную scanPos. Заметьте, что в сортировке вставками, scanPos уменьшается, а не увеличивается. Адрес каждой ячейки, значение которой больше чем keyValue двигается наверх (вправо) на одну ячейку. Когда цикл находит позицию с меньшим элементом, чем keyValue, он останавливается и кладёт keyValue справа от него.

Внешний цикл в сортировке вставками пройдёт $n$ раз. Внутренний цикл в среднем будет проходить $n/2$ раз, если массив случайно отсортирован. Если список очень близок к отсортированному, тогда внутренний цикл не будет вызываться слишком часто, а время выполнения сортировки будет близко к $n$.

def insertion_sort(list):
    # Начать со второго элемента (pos 1).
    # Использовать этот элемент для вставки
    # в список.
    for keyPos in range(1, len(list)):
        # Получить значения элемента для вставки
        keyValue = list[keyPos]
        # Сканировать левую часть
        scanPos = keyPos - 1
        # Пройти через каждый элемент, двигая их вверх
        # до момента, когда мы достигнем ячейки с меньшим элементом
        while (scanPos >=0) and (list[scanPos] > keyValue):
            list[scanPos+1] = list[scanPos]
            scanPos = scanPos - 1
        # Всё было передвинуто, теперь вставим элемент
        # справа от последней ячейки
        list[scanPos+1] = keyValue

17.4 Проверка пройденного

Эти вопросы можно скачать в виде бланка (на английском):
[docx] [doc] [pdf]

После заполнения бланка, вы можете проверить свои ответы, сверив их со списком атветов. Их можно скачать здесь:
[docx] [doc] [pdf]
Видео с полным объяснением ответов может быть найдено [здесь].

17.4.1 Предыдущие главы

1. Напишите цикл “for”, который выведет горизонтальную линию из десяти звёздочек (*).
2. Напишите два гнездящихся цикла for, которые выведет квадрат 10x10 из звёздочек.
3. Напишите Python код, который создаст массив из 100 нулей.
4. Какая разница между классом и объектом?
5. Какая разница между функцией и методом?
6. Напишите функцию, которая выведет на экран ваше любимое число.
7. Вызовите функцию, которая выводит ваше любимое число на экран.
8. Напишите функцию, которая берёт три числа и возвращает среднее арифметическое этих чисел.
9. Программирование классов:
   1. Напишите код для класса Ball(мяч). Задайте ему аттрибуты для позиции и скорости.
   2. Создайте метод update(), двигающий позицию мяча относительно его скорости.
   3. Создайте инстанцию класса Ball, задайте его аттрибуты.
   4. Создайте цикл for, который будет вызывать метод update() на мяче 10 раз, а также выводить позицию мяча.

17.4.2 Глава о сортировке

10. Напишите код для обмена местами чисел 25 и 40.

    list = [55, 41, 52, 68, 45, 27, 40, 25, 37, 26]
    

11. Напишите код для обмена местами чисел 2 и 27.

    list = [27, 32, 18,  2, 11, 57, 14, 38, 19, 91]
    

12. Почему не работает следующий код?

    list = [70, 32, 98, 88, 92, 36, 81, 83, 87, 66]
    temp = list[0]
    list[1] = list[0]
    list[0] = temp 
    

13. Покажите, как сортируется следующий список чисел, используя сортировку выбором:

    

14. Покажите, как сортируется следующий список чисел, используя сортировку выбором:

    

15. Покажите, как сортируется следующий список чисел, используя сортировку вставкой:

    

16. Покажите, как сортируется следующий список чисел, используя сортировку вставкой:

    

17. Объясните, что делает minPos в сортировке выбором.
18. Объясните, что делает curPos в сортировке выбором.
19. Объясните, что делает scanPos в сортировке выбором.
20. Объясните, что делают keyPos и keyValue в сортировке вставками.
21. Объясните, что делает scanPos в сортировке вставками.
22. Измените сортировки, чтобы они выводили количество раз, которое выполнились внешний и внутренние циклы.

You are not logged in. Log in here and track your progress.