Advertisement
C3EQUALZ

Все виды сортировок.

Nov 24th, 2022 (edited)
585
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.64 KB | None | 0 0
  1. ###Сортировка пузырьком. Идем последовательно, сравнивая каждый элемент с соседом. Кол-во итераций здесь n - 1 (просто запомнить этот факт). Делаю n - i - 1, так как на 1 число каждый раз меньше рассматривать, после 1 итерации выйдет max в конец. flag сделал для более высокой скорости кода, если будет уже все отсортировано меньше, чем за n-1.  
  2. def bubble_sort(lst):
  3.     n = len(lst)
  4.     for i in range(n - 1):
  5.         flag = True
  6.         for j in range(n - i - 1):
  7.             if lst[j] > lst[j + 1]:
  8.                 lst[j], lst[j + 1] = lst[j + 1], lst[j]
  9.                 flag = False
  10.         if flag == True:
  11.             break
  12.     return lst
  13.  
  14. ###Сортировка выбором. Находим минимальное значение в списке, достаем индекс, удаляем его (pop() возвращает значение), а потом добавляем в конец списка. С помощью среза перестаю рассматривать последний элемент и т.д.
  15. def choice_sort(lst):
  16.     for k in range(len(lst), 0, -1):
  17.         lst.append(lst.pop(lst.index(min(lst[:k]))))
  18.     return lst
  19.  
  20. ###Сортировка вставкой. Здесь мы берем элемент и сравниваем с прошлыми до самого начала. Самый минимальный сразу станет в начало. Идем последовательно слева-направо.
  21. def s_insert(lst):
  22.     for i in range(1, len(lst)):
  23.         for j in range(i,0,-1):
  24.             if lst[j] < lst[j-1]:
  25.                 lst[j], lst[j-1] = lst[j-1], lst[j]
  26.             else:
  27.                 break
  28.     return lst
  29.  
  30. ### Сортировка Шелла. Здесь мы берем и сравниваем элементы на расстоянии, начиная с n//2 и уменьшая данное расстояние в два раза.
  31. def shell_sort(lst):
  32.     move = len(lst) // 2
  33.     while move > 0:
  34.         for i in range(len(lst) - move):
  35.             if lst[i] > lst[i+move]:
  36.                 lst[i], lst[i+move] = lst[i+move], lst[i]
  37.         move //= 2
  38.     return lst
  39.  
  40. ### Сортировка Хоара. Здесь мы берем случайный элемент из списка и формируем два списка, ставя вокруг данного элемента. Способ рекурсивный.
  41. def quick_sort(lst):
  42.     if len(lst) > 1:
  43.         x = matrix[random.randint(0, len(lst)-1)]
  44.         low = [l for l in matrix if l < x]
  45.         eq = [l for l in matrix if l == x]
  46.         high = [l for l in matrix if l > x]
  47.         lst = quick_sort(low) + eq + quick_sort(high)
  48.     return lst
  49.  
  50. ### Сортировка слиянием. Делим исходный наш лист постоянно на две части, пока каждый элемент не будет по отдельности. Объединяем листы, а потом сортируем с помощью сортировки выбора (def merge_list).
  51. def merge_list(a, b):
  52.     sum_list, c = a + b, []
  53.     while sum_list:
  54.         c.append(sum_list.pop(sum_list.index(min(sum_list))))
  55.     return c
  56.  
  57. def split_and_merge_list(lst):
  58.     a, b = lst[len(lst)//2:], lst[:len(lst)//2]
  59.     if len(a) > 1:
  60.         a = split_and_merge_list(a)
  61.     if len(b) > 1:
  62.         b = split_and_merge_list(b)
  63.  
  64.     return merge_list(a, b)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement