Алгоритм быстрой сортировки чисел в массиве элементов, указатели места

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

Среднее время алгоритма быстрой сортировки NlogN, худший случай O(N^2), где N – длина массива. Чтобы избежать худшего случая нужно: перед использованием быстрой сортировки массива перемешать его.

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

Давайте рассмотрим работу алгоритма на примере. Пусть у нас есть массив с элементами: 4,9,7,6,2,3,8

результат работы программы быстрая сортировка

Выберем число относительно которого мы будем сравнивать – 6. Обычно выбирается число стоящее в середине. И определим два указателя b (begin) и e (end). Теперь мы двигаем наши указатели до тех пор пока не встретим число большее(если указатель b) или меньшее(указатель e) 6.

Так как числа на нужных местах, то мы продвигаем наши указатели вперед. Теперь мы наткнулись на числа 9 и 3. Мы должны поменять их местами так как 9>6, а 3<6.

Снова сдвигаем указатели на одну итерацию. Видим числа стоящие не на своем месте 7>6 и 2<6. Меняем их местами.

Вновь передвигаем указатели, они оказываются на 6.

Теперь делим массив на две части и в каждой части производим такую же сортировку.

результат работы программы быстрая сортировка

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

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

Все первая часть отсортирована, займемся второй частью массива.

Выберем элемент со значением, как элемент относительно которого будем сравнивать.

6 и 8 оставляем на своих местах, сдвигаем указатели. 7 и 9 тоже не трогаем. Теперь давайте поделим эту половинку еще на две. И отдельно сравним элементы в каждой из половинок: 9 и 8 меняем местами, 6 и 7 не изменяем.

Ну вот и все мы отсортировали массив методом быстрой сортировки.

На этом видео вы можете увидеть как происходит метод быстрой сортировки ( в качестве массива — танцоры)

Результат быстрой сортировки

результат работы программы быстрая сортировка

Быстрая сортировка на си++

//Быстрая сортировка
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <clocale>

using namespace std;

//функция быстрой сортировки
void quick_sort(vector <int> &v,int begin0, int end0)
{
	auto d=end0;//число относительно 
	//которого будем сравнивать
	auto begin=begin0;//указатель на начало
	auto end=end0;//указатель на конец

	do
	{
		while(v[begin]<d)
			begin++;
		while(v[end]>d)
			end--;
		if(begin<=end)
		{
			swap(v[begin],v[end]);// меняем местами
			begin++;
			end--;
		}
	}while(begin<=end);
	if(begin0<end)
		quick_sort(v,begin0,end);
		if(begin<end0)
			quick_sort(v,begin,end0);
}
int main()
{ 
	setlocale(LC_CTYPE,"rus");
	vector <int> arr; //заводим массив
	//заполняем его цифрами от 0 до 19
	for(auto i=0;i<20;i++)
		arr.push_back(i);
	// перемешываем наш массив
	for(size_t i=0;i<arr.size();i++)
		swap(arr[i],arr[rand()%(arr.size()-i)+i]);
	cout<<"Массив: ";
	for(auto i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	//функция быстрой сортировки
	quick_sort(arr,0,arr.size()-1);
	cout<<"Быстрая сортировка:";
	for(auto i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	return 0;
}
Результат быстрой сортировки
результат работы программы cmd быстрая сортировка

Помогая проекту BEST-EXAM, вы делаете образование более доступным для каждого человека, внесите и вы свой вклад -
поделитесь этой статьей в социальных сетях!