Quick sort using vectors

@dinbo · Регистрация: 03.11.2016

Студворк — интернет-сервис помощи студентам

Now that you have learned about three sorting algorithms with quadratic time complexity (Bubble, (./selection) and Insertion sorts) you should be curious, whether it is possible to perform the task significantly faster.

The problem is that if these algorithms solrt 10000 elements in a second, then they will sort 100 times more elements (one million) in about 100*100 longer time, i.e. several hours!

Luckily there really are other approaches. One of them is a Quick-sort. It uses quite simple idea and allows to sort with time complexity of O(N*log(N)) which increases almost proportional to simple N rather than N*N as with simpler methods!

Algorithm
Suggest we have an array of numbers:

5 3 8 1 4 7 2 9 6
Let us choose some element - call it pivot and try to reorder others in such a way that ones which are lesser than pivot will be put before it while others, which are greater, will take place behind it. For example if pivot is 5 then we want something like this:

2 3 4 1 5 7 8 9 6
Now we can say that array is partially sorting - it have two unordered parts, but these parts are ordered in relation to each other. We need not move elements between them any more - only inside them.

Now let us regard this array like composition of pivot and two subarrays:

[2 3 4 1] 5 [7 8 9 6]
Obviously we can apply the same strategy to each of sub-parts, and proceed until subarrays will decrease to the size of 1. It is convenient to use recursive function for such algorithm:

PureBasic
1
2
3
4
5
6
7
8
9
function quicksort(array, left, right):
    pivot_pos = partition(array, left, right)
    if pivot_pos - left > 1
        quicksort(array, left, pivot_pos - 1)
    end if
    if right - pivot_pos > 1
        quicksort(array, pivot_pos + 1, right)
    end if
end fun

Here the function receives the array being sorted as an argument and also two indices specifying which range should be sorted by this call.

Partitioning
The only tricky moment is how to perform "partitioning" - i.e. choosing pivot and reordering elements to the sides of it. Lazy implementations, especially in functional programming languages, may create two new sub-arrays and filter elements into them - however it is not "honest" since proper quicksort could be done "in-place".

Here is one of the approaches, based on moving large elements to the rightmost end and small elements to the leftmost end step by step:

Pivot is initially copied to temporary variable to provide one "empty" cell and is returned to array only when the pass is over.
Empty space is initially placed on the left side of array.
We maintain two pointers to the segment still not processed - left lt and right rt; the algorithm moves lt and rt towards each other leaving partitioned elements outside.
When the empty space is on the left, we compare elements pointed by other end rt (decreasing it in loop) with pivot, until we find one which is less (and so it should not be on the right side); then this element is swapped with the "empty" space.
Now (when empty space is on the right) we compare elements pointed by lt (increasing it at each step) until we find the element which is greater than pivot and should be swapped with empty space on the right.
So we continue steps 4 and 5 until lt and rt meet - then we restore pivot to this point (which is "empty").
Here is the pseudocode:

PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function partition(array, left, right)
    lt = left
    rt = right
    dir = 'left'        #specifies at which side is currently "empty" space
    pivot = array[left]
    while lt < rt
        if dir = 'left'
            if array[rt] > pivot
                rt = rt - 1
            else
                a[lt] = a[rt]
                lt = lt + 1
                dir = 'right'
            end if
        else
            if array[lt] < pivot
                lt = lt + 1
            else
                a[rt] = a[lt]
                rt = rt - 1
                dir = 'left'
            end if
        end if
    end while
    array[lt] = pivot       #here lt = rt - both points to empty cell where pivot should return
    return lt
end fun

Examine this algorithm step by step with pencil and paper to see how it works.

Problem statement
Please implement the described algorithm and run it on a sample array. For each call of quicksort please output its left and right parameters.

Input data will contain N - the size of array - in the first line.
Next line will contain the array itself (all elements will be different).
Answer should contain left-right ranges for each call of the recursive function in order. Separate values of each pair with a dash, while pairs itself should be separated with spaces.

Example:

input data:
10
38 23 9 19 113 5 42 85 71 112

answer:
0-9 0-3 1-3 1-2 5-9 5-8 5-7

@sourcerer · 04.11.2016, 18:08

dinbo, how it's connected to C++? Do you need translate this code from PureBasic to C++? Or code you have written is just for example and language doesn't matter? What do you really need? C++ implementation?

