In my quicksort implementation using C++ vectors, is partition function same as using the trivial method of swaps?

Question

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void quick_sort(vector<int> &a, int start, int end);
int partition(vector<int> &a, int start, int end);

int main(){
    vector<int> v = {7, 6, 5, 4, 3, 2, 1};
    int n(7);
    quick_sort(v, 0, n);
    for (auto& itr : v){
        cout << itr << ' ';
    }
    return 0;
}

void quick_sort(vector<int> &a, int start, int end){
    if (start < end){
        int index;
        index = partition(a, start, end);
        
        quick_sort(a, start, index - 1);
        quick_sort(a, index, end);
    }
}

int partition(vector<int> &a, int start, int end){
    int pivot, count(0);
    pivot = a[end - 1];
    for (int i = start; a[i] != pivot; i++){
        if (a[i] > pivot){
            a.insert(a.begin()+end, a[i]);
            a.erase(a.begin() + i);
            count++;
            i--;
        }
    }
    return end-count;
}

Here in the partition function I have used insert and erase functions provided in the STL library.

Will the time complexity for partition function be greater than O(n) (The case when using swaps)?

According to me worst case would be when the pivot element is the smallest element, then all of the (n-1) elements will be pushed at the end of the vector.

EDIT:

int partition(vector<int> &a, int start, int end){
    int pivot;
    pivot = end - 1;
    for (int i = start; i < end; i++){
        if (a[i] > a[pivot] && i < pivot){
            swap(a[i], a[pivot]);
            pivot = i;
        }
        else if (a[i] < a[pivot] && i > pivot){
            swap(a[i], a[pivot]);
            pivot = i;
        }
    }
    return pivot + 1;
}

This partition function runs in O(n) time.

partition can be done in `O(n)`, but your is `O(n²)`. `erase`/`insert` is `O(n)`. — Jarod42, Jun 03 '21 at 10:42
Please don't do [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice), particularly never in combinaton. — πάντα ῥεῖ, Jun 03 '21 at 11:01

score 0 · Accepted Answer · answered Jun 03 '21 at 11:10

You move every element after end doing the insert, and every element after i doing the erase. This version is much worse than swapping. With std::swap, you only touch two elements.

Aside: sorting in C++ is traditionally done with iterators, not indexes, i.e.

using iterator = std::vector<int>::iterator; 

void quick_sort(iterator start, iterator end);
iterator partition(iterator start, iterator end);

In my quicksort implementation using C++ vectors, is partition function same as using the trivial method of swaps?

1 Answers1