From a52f63efd443ec92a53509915bc4d8e69b55a51f Mon Sep 17 00:00:00 2001 From: leo Date: Wed, 14 Feb 2024 16:27:12 -0300 Subject: first --- algorithms/quicksort.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 algorithms/quicksort.c (limited to 'algorithms') diff --git a/algorithms/quicksort.c b/algorithms/quicksort.c new file mode 100644 index 0000000..a0f0153 --- /dev/null +++ b/algorithms/quicksort.c @@ -0,0 +1,46 @@ +#include + +//pior caso \theta(n²) +//eficiencia media \theta(nlog(n)) +int partition(int *A, int p, int r){ + //escolher o pivot(vai ser o ultimo, pois fica mais facil de implementar + //caso queira escolher um pivo aleatório, basta trocar A[pos_aleatoria] com A[r] + int pivot = A[r]; + int pos_pivot = p; + for(int i=p; i < r; ++i){ + if(A[i] <= pivot){ + int aux = A[i]; + A[i] = A[pos_pivot]; + A[pos_pivot] = aux; + + pos_pivot++; + } + } + int aux = A[pos_pivot]; + A[pos_pivot] = pivot; + A[r] = aux; + + return pos_pivot; +} + +int quicksort(int *A, int p, int r){ + printf("p: %d, r: %d\n", p, r); + if(p < r){ + int q = partition(A, p, r); + quicksort(A, p, q-1); + quicksort(A, q+1, r); + } +} + + +int main(){ + // pp = 0 + // 13 32 52 69 420 22 42 + int A[7] = {42, 32, 52, 69, 420, 22, 13}; + quicksort(A, 0, 6); + for(int i=0; i<7; ++i){ + printf("%d ", A[i]); + } + printf("\n"); + return 0; +} -- cgit v1.2.3