Сортиране на вектор в C++

Сортиране на вектори в C++

Въведение

Векторите са един от основните типове контейнери в C++, които съхраняват динамичен масив от елементи. Понякога може да се наложи да сортираме елементите във вектора, за да ги подредим по някакъв специфичен ред. C++ предоставя различни вградени функции и алгоритми за сортиране на вектори. В тази статия ще разгледаме различните техники за сортиране и тяхното прилагане към вектори в C++.

Алгоритми за сортиране

Алгоритъм за сортиране по балончета

Този алгоритъм повтаряно сравнява съседни елементи и разменя тези, които не са в ред, докато не бъдат сортирани всички елементи. Той е прост за разбиране и имплементиране, но неговата ефективност е O(n\2)*, където *n е броят на елементите във вектора.

Алгоритъм за сортиране по поставяне

Този алгоритъм създава сортирана част във вектора и последователно поставя всеки несортиран елемент в правилната му позиция в сортираната част. Той е ефективен за малки вектори и вече почти сортирани вектори. Неговата ефективност е O(n\2)* в най-лошия случай и *O(n) в най-добрия случай.

Алгоритъм за сортиране по избор

Този алгоритъм намира минималния несортиран елемент от вектора и го разменя с първия несортиран елемент. Този процес се повтаря, докато не бъдат сортирани всички елементи. Неговата ефективност е O(n\2).

Алгоритъм за сортиране по бързо поставяне

  Търсите безплатна пробна версия на Netflix? Вместо това опитайте тези услуги

Този алгоритъм комбинира сортирането по поставяне и бързото сортиране. Той използва бързото сортиране за сортиране на по-големи сегменти от вектора, а след това сортира всяка от тези части с поставяне. Той е по-ефективен от горните алгоритми и неговата ефективност е O(n log n).

Алгоритъм за сортиране по бързина

Това е един от най-ефективните алгоритми за сортиране с ефективност O(n log n). Той разделя вектора на две части: сортирана и несортирана част. След това избира опорна точка от несортираната част и пренарежда елементите така, че всички елементи, по-малки от опорната точка, да са от лявата страна, а всички елементи, по-големи от опорната точка, да са от дясната страна. Този процес се повтаря рекурсивно за лявата и дясната части, докато не бъдат сортирани всички елементи.

Имплементация във C++

Следните примери в C++ демонстрират различните алгоритми за сортиране, приложени към вектори:

Сортиране по балончета
cpp
void bubbleSort(vector<int>& vec) {
for (int i = 0; i < vec.size() - 1; i++) {
for (int j = 0; j < vec.size() - i - 1; j++) {
if (vec[j] > vec[j + 1]) {
swap(vec[j], vec[j + 1]);
}
}
}
}

Сортиране по поставяне
cpp
void insertionSort(vector<int>& vec) {
for (int i = 1; i < vec.size(); i++) {
int key = vec[i];
int j = i - 1;
while (j >= 0 && vec[j] > key) {
vec[j + 1] = vec[j];
j--;
}
vec[j + 1] = key;
}
}

Сортиране по избор
cpp
void selectionSort(vector<int>& vec) {
for (int i = 0; i < vec.size() - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < vec.size(); j++) {
if (vec[j] < vec[minIdx]) {
minIdx = j;
}
}
swap(vec[minIdx], vec[i]);
}
}

Сортиране по бързо поставяне
cpp
void quickInsertionSort(vector<int>& vec) {
if (vec.size() <= 10) {
insertionSort(vec);
} else {
quickSort(vec, 0, vec.size() - 1);
}
}

void quickSort(vector<int>& vec, int low, int high) {
if (low < high) {
int pivot = partition(vec, low, high);
quickSort(vec, low, pivot - 1);
quickSort(vec, pivot + 1, high);
}
}

int partition(vector<int>& vec, int low, int high) {
int pivot = vec[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (vec[j] <= pivot) {
i++;
swap(vec[i], vec[j]);
}
}
swap(vec[i + 1], vec[high]);
return i + 1;
}

Сортиране по бързина
cpp
void quickSort(vector<int>& vec) {
quickSortHelper(vec, 0, vec.size() - 1);
}

void quickSortHelper(vector<int>& vec, int low, int high) {
if (low < high) {
int pivot = partition(vec, low, high);
quickSortHelper(vec, low, pivot - 1);
quickSortHelper(vec, pivot + 1, high);
}
}

int partition(vector<int>& vec, int low, int high) {
int pivot = vec[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (vec[j] <= pivot) {
i++;
swap(vec[i], vec[j]);
}
}
swap(vec[i + 1], vec[high]);
return i + 1;
}

Заключение

Сортирането на вектори в C++ е важна операция за организиране и управление на данни. C++ предоставя различни вградени алгоритми за сортиране, всеки със своите предимства и недостатъци. Изборът на най-подходящия алгоритъм зависи от размера на вектора, вида на данните и изискваната ефективност. Чрез разбирането на различните алгоритми за сортиране, разработчиците могат да изберат най-подходящата техника за своите конкретни приложения.

Често задавани въпроси

1. Кой е най-добрият алгоритъм за сортиране за големи вектори?
– Бързото сортиране е най-добрият алгоритъм за сортиране за големи вектори, като неговата ефективност е O(n log n).

2. Кой е най-ефективният алгоритъм за сортиране за малки вектори?
– Сортирането по поставяне е най-ефективният алгоритъм за сортиране за малки вектори, като неговата ефективност е O(n\2).

3. Какво е сортиране in-place?
– Сортирането in-place е тип сортиране, което сортира данните в същия вектор, без да създава нови копия.

4. Кой сортиращ алгоритъм е стабилен?
– Сортирането по поставяне е стабилен сортиращ алгоритъм, което означава, че запазва реда на равни елементи.

5. Кое сортиране е подходящо за сортиране на целочислени данни?
– Всички горепосочени алгоритми са подходящи за сортиране на целочислени данни.

6. **Кое сортиране е най-подходящо за сортиране на