X-Git-Url: https://git.piment-noir.org/?p=TD_C.git;a=blobdiff_plain;f=TP_9%2Fexo2%2Fclist.c;h=2fd3dfd98f734570e2551f6a774d4af9eae9a62d;hp=afdb00f6c12e84617d2d360dc331c8849dee94a5;hb=5d64063095177554839e67ddc73193929f115d07;hpb=954256b7be7394db3b0b64c6a74fb5f79bec8b5e

diff --git a/TP_9/exo2/clist.c b/TP_9/exo2/clist.c
index afdb00f..2fd3dfd 100644
--- a/TP_9/exo2/clist.c
+++ b/TP_9/exo2/clist.c
@@ -1,11 +1,11 @@
-#include <stdlib.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include <stdbool.h>
 
 #include "clist.h"
 
 link_t* list_new(int value) {
-    link_t* link_new;	
+    link_t* link_new;
     link_new = malloc(sizeof(link_t));
     link_new->value = value;
     link_new->next = NULL;
@@ -14,12 +14,12 @@ link_t* list_new(int value) {
 
 link_t* list_append(link_t* head, int value) {
 
-    if (head == NULL) { 
+    if (head == NULL) {
         return head = list_new(value);
     } else {
         link_t* head_first = head;
         while (head->next != NULL) {
-    	    head = head->next; 
+            head = head->next;
         }
         head->next = list_new(value);
         return head_first;
@@ -28,7 +28,7 @@ link_t* list_append(link_t* head, int value) {
 
 link_t* list_prepend(link_t* head, int value) {
     link_t* first_link = list_new(value);
-    
+
     first_link->next = head;
     return first_link;
 }
@@ -36,11 +36,11 @@ link_t* list_prepend(link_t* head, int value) {
 link_t* list_insert(link_t* head, unsigned index, int value) {
 
     if (index == 0) {
-        return list_prepend(head, value);  
+        return list_prepend(head, value);
     } else if (index == list_count(head)) {
         return list_append(head, value);
     } else {
-        link_t* link_insrt = list_new(value);  
+        link_t* link_insrt = list_new(value);
         link_t* head_first = head;
         link_t* head_next = NULL;
         for (unsigned i = 0; i < index-1; i++) {
@@ -49,7 +49,7 @@ link_t* list_insert(link_t* head, unsigned index, int value) {
         head_next = head->next;
         head->next = link_insrt;
         head = link_insrt;
-        head->next = head_next; 
+        head->next = head_next;
         return head_first;
     }
 }
@@ -58,7 +58,7 @@ link_t* list_delete(link_t* head, unsigned index) {
     link_t* head_prev = NULL;
     link_t* head_next = NULL;
     link_t* head_ret = NULL;
-   
+
     if (head == NULL) {
         return NULL;
     } else if (index == 0) {
@@ -108,23 +108,64 @@ link_t* list_sort(link_t* head) {
                 tmp = head->value;
                 head->value = head->next->value;
                 head->next->value = tmp;
-	        isswaped = true;
+                isswaped = true;
             }
-	    head = head->next;
+            head = head->next;
         }
-	/* Reloop at the beginning of the list until there's values swaped */
-	head = head_first;
+        /* Reloop at the beginning of the list until there's values swaped */
+        head = head_first;
     } while (isswaped);
     return head_first;
 }
 
+static link_t* _list_merge_sort(link_t* head1, link_t* head2) {
+    link_t* head_result = NULL;
+
+    if (head1 == NULL) {
+        return head2;
+    }
+    if (head2 == NULL) {
+        return head1;
+    }
+    if (head1->value < head2->value) {
+        head_result = head1;
+        head_result->next = _list_merge_sort(head1->next, head2);
+    } else {
+        head_result = head2;
+        head_result->next = _list_merge_sort(head1, head2->next);
+    }
+    return head_result;
+}
+
+link_t* list_merge_sort(link_t* head) {
+    link_t* head1;
+    link_t* head2;
+
+    if (head == NULL || head->next == NULL) {
+        return head;
+    }
+
+    head1 = head;
+    head2 = head->next;
+    while (head2 != NULL && head2->next != NULL) {
+        head = head->next;
+        head2 = head->next->next;
+    }
+    head2 = head->next;
+    head->next = NULL;
+
+    head1 = list_merge_sort(head1);
+    head2 = list_merge_sort(head2);
+    return _list_merge_sort(head1, head2);
+}
+
 unsigned list_count(link_t* head) {
     unsigned count = 0;
-    
+
     while (head != NULL) {
         ++count;
         head = head->next;
-    } 
+    }
     return count;
 }
 
@@ -139,13 +180,13 @@ void list_set(link_t* head, unsigned index, int value) {
 }
 
 int list_get(link_t* head, unsigned index) {
-    unsigned count = 0;    
+    unsigned count = 0;
 
     while (head != NULL && count < index) {
         ++count;
-        head = head->next; 
+        head = head->next;
     }
-    if (head != NULL) { 
+    if (head != NULL) {
         return head->value;
     } else {
         return -1;
@@ -168,8 +209,8 @@ void list_display_values(link_t* head) {
     printf("------Begin------\n");
     while (head != NULL) {
         printf("value at [%d]=%d\n", i, head->value);
-	head = head->next;
-	i++;
+        head = head->next;
+        i++;
     }
     printf("------End------\n");
 }