Commits

Cédric Bonhomme  committed 7123c13

Initial commit. Added Bubble, Casier, Fusion, Selection and Insertion sorting algorithms.

  • Participants

Comments (0)

Files changed (7)

File benchmark.py

+#! /usr/bin/env python
+#-*- coding: utf-8 -*-
+
+import time
+import random
+
+from fusion import Fusion
+from bubble import Bubble
+from selection import Selection, Selection_Better
+from casier import Casier
+from insertion import Insertion, Insertion_Better
+from natif import Natif
+
+
+class Benchmark(object):
+    """
+    Benchmark on sorting functions.
+    """
+    def __init__(self, nb_elements = [500,1000,5000,10000], nb_max = 2**64):
+        """
+        Initializations.
+        """
+        self.nb_elements = nb_elements
+        self.nb_max = nb_max
+        self.list = []
+        self.sorting_functions = {"Fusion" : [], \
+                                    "Bubble" : [], \
+                                    "Selection": [], \
+                                    "Selection_Better": [], \
+                                    "Casier": [], \
+                                    "Insertion": [], \
+                                    "Insertion_Better": [], \
+                                    "Natif": []}
+
+    def run(self):
+        """
+        Launch the benchmark.
+        """
+        for nb_element in self.nb_elements:
+            self.list = []
+            for i in range(nb_element):
+                self.list.append(random.randint(0, self.nb_max))
+
+            for sorting_function in self.sorting_functions.keys():
+                print("Sorting with", sorting_function + "...")
+                list_to_sort = self.list[:]
+                begin  = time.clock()
+                sorting_func = globals()[sorting_function](list_to_sort)
+                sorting_func.sort()
+                end = time.clock()
+                self.sorting_functions[sorting_function] = self.sorting_functions[sorting_function] + ["%.10f" % (end - begin)]
+
+    def write(self):
+        """
+        Write results in a file.
+        """
+        result = self.__str__()
+        file = open('result', 'w')
+        file.write(result)
+        file.close()
+
+    def __str__(self):
+        """
+        Display the results.
+        """
+        table = "Algorithm"
+        for i in self.nb_elements:
+            table = table  + "\t\t\t\t" + str(i)
+        table = table + "\n\n"
+        for algo in list(self.sorting_functions.keys()):
+            table = table + algo + "\t\t\t"
+            table = table + "\t\t\t".join(self.sorting_functions[algo])
+            table = table + "\n"
+        table = table + "\nTime in seconds.\n\nMachine:\n\n"
+        fich = open('/proc/cpuinfo', 'r')
+        info = fich.read()
+        fich.close()
+        table = table + info
+        return table
+
+        
+
+if __name__ == '__main__':
+    # Point of entry in execution mode.
+    #benchmark = Benchmark(nb_elements = [100, 2000], nb_max=50)
+    benchmark = Benchmark()
+    benchmark.run()
+    #print(benchmark)
+    benchmark.write()
+
+
+
+
+class Bubble(object):
+    """
+    Bubble sort - O(n^2)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        for i in range(len(l)):
+            for j in reversed(range(i,len(l))):
+                if l[j]<l[j-1]:
+                    t=l[j]
+                    l[j]=l[j-1]
+                    l[j-1]=t
+
+
+
+
+class Casier(object):
+    """
+    Casier sort - O(n)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        maxi=max(l)
+        ll = []
+        for i in range(len(str(maxi))):
+            ll.append([])
+        for j in range(len(str(maxi))):
+            for k in range(11):
+                ll[j].append([])
+        for i in l:
+            ll[len(str(i))-1][10].append(i)
+        for i in range(len(str(maxi))):
+            for j in reversed(range(i+1)):
+                for k in ll[i][10]:
+                    ll[i][int(str(k)[j])].append(k)
+                ll[i][10]=[]
+                for m in range(10): ll[i][10].extend(ll[i][m])
+                for m in range(10): ll[i][m]=[]
+        l=[]
+        for i in range(len(str(maxi))):
+            l.extend(ll[i][10])
+
+
+
+
+class Fusion(object):
+    """
+    Fusion sort - O(nlog(n))
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        def Tri_Fusion_interne(l):
+            if len(l)<2:
+                return l
+            return self.merge(Tri_Fusion_interne(l[:len(l)//2]), Tri_Fusion_interne(l[len(l)//2:]))
+        l[:] = Tri_Fusion_interne(l)
+
+    def merge(self, l1, l2):
+        """Merge two sorted lists."""
+        l = []
+        i = j =0
+        n1=len(l1)
+        n2=len(l2)
+        while True:
+            if i<n1 and j<n2:
+                if l1[i]<l2[j]:
+                    l.append(l1[i])
+                    i+=1
+                else:
+                    l.append(l2[j])
+                    j+=1
+            elif i>=n1:
+                l.extend(l2[j:])
+                break
+            else:
+                l.extend(l1[i:])
+                break
+        return l

File insertion.py

+
+
+
+
+class Insertion(object):
+    """
+    Insertion sort - O(n^2)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        for i in range(len(l)):
+            m=l[i]
+            for j in range(i+1):
+                if m<l[j]:
+                    for k in reversed(range(j+1,i+1)):
+                        l[k]=l[k-1]
+                    l[j]=m
+                    break
+
+class Insertion_Better(object):
+    """
+    Insertion sort - O(n^2)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        for i in range(len(l)):
+            m=l[i]
+            for j in range(i+1):
+                if m<l[j]:
+                    l[j+1:i+1] = l[j:i]
+                    l[j]=m
+                    break
+
+
+
+
+class Natif(object):
+    """
+    Casier sort - O(n)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        l.sort()

File selection.py

+
+
+
+
+class Selection(object):
+    """
+    Selection sort - O(n^2)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        for i in range(len(l)-1):
+            mini=i
+            for j in range(i+1,len(l)):
+                if l[j] < l[mini]:
+                    mini=j
+                self.swap(l,i,mini)
+
+    def swap(self, l, i, j):
+        """echange 2 valeurs d'une liste"""
+        l[i], l[j] = l[j], l[i]
+
+class Selection_Better(object):
+    """
+    Selection sort - O(n^2)
+    """
+    def __init__(self, l):
+        self.unsorted_list = l
+
+    def sort(self):
+        l = self.unsorted_list
+        for i in range(len(l) - 1):
+            mini=i
+            lmini = l[i]
+            for j in range(i + 1, len(l)):
+                if l[j] < lmini:
+                    mini = j
+                    lmini = l[j]
+            l[mini], l[i] = l[i], lmini