From: Jerome Benoit <jerome.benoit@sap.com>
Date: Sun, 5 Mar 2017 22:14:40 +0000 (+0100)
Subject: TP 9 exo2: Implement a merge sort function for the linked list.
X-Git-Url: https://git.piment-noir.org/?p=TD_C.git;a=commitdiff_plain;h=4a758ce5f71ecc19fb6457595fb04c18b6918b9f

TP 9 exo2: Implement a merge sort function for the linked list.

Signed-off-by: Jerome Benoit <jerome.benoit@sap.com>
---

diff --git a/TP_9/exo2/clist.c b/TP_9/exo2/clist.c
index afdb00f..ae7db6f 100644
--- a/TP_9/exo2/clist.c
+++ b/TP_9/exo2/clist.c
@@ -1,5 +1,6 @@
-#include <stdlib.h>
 #include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
 #include <stdbool.h>
 
 #include "clist.h"
@@ -118,6 +119,47 @@ link_t* list_sort(link_t* head) {
     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;
     
diff --git a/TP_9/exo2/clist.h b/TP_9/exo2/clist.h
index a08ec17..2ca5752 100644
--- a/TP_9/exo2/clist.h
+++ b/TP_9/exo2/clist.h
@@ -14,6 +14,7 @@ link_t* list_insert(link_t* head, unsigned index, int value);
 link_t* list_delete(link_t* head, unsigned index);
 link_t* list_concat(link_t* first, link_t* second);
 link_t* list_sort(link_t* head);
+link_t* list_merge_sort(link_t* head);
 unsigned list_count(link_t* head);
 void list_set(link_t* head, unsigned index, int value);
 int list_get(link_t* head, unsigned index);
diff --git a/TP_9/exo2/exo2.c b/TP_9/exo2/exo2.c
index b06d7a4..810bd9e 100644
--- a/TP_9/exo2/exo2.c
+++ b/TP_9/exo2/exo2.c
@@ -35,7 +35,8 @@ int main() {
     list_display_values(head2);
     head = list_concat(head1, head2);
     list_display_values(head);
-    head = list_sort(head);
+    head = list_merge_sort(head);
+    //head = list_sort(head);
     list_display_values(head);
     //list_clear(head1);
     //list_clear(head2);