С возвращением, начинающие инженеры! Сегодня я расскажу вам о нескольких распространенных алгоритмах сортировки списков. Вы, несомненно, в свое время как программисты сталкивались со случаями, когда было полезно, чтобы элементы в списке отображались в отсортированном порядке. При поиске первого экземпляра пользователя в алфавитном порядке, поиске имени первого питомца пользователя в алфавитном порядке или для бесчисленного множества других приложений вы, вероятно, использовали метод array.sort() вашего языка и мало думали об этом. Это хорошо, но при переходе от программирования небольших личных приложений к большому программному обеспечению, ориентированному на коллективную работу с интенсивным использованием данных, полезно иметь представление о том, как создаются эти методы, и о распространенных методах сортировки. Более того, сортировка данных — одно из самых важных и фундаментальных упражнений в компьютерных науках, и время, потраченное на изучение ее передового опыта, — хороший обзор тем, которые будут возникать снова и снова при решении задач cs. Кроме того, если вам зададут вопрос на собеседовании, в котором наличие отсортированного списка может каким-то образом помочь (например, реализовать бинарный поиск), вы сможете продемонстрировать, что знаете, как сортировать список без встроенного метода определенного языка, и что у вас есть хорошее понимание компромиссов между различными алгоритмами.

Сегодня я расскажу об алгоритмах сортировки вставками, сортировки выбором, сортировки слиянием и быстрой сортировки. Есть и другие, о которых вы должны хотя бы быть знакомы, такие как пузырьковая сортировка, сортировка кучей, сортировка ведра и сортировка по основанию, но четыре рассмотренных здесь, возможно, являются наиболее распространенными и представляют собой надежное введение. Главный вывод заключается в том, что некоторые алгоритмы сортировки плохи (конечно, с точки зрения пространственно-временной сложности), но их важно знать, потому что они помогают раскрыть правду о лучших из них и потому что иногда их можно использовать. Все алгоритмы, которые я буду обсуждать, могут быть применены к массивам или связанным спискам, но некоторые из них имеют преимущества для одной структуры данных по сравнению с другой. Я буду обсуждать алгоритмы для массивов конкретно. Итак, давайте поговорим о сортировке выбором.

Сортировка выбором — самый простой алгоритм сортировки, и, по сути, это то, как наивный человек отсортирует список, если его об этом попросят. По сути, сортировка выбором сохраняет указатель на первый несортированный элемент в списке и проходит по списку в поисках минимального элемента. Если элемент min не является первым элементом, они меняются местами, и этот процесс повторяется до тех пор, пока не будет достигнут конец списка. Заметьте, я сказал «первый элемент в несортированном списке». Сортировка выбором поддерживает два списка, один отсортированный, один несортированный. Однако для массивов его можно реализовать «на месте», т. е. без лишней памяти, потому что для начала считается, что отсортированный список имеет длину 0, а несортированный список — это все. При каждом обмене отсортированный список увеличивается на единицу, а несортированный список сжимается на единицу. Очевидно, что поиск каждого минимального элемента — это утомительный процесс O(n), что является нашим первым намеком на то, что сортировка выбором — не очень эффективный алгоритм. Фактически, весь алгоритм выполняется за время O(n²) в лучшем и худшем случае. На коротком примере будет легче понять, как это работает, допустим, у нас есть список 9,2,7,8. Мы проходим по несортированному списку, чтобы найти минимальное значение, которое равно 2, поэтому мы меняем его местами с первым элементом, 9. Это оставляет отсортированный список как 2, а несортированный список как 9,7,8. Затем мы снова проходим по несортированному списку, находим минимум 7 и меняем его местами с первым элементом 9, оставляя 2,7,9,8. Несортированный список теперь содержит 8 и 9, поэтому мы поменяем их местами, чтобы получить окончательный список 2,7,8,9. Псевдокод для сортировки выбором приведен ниже.

function selectionSort(array, length)  
		for i = 1 to  length -1
		    min = i 
				for j = i + 1 to length 
				    if array[j] < array[min] 
				        min = j 
		    swap array[i], array[min]

Следующий алгоритм, который мы обсудим, тоже прост и тоже ПЛОХ. Она называется сортировкой вставками и концептуально похожа на сортировку выбором. Сортировка вставками также выполняется за время O(n²) в худшем случае, но может работать значительно лучше в списках, которые изначально почти отсортированы, и в этом случае временная сложность пропорциональна количеству инверсий (т. приказ). Также как и сортировка выбором, она поддерживает отсортированный и несортированный список и может быть реализована практически таким же образом. Первый элемент берется для сортировки, и вместо того, чтобы найти минимум и поменять местами, как при сортировке выбором, следующий элемент просто добавляется в отсортированный список по порядку. Давайте вернемся к нашему примеру 9,2,7,8, чтобы проиллюстрировать это. 9 берется для сортировки, поэтому мы начинаем с 2. 2 стоит перед 9, поэтому мы перемещаем его в начало, оставляя 2,9,7,8. 7 стоит перед 9 и после 2, поэтому мы перемещаем его на 1 позицию, оставляя 2,7,9,8. 8 стоит перед 9 и после 7, поэтому мы перемещаем его на одну позицию. Суть в том, что при вставке элементов в отсортированный список мы начинаем с конца и перемещаем элемент, пока не найдем тот, который стоит перед ним. Ниже приведен псевдокод этой процедуры.function insertionSort(array, length) for j = 2 to length key = j i = j-1 while i > 0 && array[i] > key array[i+1] = array[i] i = i-1 array[i+1] = key Хорошо. Достаточно неэффективной сортировки для одного дня. Суть в том, что эти два алгоритма плохи, но их полезно изучать, потому что они имитируют то, как мозг естественным образом думает о сортировке, и помогают нам понять, как и почему получаются хорошие алгоритмы. Завтра мы изучим сортировку слиянием и быструю сортировку, которые вы действительно хотите знать и понимать. А пока я оставлю вас с несколькими мудрыми словами физика элементарных частиц Саваса Димополуса из документальной лихорадки частиц. Отличный фильм, посмотрите как-нибудь.

«Ключ к успеху — двигаться от неудачи к неудаче с большим энтузиазмом».

Возможно, я просто вырезал эту цитату. Хотя цитата отличная.

До следующего раза!