Какие знаешь алгоритмы сортировки

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

1. Пузырьковая сортировка (Bubble Sort)

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

   void bubbleSort(int arr[], int n) {
       for (int i = 0; i < n - 1; i++) {
           for (int j = 0; j < n - i - 1; j++) {
               if (arr[j] > arr[j + 1]) {
                   // Меняем местами arr[j] и arr[j+1]
                   int temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
               }
           }
       }
   }
   

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

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

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

   void insertionSort(int arr[], int n) {
       for (int i = 1; i < n; i++) {
           int key = arr[i];
           int j = i - 1;
           // Перемещаем элементы arr[0..i-1], которые больше ключа, на одну позицию вперед
           while (j >= 0 && arr[j] > key) {
               arr[j + 1] = arr[j];
               j = j - 1;
           }
           arr[j + 1] = key;
       }
   }
   

   • Внешний цикл for проходит по всем элементам массива, начиная со второго.
   • Внутренний цикл while перемещает элементы, которые больше текущего ключа, вправо.
   • Ключ вставляется в правильное место.

3. Сортировка выбором (Selection Sort)

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

   void selectionSort(int arr[], int n) {
       for (int i = 0; i < n - 1; i++) {
           int min_idx = i;
           for (int j = i + 1; j < n; j++) {
               if (arr[j] < arr[min_idx]) {
                   min_idx = j;
               }
           }
           // Меняем местами минимальный элемент с первым элементом
           int temp = arr[min_idx];
           arr[min_idx] = arr[i];
           arr[i] = temp;
       }
   }
   

   • Внешний цикл for проходит по всем элементам массива.
   • Внутренний цикл for находит минимальный элемент в неотсортированной части.
   • Минимальный элемент меняется местами с первым элементом неотсортированной части.

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

   Быстрая сортировка — это эффективный алгоритм, который использует метод "разделяй и властвуй". Он выбирает опорный элемент и разделяет массив на две части: элементы меньше опорного и элементы больше опорного.

   int partition(int arr[], int low, int high) {
       int pivot = arr[high];
       int i = (low - 1);
       for (int j = low; j <= high - 1; j++) {
           if (arr[j] < pivot) {
               i++;
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }
       int temp = arr[i + 1];
       arr[i + 1] = arr[high];
       arr[high] = temp;
       return (i + 1);
   }
   ​
   void quickSort(int arr[], int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);
           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }
   

   • Функция partition выбирает последний элемент как опорный и размещает его в правильной позиции.
   • Все элементы меньше опорного перемещаются влево, а больше — вправо.
   • Рекурсивно применяется quickSort к подмассивам слева и справа от опорного элемента.

5. Сортировка слиянием (Merge Sort)

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

   void merge(int arr[], int l, int m, int r) {
       int n1 = m - l + 1;
       int n2 = r - m;
       int L[n1], R[n2];
       for (int i = 0; i < n1; i++)
           L[i] = arr[l + i];
       for (int j = 0; j < n2; j++)
           R[j] = arr[m + 1 + j];
       int i = 0, j = 0, k = l;
       while (i < n1 && j < n2) {
           if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
           } else {
               arr[k] = R[j];
               j++;
           }
           k++;
       }
       while (i < n1) {
           arr[k] = L[i];
           i++;
           k++;
       }
       while (j < n2) {
           arr[k] = R[j];
           j++;
           k++;
       }
   }
   ​
   void mergeSort(int arr[], int l, int r) {
       if (l < r) {
           int m = l + (r - l) / 2;
           mergeSort(arr, l, m);
           mergeSort(arr, m + 1, r);
           merge(arr, l, m, r);
       }
   }
   

   • Функция merge объединяет два подмассива в один отсортированный.
   • mergeSort рекурсивно делит массив на две половины и сортирует их.
   • После сортировки половины объединяются с помощью merge.

6. Пирамидальная сортировка (Heap Sort)

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

   void heapify(int arr[], int n, int i) {
       int largest = i;
       int l = 2 * i + 1;
       int r = 2 * i + 2;
       if (l < n && arr[l] > arr[largest])
           largest = l;
       if (r < n && arr[r] > arr[largest])
           largest = r;
       if (largest != i) {
           int swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;
           heapify(arr, n, largest);
       }
   }
   ​
   void heapSort(int arr[], int n) {
       for (int i = n / 2 - 1; i >= 0; i--)
           heapify(arr, n, i);
       for (int i = n - 1; i > 0; i--) {
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;
           heapify(arr, i, 0);
       }
   }
   

   • heapify перестраивает поддерево с корнем в заданном индексе.
   • heapSort сначала строит максимальную кучу, затем извлекает элементы из кучи, перестраивая её.

7. Сортировка подсчетом (Counting Sort)

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

   void countingSort(int arr[], int n) {
       int max = *max_element(arr, arr + n);
       int count[max + 1] = {0};
       for (int i = 0; i < n; i++)
           count[arr[i]]++;
       for (int i = 1; i <= max; i++)
           count[i] += count[i - 1];
       int output[n];
       for (int i = n - 1; i >= 0; i--) {
           output[count[arr[i]] - 1] = arr[i];
           count[arr[i]]--;
       }
       for (int i = 0; i < n; i++)
           arr[i] = output[i];
   }
   

   • count хранит количество вхождений каждого элемента.
   • output используется для построения отсортированного массива.
   • Элементы размещаются в output на основе накопленных значений в count.

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