@dinbo · 04.11.2016, 18:16 **[ТС]**

it is just example of code, you have to convert to c++, i don't know how it work. can you help me ? to write with vector is necessary

@sourcerer · 04.11.2016, 18:35

There are a lot of examples here at forum. Just try to search with these keywords:
.
пузырьковая сортировка
.
сортировка пузырьком
.
bubble sort
.
сортировка вставками
.
insertion sort
.
сортировка выбором
.
selection sort
.
Use search tool this way:

IGPIGP · 04.11.2016, 20:54

Гость:
-Начелдахи недурнасы...
Левый слуга:
-Пашли баши
Правый слуга:
-Пашли баши....
Уходят.
Граф Лудовико:
-Какой занятный язык!

Если бы я знал Паскаль мог бы сказать что-то более определённое. На плюсах это может выглядеть так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;
template<typename T>
int partition_srt(T *ar_ray, int left, int right)
{
int lt = left,
    rt = right;
enum DIR {LEFT, RIGHT};
DIR dir = LEFT;
T pivot = ar_ray[left];
 
while( lt < rt ){
    if(dir == LEFT){
        if (ar_ray[rt] > pivot){
                rt = rt - 1 ;
        }
        else{
                ar_ray[lt] = ar_ray[rt] ;
                lt = lt + 1 ;
                dir = RIGHT ;
        }
    }
    else{
        if (ar_ray[lt] < pivot){
                lt = lt + 1 ;
        }
        else{
                ar_ray[rt] = ar_ray[lt] ;
                rt = rt - 1 ;
                dir = LEFT ;
            }
    }
}
    ar_ray[lt] = pivot;       //here lt = rt - both points to empty cell where pivot should return
    return lt;
}
 
template<typename T>    
void quick_part_sort(T *ar_ray, int left, int right){
    int pivot_pos = partition_srt(ar_ray, left, right);
    if (pivot_pos - left > 1)
        quick_part_sort(ar_ray, left, pivot_pos - 1);
   
    if (right - pivot_pos > 1)
        quick_part_sort(ar_ray, pivot_pos + 1, right);
    }
 
 
int main(int argc, char* argv[])
{
    int ar[]={5, 7, 25, 43, 30, 1, 10, 15, 18, 31 };
 
for(int i=0; i<10; ++i)cout<<ar[i]<<' '; 
cout<<endl;
quick_part_sort(ar, 0, 9);
for(int i=0; i<10; ++i)cout<<ar[i]<<' '; 
cout<<endl;
system("pause");
return 0;
}

Занятная штучка.

@dinbo · 04.11.2016, 21:02 **[ТС]**

IGPIGP, а сможешь решить через вектора?

IGPIGP · 04.11.2016, 21:07

Сообщение от dinbo

IGPIGP, а сможешь решить через вектора?

Хотите вызвать у меня азарт? - Облом. Такой вопрос, как ведро холодной воды. Я думал Вы читаете алгоритмы и вникаете. А на плюсах не получается, пока.
dinbo, Вам задача, - посидите часок и сделайте на векторе. Там практически ничего делать не придётся. Но если не знаете, то это "ничего" потребует некоторых усилий.

@dinbo · 04.11.2016, 22:59 **[ТС]**

IGPIGP, реши, пожалуйста, через вектор

IGPIGP · 05.11.2016, 00:00

Сообщение от dinbo

IGPIGP, реши, пожалуйста, через вектор

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

@Aymurat · 05.11.2016, 10:17

Не по теме:

Весело тут у вас :D

IGPIGP · 05.11.2016, 13:13

Не по теме:

Сообщение от Aymurat

Весело тут у вас

Угощайся. :)
Клянусь, если ТС расскажет о слабых местах алгоритмов Шелла и быстой сортировки, я выложу перегрузку для векторов. :)

Добавлено через 2 часа 48 минут
dinbo, я тут порезвился слегка, но ведь не знал же, что Вы девушка. Пока в соседней теме не вычитал.

Нежелание перевести суть топика на русский (хотя бы в нескольких фразах) и потом вопрос

Сообщение от dinbo

IGPIGP, а сможешь решить через вектора?

