Сортировка массива: методы, примеры, алгоритмы

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

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

1. Сортировка пузырьком (Bubble Sort)

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

   def пузырьковая_сортировка(массив):
       n = len(массив)
       
       for i in range(n - 1):
           for j in range(n - i - 1):
               if массив[j] > массив[j + 1]:
                   массив[j], массив[j + 1] = массив[j + 1], массив[j]
                   
       return массив
   

2. Сортировка вставками (Insertion Sort)

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

   def сортировка_вставками(массив):
       n = len(массив)
       
       for i in range(1, n):
           текущий_элемент = массив[i]
           позиция = i - 1
           
           while позиция >= 0 and текущий_элемент < массив[позиция]:
               массив[позиция + 1] = массив[позиция]
               позиция -= 1
           
           массив[позиция + 1] = текущий_элемент
           
       return массив
   

3. Быстрая сортировка (Quick Sort)

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

   def быстрая_сортировка(массив):
       if len(массив) <= 1:
           return массив
       
       опорный = массив[0]
       меньшие = [элемент for элемент in массив[1:] if элемент <= опорный]
       большие = [элемент for элемент in массив[1:] if элемент > опорный]
       
       return быстрая_сортировка(меньшие) + [опорный] + быстрая_сортировка(большие)
   

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