Сортировка в структуре данных: категории и типы [с примерами]

Расположение данных в предпочтительном порядке называется сортировкой в ​​структуре данных. Благодаря сортировке данных поиск по ним становится проще и быстрее. Самый простой пример сортировки — словарь. До эпохи Интернета, когда вы хотели найти слово в словаре, вы делали это в алфавитном порядке. Это упростило задачу.

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

Короче говоря, сортировка облегчает нашу жизнь. Ознакомьтесь с нашими курсами по науке о данных, чтобы узнать больше об алгоритмах обработки данных.

В этом посте мы познакомим вас с различными структурами данных и алгоритмами сортировки. Но сначала давайте разберемся, что такое алгоритм сортировки и сортировка в структуре данных.

Что такое алгоритм сортировки?

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

Многие дети научились бы сортировать структуры данных на уроках информатики. Он вводится на раннем этапе, чтобы помочь заинтересованным детям получить представление о более глубоких темах информатики — методах «разделяй и властвуй», бинарных деревьях, кучах и т. д.

Вот пример того, что делает сортировка.

Предположим, у вас есть массив строк: [h,j,k,i,n,m,o,l]

Теперь сортировка даст выходной массив в алфавитном порядке.

Вывод: [h,i,j,k,l,m,n,o]

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

Оформить заказ: типы бинарного дерева

Сортировка категорий

В сортировке есть две разные категории:

• Внутренняя сортировка : если входные данные таковы, что их можно сразу откорректировать в основной памяти, это называется внутренней сортировкой.
• Внешняя сортировка : если входные данные таковы, что их нельзя сразу полностью отрегулировать в памяти, их необходимо сохранить на жестком диске, гибком диске или любом другом устройстве хранения. Это называется внешней сортировкой.

Читайте: Интересные идеи и темы проекта структуры данных

Типы сортировки в структуре данных

Вот несколько наиболее распространенных типов алгоритмов сортировки.

1. Сортировка слиянием

Этот алгоритм работает над разбиением массива на две половины сопоставимых размеров. Затем каждая половина сортируется и снова объединяется вместе с помощью функции merge().

Вот как работает алгоритм:

Сортировка слиянием (обр[], л, г)

Если г > л

1. Разделите массив на две равные половины, найдя среднюю точку:

средний m = (l+r)/2

2. Используйте функцию mergeSort для вызова первой половины:

Вызов mergeSort(arr, l, m)

3. Вызовите mergeSort для второй половины:

Вызов mergeSort(arr, m+1, r)

4. Используйте функцию merge(), чтобы объединить две половины, отсортированные на шаге 2 и 3:

Вызов слияния (arr, l, m, r)

Посмотрите на изображение ниже, чтобы получить четкое представление о том, как это работает.

Источник

Программа Python для реализации сортировки слиянием

деф сортировка слиянием (а):

если len(a) >1:

середина = длина(а)//2

А = а[:середина]

В = а [середина:]

сортировка слиянием (A)

сортировка слиянием (B)

я = j = к = 0

в то время как я < len (A) и j < len (B):

если А[i] < B[j]:

а[к] = А[я]

я+=1

еще:

а[к] = В[j]

j+=1

к+=1

пока я < len(A):

а[к] = А[я]

я+=1

к+=1

в то время как j < len (R):

а[к] = В[j]

j+=1

к+=1

определить список печати (а):

для i в диапазоне (len (a)):

печать (а [я], конец = " ")

Распечатать()

если __name__ == '__main__':

а = [12, 11, 13, 5, 6, 7]

сортировка слиянием (а)

print("Отсортированный массив: ", end="\n")

список печати (а)

Узнайте больше: Рекурсия в структуре данных: как это работает, типы и когда используется

2. Сортировка выбором

При этом сначала самый маленький элемент отправляется на первую позицию.

Затем в оставшемся массиве ищется следующий наименьший элемент, который помещается на вторую позицию. Это продолжается до тех пор, пока алгоритм не достигнет последнего элемента и не поместит его в правильное положение.

Посмотрите на картинку ниже, чтобы понять это лучше.

Источник

Программа Python для реализации сортировки выбором

импорт системы

Х = [6, 25, 10, 28, 11]

для i в диапазоне (len (X)):

min_idx = я

для j в диапазоне (i+1, len(X)):

если X[min_idx] > X[j]:

мин_idx = j

X[i], X[min_idx] = X[min_idx], X[i]

print («Отсортированный массив»)

для i в диапазоне (len (X)):

печать("%d" %X[i]),

Расширенная сертификация Data Science, более 250 партнеров по найму, более 300 часов обучения, 0% EMI

3. Пузырьковая сортировка

Это самый легкий и простой из всех алгоритмов сортировки. Он работает по принципу многократной замены соседних элементов, если они расположены не в правильном порядке.

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

Пример :

Ввод : 637124

Первый проход

63 7124 -> 36 7124 : Пузырьковая сортировка сравнивает 6 и 3 и меняет их местами, потому что 3<6.

3 67 124 -> 3 67 124 : Так как 6<7, без замены

36 71 24 -> 36 17 24 : 7 и 1 поменяны местами, так как 7>1

361 72 4 -> 361 27 4 : 2 и 7 поменяны местами, так как 2<7

3612 74 -> 3612 47 : 4 и 7 поменяны местами, так как 4<7

Второй проход

36 1247 -> 36 1247

3 61 274 -> 3 16 274

31 62 74 -> 31 26 74

312 67 4 -> 312 67 4

3126 74 -> 3126 47

Третий проход

31 2647 -> 13 2647

1 32 647 -> 1 23 647

12 36 47 -> 12 36 47

123 64 7 -> 123 46 7

1234 67 -> 1234 67

Как видите, мы получаем результат в порядке возрастания после трех проходов.

Программа Python для реализации пузырьковой сортировки

def пузырьковая сортировка (а):

п = лен(а)

для я в диапазоне (n):

для j в диапазоне (0, ni-1):

если а[j] > а[j+1] :

а[j], а[j+1] = а[j+1], а[j]

а = [64, 34, 25, 12, 22, 11, 90]

пузырьковая сортировка (а)

print («Отсортированный массив:»)

для i в диапазоне (len (a)):

печать («%d» %a[i]),

Читайте также: Фреймы данных в Python: подробное руководство по Python

Заключение

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

Чтобы получить больше информации о том, как работает сортировка, свяжитесь с нами, и мы поможем вам начать работу с курсом, который наилучшим образом соответствует вашим потребностям!

Если вам интересно узнать о науке о данных, ознакомьтесь с программой IIIT-B & upGrad Executive PG по науке о данных, которая создана для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1 -на-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.

Получайте удовольствие от кодирования!