вызвали желание пошутить. Вот тут и для вектора перегрузка:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
int partitition_srt(T *ar_ray, int left, int right)
{
int lt = left,
    rt = right;
enum DIR {LEFT, RIGHT};
DIR dir = LEFT;
T pivot = ar_ray[left];
 
while( lt < rt ){
    if(dir == LEFT){
        if (ar_ray[rt] > pivot){
                rt = rt - 1 ;
        }
        else{
                ar_ray[lt] = ar_ray[rt] ;
                lt = lt + 1 ;
                dir = RIGHT ;
        }
    }
    else{
        if (ar_ray[lt] < pivot){
                lt = lt + 1 ;
        }
        else{
                ar_ray[rt] = ar_ray[lt] ;
                rt = rt - 1 ;
                dir = LEFT ;
            }
    }
}
    ar_ray[lt] = pivot;       //here lt = rt - both points to empty cell where pivot should return
    return lt;
}
 
template<typename T>    
void quick_part_sort(T *ar_ray, int left, int right){
    int pivot_pos = partitition_srt(ar_ray, left, right);
    if (pivot_pos - left > 1)
        quick_part_sort(ar_ray, left, pivot_pos - 1);
   
    if (right - pivot_pos > 1)
        quick_part_sort(ar_ray, pivot_pos + 1, right);
    }
 
template<typename T>
int partitition_srt(vector<T> &ar_ray, int left, int right)
{
int lt = left,
    rt = right;
enum DIR {LEFT, RIGHT};
DIR dir = LEFT;
T pivot = ar_ray[left];
 
while( lt < rt ){
    if(dir == LEFT){
        if (ar_ray[rt] > pivot){
                rt = rt - 1 ;
        }
        else{
                ar_ray[lt] = ar_ray[rt] ;
                lt = lt + 1 ;
                dir = RIGHT ;
        }
    }
    else{
        if (ar_ray[lt] < pivot){
                lt = lt + 1 ;
        }
        else{
                ar_ray[rt] = ar_ray[lt] ;
                rt = rt - 1 ;
                dir = LEFT ;
            }
    }
}
    ar_ray[lt] = pivot;       //here lt = rt - both points to empty cell where pivot should return
    return lt;
}
 
template<typename T>    
void quick_part_sort(vector<T> &ar_ray, int left, int right){
    int pivot_pos = partitition_srt(ar_ray, left, right);
    if (pivot_pos - left > 1)
        quick_part_sort(ar_ray, left, pivot_pos - 1);
   
    if (right - pivot_pos > 1)
        quick_part_sort(ar_ray, pivot_pos + 1, right);
    }
 
int main(int argc, char* argv[])
{
    int ar[]={5, 7, 25, 43, 30, 1, 10, 15, 18, 31 };
 
for(int i=0; i<10; ++i)cout<<ar[i]<<' '; 
cout<<endl;
quick_part_sort(ar, 0, 9);
for(int i=0; i<10; ++i)cout<<ar[i]<<' '; 
cout<<endl<<endl;
 
int arr[]={5, 7, 25, 43, 30, 1, 10, 15, 18, 31 };
 
vector<int> vec(arr, arr+10);
for(int i=0; i<10; ++i)cout<<vec[i]<<' '; 
cout<<endl;
quick_part_sort(vec, 0, 9);
for(int i=0; i<10; ++i)cout<<vec[i]<<' '; 
cout<<endl;
 
system("pause");
return 0;
}

и всё же непонятно. Класс это же не аудитория... Вы в школе учитесь?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	04.11.2016, 18:08
	dinbo, how it's connected to C++? Do you need translate this code from PureBasic to C++? Or code you have written is just for example and language doesn't matter? What do you really need? C++ implementation? 0

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 18:16 [ТС]
	it is just example of code, you have to convert to c++, i don't know how it work. can you help me ? to write with vector is necessary 0

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	04.11.2016, 18:35
	There are a lot of examples here at forum. Just try to search with these keywords: . `пузырьковая сортировка` . `сортировка пузырьком` . `bubble sort` . `сортировка вставками` . `insertion sort` . `сортировка выбором` . `selection sort` . Use search tool this way: Миниатюры 1

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 21:02 [ТС]
	IGPIGP, а сможешь решить через вектора? 0

@dinbo 0 / 0 / 0 Регистрация: 03.11.2016 Сообщений: 18
	04.11.2016, 22:59 [ТС]
	IGPIGP, реши, пожалуйста, через вектор 0

@Aymurat
	05.11.2016, 10:17
	Не по теме: Весело тут у вас :D 0