Быстрая сортировка хоара: принцип работы и алгоритм

Быстрая сортировка Хоара – один из самых известных и эффективных алгоритмов сортировки. Он был разработан британским информатиком Чарльзом Хоаром в 1960-х годах. Принцип работы алгоритма основан на разделении массива на две части, с последующей сортировкой каждой из них.

Преимущество быстрой сортировки Хоара заключается в ее высокой производительности и эффективности на практике. Алгоритм работает по принципу «разделяй и властвуй», что позволяет сортировать массивы большого размера за короткое время.

Пример работы алгоритма можно проиллюстрировать следующим образом: предположим, что у нас есть массив из 10 чисел, которые нужно отсортировать по возрастанию. Алгоритм выбирает опорный элемент, например, первый элемент массива, и проходит по всем элементам, разделяя их на две группы – меньше опорного и больше опорного. Затем процесс разделения повторяется для каждой из двух полученных групп до тех пор, пока в каждой из них не останется по одному элементу. Затем элементы объединяются в отсортированный массив.

Быстрая сортировка Хоара – один из самых популярных алгоритмов сортировки. Его применение позволяет сортировать массивы большого размера за короткое время. Основанный на принципе «разделяй и властвуй», алгоритм разбивает массив на две части, сортирует их по отдельности, а затем объединяет в отсортированный массив. Преимущества быстрой сортировки Хоара делают ее незаменимой при работе с большими объемами данных и в различных областях программирования.

Алгоритм быстрой сортировки Хоара

Принцип работы алгоритма быстрой сортировки состоит в следующем:

  • Выбирается опорный элемент из массива, как правило, случайным образом. Опорный элемент позволяет разделить массив на две части.
  • Весь массив переписывается таким образом, чтобы элементы меньше опорного оказались в левой части массива, а элементы больше опорного – в правой.
  • Для каждой из двух получившихся частей рекурсивно вызывается алгоритм быстрой сортировки.
  • Рекурсия продолжается до тех пор, пока не останется массивов из одного элемента. (Массивы из одного элемента считаются отсортированными.)

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

Ниже приведен пример реализации алгоритма быстрой сортировки Хоара на языке Python:


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

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

Принцип работы алгоритма

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

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

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

Лучший случайСредний случайХудший случай
\(O(n \log n)\)\(O(n \log n)\)\(O(n^2)\)

Особенности быстрой сортировки Хоара

Основные особенности быстрой сортировки Хоара включают:

  • Деление массива на подмассивы. Алгоритм разбивает исходный массив на подмассивы, которые затем сортируются отдельно.
  • Выбор опорного элемента. Для каждого подмассива нужно выбрать опорный элемент, который используется для сравнения и перемещения других элементов.
  • Рекурсивность. Быстрая сортировка Хоара использует рекурсивный подход, который позволяет сортировать подмассивы до тех пор, пока в них не останется один элемент.

Благодаря своим особенностям, быстрая сортировка Хоара обеспечивает высокую скорость работы на больших массивах данных. Однако, в худшем случае, когда опорным элементом выбирается наименьший или наибольший элемент массива, время работы алгоритма может увеличиться до квадратичного.

Пример 1: Сортировка чисел

Давайте рассмотрим пример применения быстрой сортировки Хоара для сортировки массива чисел.


function quickSort(arr, left = 0, right = arr.length - 1) {
if (arr.length > 1) {
const index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
}
if (index < right) {
quickSort(arr, index, right);
}
}
return arr;
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
return i;
}
const array = [5, 2, 1, 8, 4];
console.log(quickSort(array)); // [1, 2, 4, 5, 8]

В данном примере мы определяем функцию quickSort, которая принимает массив чисел и вызывает функцию partition для разделения массива на две части. Затем функция quickSort рекурсивно вызывается для каждой из этих частей до тех пор, пока размер массива не станет меньше или равным 1.

Функция partition выбирает опорный элемент из массива и перемещает все элементы, меньшие его, влево, а все элементы, большие его, вправо. После этого функция возвращает индекс опорного элемента.

В конце примера мы создаем массив чисел [5, 2, 1, 8, 4], применяем к нему быструю сортировку и выводим результат в консоль. В результате получается отсортированный по возрастанию массив [1, 2, 4, 5, 8].

Пример 2: Сортировка строк

Быстрая сортировка Хоара также может быть использована для сортировки строк. Рассмотрим пример, в котором необходимо отсортировать массив строк по алфавиту.

Для этого нам понадобится изменить условие сравнения элементов массива. Вместо операции "меньше" или "больше" будем использовать функцию сравнения строк.

Например, предположим, что у нас есть массив строк:

['apple', 'banana', 'cherry', 'date']

Применим быструю сортировку Хоара к этому массиву. На первом шаге выберем опорный элемент. В качестве опорного элемента выберем строку 'cherry'. Затем разделим массив на две части, переместив все строки, которые меньше или равны 'cherry', влево, а все строки, которые больше 'cherry', вправо. Получим следующий массив:

['apple', 'banana', 'cherry', 'date']

Затем рекурсивно применим быструю сортировку к левой и правой частям массива. На каждом шаге выбираем опорный элемент и разделяем массив на две части.

После нескольких итераций получим отсортированный массив:

['apple', 'banana', 'cherry', 'date']

Таким образом, быстрая сортировка Хоара может успешно применяться для сортировки строк по алфавиту. Она остается эффективным алгоритмом даже при работе с большими массивами строк.

Пример 3: Сортировка объектов

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

Представим, что у нас есть массив с объектами типа "Студент", у каждого объекта есть два свойства: "имя" и "возраст". Наша задача - отсортировать студентов по возрасту в порядке возрастания. Для этого определим функцию сравнения:


function compareAge(a, b) {
if (a.age < b.age) {
return -1;
}
if (a.age > b.age) {
return 1;
}
return 0;
}

Теперь мы можем передать эту функцию в качестве аргумента в быструю сортировку Хоара:


let students = [
{ name: "Алексей", age: 20 },
{ name: "Елена", age: 22 },
{ name: "Иван", age: 19 },
{ name: "Мария", age: 21 }
];
quickSort(students, compareAge);
console.log(students);

После выполнения данного кода в консоли мы получим отсортированный по возрасту массив студентов:


[
{ name: "Иван", age: 19 },
{ name: "Алексей", age: 20 },
{ name: "Мария", age: 21 },
{ name: "Елена", age: 22 }
]

Таким образом, быстрая сортировка Хоара может быть эффективно использована для сортировки массивов объектов, позволяя указать функцию сравнения, которая учитывает не только одно свойство объектов, но и их отношение в целом.

Оцените статью