From a7c59b01a5b9969f1728dfcb1b954f850f250b2d Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Fri, 3 Mar 2017 18:14:19 +0100 Subject: [PATCH] TP3: Add merge sort implementation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- TP3/Makefile | 79 ++++++++++++++++++++++++++++++++++++++++++++++++++++ TP3/tp3.c | 62 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 141 insertions(+) create mode 100644 TP3/Makefile create mode 100644 TP3/tp3.c diff --git a/TP3/Makefile b/TP3/Makefile new file mode 100644 index 0000000..6a950a1 --- /dev/null +++ b/TP3/Makefile @@ -0,0 +1,79 @@ +# Sample Makefile to build simple project. +# +# This Makefile expect all source files (.c) to be at the same level, in the +# current working directory. +# +# It will automatically generate dependencies, compile all files, and produce a +# binary using the provided name. +# +# Set BINARY_NAME to the name of the binary file to build. +# Set BUILD_TYPE to either debug or release +# +# Automatic dependencies code from: +# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr +BINARY_NAME=tp3 +BUILD_TYPE=debug + +# ==================================== +# DO NOT CHANGE STUFF BEYOND THIS LINE +# ==================================== + +all: $(BINARY_NAME) + +CC=gcc +LD=gcc + +WARN_FLAGS = -Wall -Wextra +STD_FLAG = -std=c99 + +ifeq ($(BUILD_TYPE),debug) +BUILDDIR := .build/debug +DEBUG_FLAG = -g +STRIP_FLAG = +OPTI_FLAG = -O0 +else +BUILDDIR := .build/release +DEBUG_FLAG = +STRIP_FLAG = -s +OPTIFLAG = -O3 +endif + +CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG) +LDFLAGS := $(LDFLAGS) $(STRIP_FLAG) + +OBJDIR := $(BUILDDIR)/objs +$(shell mkdir -p $(OBJDIR)) + +SRCS=$(wildcard *.c) +OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS)) + +DEPDIR := $(BUILDDIR)/deps +$(shell mkdir -p $(DEPDIR)) +DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td +POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d + +$(BINARY_NAME): $(OBJS) + @echo "[LD ] $@" + @$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ + +$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d + @echo "[C ] $*" + @$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@ + @$(POSTCOMPILE) + +$(DEPDIR)/%.d: ; + +.PRECIOUS: $(DEPDIR)/%.d + +include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))) + +clean: + @echo "[CLN]" + -@rm -r $(BUILDDIR) + -@rm $(BINARY_NAME) + +disassemble: $(BINARY_NAME) + objdump -d $< | less + +symbols: $(BINARY_NAME) + objdump -t $< | sort | less diff --git a/TP3/tp3.c b/TP3/tp3.c new file mode 100644 index 0000000..4caf275 --- /dev/null +++ b/TP3/tp3.c @@ -0,0 +1,62 @@ +#include +#include + +void AfficheTab(int T[], int n) { + for (int i = 0; i < n; i++) { + printf("T[%d]=%d\n", i, T[i]); + } +} + +void TriFusion(int T[], int n) { + int i = 0, j = 0, k = 0; + int* T1; + int* T2; + + T1 = malloc(n/2*sizeof(int)); + T2 = malloc((n - n/2)*sizeof(int)); + + if (n > 1) { + for (int i = 0; i < n/2; i++) { + T1[i] = T[i]; + T2[i] = T[i + n/2]; + } + TriFusion(T1, n/2); + TriFusion(T2, n/2); + while (k < n/2 && j < n/2) { + if (T1[k] <= T2[j]) { + T[i] = T1[k]; + i++; + k++; + } else { + T[i] = T2[j]; + i++; + j++; + } + } + while (k < n/2) { + T[i] = T1[k]; + i++; + k++; + } + while (j < n/2) { + T[i] = T2[j]; + i++; + j++; + } + free(T1); + free(T2); + } +} + +int main() { + int T[] = {4, 2, 7, 3, 8, 1, 6, 5}; + int tabSize = sizeof(T)/sizeof(T[0]); + + AfficheTab(T, tabSize); + + TriFusion(T,tabSize); + + AfficheTab(T, tabSize); + + return 0; +} -- 2.34.1