Алгоритмы

Сортировка вставкой/Insertion sort

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

Сортировка выбором/Selection sort

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

Преимущества:

  1. Простой в применении
  2. Сортировка на месте(не использует дополнительного места)

Пузырьковая сортировка/Bubble sort

Пузырьковая сортировка является одним из самых простых алгоритмов сортирования. Хотя многие говорят, что этот алгоритм не стоит даже рассматривать, я бы все равно предпочел написать о нем в паре строк. Алгоритм действительно является плохим в плане производительности и его не стоит использовать в приложениях так, как его сложность в хутшем, да и в лучшем случае, будет О(n^2). Пузырьковая сортировка называется так лиш потому, что больший елемент перемещается в конец массива как пузырек)).

Алгоритм быстрой сортировки (Quick sort algorithm)

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

Для наглядности позначим сортируемый массив  А[p...r].

Разделение.

В этой части массив А[p...r] разбивается на две части, а именно на А[p...q-1] и А[q+1...r], где элементы А[p...q-1]  меньше или равно значению A[q], а элементы подмассива А[q+1...r] больше или равны значению A[q]. Где элемент q - вычисляется при исполнении процедуры разбиения.

Поис максимального подмассива

Задача: Поиск максимального подмассива

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

К примеру, дан массив [−2,1,−3,4,−1,2,1,−5,4], смежный подмасив [4,−1,2,1] имеет наибольшую суму равную 6.