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.

Answer 1

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);