summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorleo <leo@azuminha.com>2024-02-14 16:27:12 -0300
committerleo <leo@azuminha.com>2024-02-14 16:27:12 -0300
commita52f63efd443ec92a53509915bc4d8e69b55a51f (patch)
tree9c61e17ec19ce320736aaff0c169927fd26a0817
-rw-r--r--algorithms/quicksort.c46
-rw-r--r--data_structures/linked_list.c98
2 files changed, 144 insertions, 0 deletions
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 <stdio.h>
+
+//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;
+}
diff --git a/data_structures/linked_list.c b/data_structures/linked_list.c
new file mode 100644
index 0000000..b75dfea
--- /dev/null
+++ b/data_structures/linked_list.c
@@ -0,0 +1,98 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct Node{
+ int value;
+ struct Node* next;
+}list;
+
+void* create_list(){
+ void* ptr = NULL;
+ return ptr;
+}
+
+void add_node(list **head, int value){
+ list *node = (list*)malloc(sizeof(list));
+ node->value = value;
+ node->next = NULL;
+
+ if(*head == NULL){
+ *head = node;
+ }else{
+ list *tmp = *head;
+ while(tmp->next != NULL){
+ tmp = tmp->next;
+ }
+ tmp->next = node;
+ }
+}
+
+void print_list(list *head){
+ while(head != NULL){
+ printf("%d -> ", head->value);
+ head = head->next;
+ }
+ printf("\n");
+}
+
+void remove_first(list **head){
+ list *tmp = *head;
+ *head = (*head)->next;
+ free(tmp);
+}
+
+int list_len(list *head){
+ int cont = 0;
+ while(head != NULL){
+ cont++;
+ head = head->next;
+ }
+ return cont;
+}
+
+void add_node_pos(list **head, int pos, int value){
+ if(pos > list_len(*head)){
+ fprintf(stderr, "Posicao nao existe\n");
+ return;
+ }
+
+ list *new_node = (list*)malloc(sizeof(list));
+ new_node->value = value;
+
+ if(pos == 0){
+ new_node->next = *head;
+ *head = new_node;
+ return;
+ }
+
+
+ int cont = 0;
+ list *f = *head;
+ list *s = NULL;
+ while(cont != pos){
+ s = f;
+ f = f->next;
+ cont++;
+ }
+ s->next = new_node;
+ new_node->next = f;
+}
+
+int main(int argv, char* argc[]){
+ list *l = create_list();
+
+ add_node(&l, 10);
+ add_node(&l, 20);
+ add_node(&l, 30);
+ print_list(l);
+ add_node_pos(&l, 3, 50);
+ print_list(l);
+ add_node_pos(&l, 3, 40);
+ print_list(l);
+ add_node_pos(&l, 0, 0);
+ print_list(l);
+ add_node_pos(&l, 1, 5);
+ print_list(l);
+
+ return 0;
+}