Quicksort

qs.cpp

#include <vector>
#include <iostream>

template <typename T>
std::vector<T> qs(std::vector<T> v){
    std::vector<T> smaller, greater;
    T pivot;

    if(!v.size()){
        return smaller;
    }

    pivot = v.back();
    v.pop_back();

    for(T val : v){
        if(val <= pivot){
            smaller.push_back(val);
        }
        else{
            greater.push_back(val);
        }
    }

    smaller = qs(smaller);
    greater = qs(greater);

    smaller.push_back(pivot);
    smaller.insert(smaller.end(), greater.begin(), greater.end());

    return smaller;
}

int main(){
    std::vector<int> foo;
    foo.push_back(2);
    foo.push_back(4);
    foo.push_back(1);
    foo.push_back(7);

    foo = qs(foo);

    for(auto val : foo){
        std::cout<<val<<" ";
    }

    std::cout<<"\n";
}

qs.hs

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) = qs [y | y <- xs, y <= x] ++ [x] ++ qs [y | y <- xs, y > x]

qs.py

def qs(v):
    if len(v) == 0:
        return list()

    pivot = v[len(v)//2]
    v.remove(pivot)

    smaller = qs([x for x in v if x <= pivot])
    greater = qs([x for x in v if x > pivot])

    smaller.append(pivot)
    smaller.extend(greater)

    return smaller


if __name__ == '__main__':
    print(qs([1, 3, 5, 3, 2, 7]))