CDSusingPython/instrumented_sort.py at master · rishabkatta/CDSusingPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
@author-1: Rishab Katta
@author-2: Akhil Karrothu
'''

counter=0
count1=0


def msort(alist):
    '''

    :param alist: Random list generated by generate_data function of the sort_experiment module
    :return: a tuple of sortedlist and the number of comparisions taken to achieve the sorted list
    '''

    global counter
    sortedlist = []
    if len(alist) < 2:
        return (alist, counter)
    mid = int(len(alist) / 2)
    y = msort(alist[:mid])
    z = msort(alist[mid:])
    leftpart=y[0]
    rightpart=z[0]
    i = 0
    j = 0
    while i < len(leftpart) and j < len(rightpart):
        counter = counter+1
        if leftpart[i] > rightpart[j]:
            sortedlist.append(rightpart[j])
            j += 1
        else:
            sortedlist.append(leftpart[i])
            i += 1
    sortedlist = sortedlist + leftpart[i:]
    sortedlist = sortedlist + rightpart[j:]
    return (sortedlist, counter)

def ssort(alist):
    '''

    :param alist: Random list generated by generate_data function of the sort_experiment module
    :return: a tuple of sortedlist and the number of comparisions taken to achieve the sorted list
    '''

    global count1
    for fs in range(len(alist)-1,0,-1):
        maxpos=0
        for location in range(1,fs+1):
            count1 = count1 + 1
            if alist[location]>alist[maxpos]:
                maxpos = location
        temp = alist[fs]
        alist[fs] = alist[maxpos]
        alist[maxpos] = temp
    return (alist,count1)