Sortowanie w wektorze

Witam, mam za zadanie posegregować elementy w wektorze tak, żeby najpierw były liczby nieparzyste a następnie parzyste i nie mam pojęcia jak to zrobić. Chciałem to zrobić funkcją swap, jeżeli podczas przechodzenia przez tablice napotka liczbę nieparzysta to zamieniają się z następnym elementem miejscami, lecz to nie działa. Ma ktoś może jakiś inny pomysł? Z góry dziękuje za pomoc

Jeżeli nie Musiz pisać ręcznie algorytmu sortowania, to można uzyć sort z STL, podając mu funkcję porównującą (parity - sortuje względem "parzystości", parzyste najpierw):

#include <iostream>
#include <vector>
#include <algorithm>
bool parity(int a, int b) {
	return ((a % 2 == 0) >= (b % 2 == 0));
}
int main() {	
	std::vector<int> v = {2, 3, 4, 5};
	std::sort (v.begin(), v.end(), parity);
	for (auto e: v)
		cout <<  e << " "; // -> 4 2 5 3
    cout << "\n";
}

EDIT: A jeżeli Musisz, to Możesz "podłączyć" swoją, dowolną funkcję sortującą z predykatem.

@lion137: Tu bardziej adekwatne będzie raczej std::partition lub std::stable_partition ;)

@Rzemysł: Jeśli musisz to samemu napisać tutaj masz przykład jak to zrobić.