Вот несколько алгоритмов сортировки, реализованных в Python:

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

   • Описание. Пузырьковая сортировка неоднократно меняет местами соседние элементы, если они расположены в неправильном порядке, пока не будет отсортирован весь список.
   • Реализация Python:

     def bubble_sort(arr):
      n = len(arr)
      for i in range(n):
          for j in range(0, n-i-1):
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]

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

   • Описание: Сортировка выбором находит минимальный элемент в неотсортированной части списка и заменяет его первым неотсортированным элементом.
   • Реализация Python:

     def selection_sort(arr):
      n = len(arr)
      for i in range(n):
          min_idx = i
          for j in range(i+1, n):
              if arr[j] < arr[min_idx]:
                  min_idx = j
          arr[i], arr[min_idx] = arr[min_idx], arr[i]

3. Сортировка вставками:

   • Описание. Сортировка вставкой создает окончательный отсортированный список по одному элементу, вставляя каждый элемент в правильное положение.
   • Реализация Python:

     def insertion_sort(arr):
      n = len(arr)
      for i in range(1, n):
          key = arr[i]
          j = i - 1
          while j >= 0 and arr[j] > key:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key

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

   • Описание. Сортировка слиянием делит список на две половины, рекурсивно сортирует их, а затем объединяет отсортированные половины для получения окончательного отсортированного списка.
   • Реализация Python:

     def merge_sort(arr):
      if len(arr) > 1:
          mid = len(arr) // 2
          left_half = arr[:mid]
          right_half = arr[mid:]
          merge_sort(left_half)
          merge_sort(right_half)
          i = j = k = 0
          while i < len(left_half) and j < len(right_half):
              if left_half[i] < right_half[j]:
                  arr[k] = left_half[i]
                  i += 1
              else:
                  arr[k] = right_half[j]
                  j += 1
              k += 1
          while i < len(left_half):
              arr[k] = left_half[i]
              i += 1
              k += 1
          while j < len(right_half):
              arr[k] = right_half[j]
              j += 1
              k += 1

5. Быстрая сортировка:

   • Описание. Быстрая сортировка выбирает опорный элемент, разделяет список на два подмассива и рекурсивно сортирует подмассивы.
   • Реализация Python:

     def quick_sort(arr):
      if len(arr) <= 1:
          return arr
      else:
          pivot = arr[0]
          lesser = [x for x in arr[1:] if x <= pivot]
          greater = [x for x in arr[1:] if x > pivot]
          return quick_sort(lesser) + [pivot] + quick_sort(greater)