Ordenação Pares e ímpares dentro de vetor

[rzp 0]

Olá, estou com um exercício para fazer:
Suponha um vetor com números inteiros positivos pares e ímpares. Elaborarum algoritmo para colocar todos os números pares à frente no vetor e os ímpares no final. NÃO DEVE SER UTILIZADO UM VETOR AUXILIAR.

O usuário deve determinar o tamanho do vetor, e gerar valores aleatorios.
Meu código por enquanto está assim, só não sei como fazer para organizar os pares de um "lado" e os impares do outro sem usar um vetor/variavel auxiliar.

@EDIT:

Também tenho que mostrar quanto tempo se passou na execução inteira do programa.

#include <stdio.h>
#include <stdlib.h>

int main () {
    int i, n, vetor[n];
    printf("Digite o tamanho do vetor: ");
    scanf("%d", &n);
    srand(1000000);
        for (i = 0; i < n ; i++) {
            printf("Os valores são %d.\n", rand() % n);
 }
return 0;
}