Существует множество алгоритмов сортировки. Поиск подходящего варианта для вашего приложения - это задача, требующая краткого понимания таких факторов, как производительность, временная сложность, длина кода и т. Д. Конкретного алгоритма. В этом посте мы рассмотрим все основные концепции, необходимые для реализации быстрой сортировки на C ++, в следующем порядке:
- Понимание алгоритма быстрой сортировки
- Псевдокод для быстрой сортировки
- Программа Quicksort на C ++
- Быстрая сортировка сложности времени
Понимание алгоритма быстрой сортировки
Как Сортировка слиянием , Quicksort следует стратегии «разделяй и властвуй». Используя стратегию разделяй и властвуй, мы разделяем проблему на множество подзадач и решаем их рекурсивно. Сначала мы разберемся со всем процессом шаг за шагом, а затем с помощью примера мы разовьем глубокое понимание всего процесса.
Сначала мы запросим у пользователя несортированный массив.
Как только у нас есть несортированный массив, нам нужно выбрать значение поворота из массива. Мы можем выбрать любое значение.
После того, как мы выберем точку поворота, после этого нам нужно расположить другие элементы массива таким образом, чтобы все элементы, меньшие, чем значение поворота, были размещены справа от значения поворота, а все элементы больше, чем значение поворота. значение должно быть помещено справа от значения поворота.
Выполняем шаг 3, пока не получим отсортированный массив.
уроки студии Android для начинающих
Теперь давайте рассмотрим пример, реализуем алгоритм и посмотрим, как он работает.
Здравствуйте [5, 4, 1, 11, 9, 6, 2, 3] в этом примере мы всегда будем рассматривать опорный элемент как крайний правый элемент списка.
Давайте пройдемся по каждому шагу и поймем логику, которую мы использовали для решения проблемы.
Сначала мы выбрали «3» в качестве точки поворота и расположили все элементы меньше «3» справа и все элементы больше «3» справа.
На данный момент у нас есть 2 подзадачи. Давайте сначала решим подзадачу справа. Мы выбрали одну точку опоры и поместили «2» вправо.
Чтобы решить вторую подзадачу, мы выбираем «6» в качестве нашей оси и размещаем элементы, как мы обсуждали ранее.
У нас есть еще 2 подзадачи. Первый решается путем выбора 4 в качестве точки поворота, а второй решается путем выбора 9 в качестве точки поворота. Наконец, у нас есть отсортированный массив с элементами, помещенными в индекс подчеркивания.
Заметка- Здесь важно понимать, что все операции выполняются в одном массиве. Новые массивы не создаются.
Псевдокод для быстрой сортировки в C ++
QuickSort (массив [], начальный_индекс, конечный_индекс) {если (начальный_индекс Программа быстрой сортировки на C ++
Мы поняли алгоритм и развили глубокое понимание работы алгоритма. Давайте реализуем Quicksort на C ++ и напишем программу для сортировки массива.
#include с использованием пространства имен std void swap_elements (int * a, int * b) {int temp = * a * a = * b * b = temp} int partition (int array [], int start_index, int end_index) {int pivot = массив [end_index] int i = (start_index - 1) for (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>Стоимость NumberofElements<<'Enter the elements one by one: ' for(i=0i>Hello [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) return 0} Вывод:
что такое токен Java
Сложность времени
Давайте поговорим о самом важном аспекте любого алгоритма сортировки, а именно о временной сложности. Это говорит нам о производительности алгоритма в различных сценариях. Эти значения могут помочь нам решить, можем ли мы использовать этот алгоритм для нашего приложения.
- Лучший случай- На)
- Средний случай- (нлогн)
- Худший случай- На2)
На этом мы подошли к концу статьи о быстрой сортировке в C ++. Если вы хотите узнать больше, ознакомьтесь с от Edureka, надежной компании онлайн-обучения. Курс обучения и сертификации по Java J2EE и SOA от Edureka разработан, чтобы обучить вас базовым и продвинутым концепциям Java, а также различным средам Java, таким как Hibernate и Spring.
Есть вопрос к нам? Пожалуйста, укажите это в разделе комментариев в этом блоге, и мы свяжемся с вами как можно скорее.