QuickSort.partition() - Code Metrics - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

QuickSort.partition() C
last analyzed 2017-05-26 05:56 UTC

↳ Parent: QuickSort

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	7
c	1
b	0
f	0
dl	0
loc	23
rs	5.5

import pyalgs.algorithms.commons.util as util

class SelectionSort(object):
    """ Order of Growth: N^2
    """

    @staticmethod
    def sort(a):
        N = len(a)
        for i in range(N):
            k = i
            for j in range(i + 1, N):
                if util.less(a[j], a[k]):
                    k = j
            util.exchange(a, i, k)


class InsertionSort(object):
    @staticmethod
    def sort(a, lo=None, hi=None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a) - 1

        for i in range(lo, hi + 1):
            for j in reversed(range(1, i + 1)):
                if util.less(a[j], a[j - 1]):
                    util.exchange(a, j, j - 1)
                else:
                    break


class ShellSort(object):
    @staticmethod
    def sort(a):
        N = len(a)
        H = 0
        while H < N // 3:
            H = 3 * H + 1

        for h in reversed(range(1, H)):
            for i in range(h, N):
                for j in range(i, h - 1, -h):
                    if util.less(a[j], a[j - h]):
                        util.exchange(a, j, j - h)
                    else:
                        break


class MergeSort(object):
    CUTOFF = 7

    @staticmethod
    def sort(a, lo=None, hi=None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a) - 1

        aux = [0] * len(a)
        MergeSort._sort(a, aux, lo, hi)

    @staticmethod
    def _sort(a, aux, lo, hi):
        if lo >= hi:
            return

        if hi - lo + 1 < MergeSort.CUTOFF:
            InsertionSort.sort(a, lo, hi)
            return

        mid = lo + (hi - lo) // 2
        MergeSort._sort(a, aux, lo, mid)
        MergeSort._sort(a, aux, mid + 1, hi)
        MergeSort._merge(a, aux, lo, mid, hi)

    @staticmethod
    def _merge(a, aux, lo, mid, hi):
        i = lo
        j = mid + 1

        for k in range(lo, hi + 1):
            aux[k] = a[k]

        for k in range(lo, hi + 1):
            if i > mid:
                a[k] = aux[j]
                j += 1
            elif j > hi:
                a[k] = aux[i]
                i += 1
            elif util.less(aux[i], aux[j]):
                a[k] = aux[i]
                i += 1
            else:
                a[k] = aux[j]
                j += 1


class QuickSort(object):
    CUTOFF = 7

    @staticmethod
    def sort(a, lo=None, hi=None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a) - 1

        if lo >= hi:
            return

        if hi - lo + 1 < QuickSort.CUTOFF:
            InsertionSort.sort(a, lo, hi)
            return

        j = QuickSort.partition(a, lo, hi)

        QuickSort.sort(a, lo, j - 1)
        QuickSort.sort(a, j + 1, hi)

    @staticmethod
    def partition(a, lo, hi):
        i = lo
        j = hi

        while True:
            while not util.less(a[lo], a[i]):
                i += 1
                if i >= hi:
                    break

            while util.less(a[lo], a[j]):
                j -= 1
                if j <= lo:
                    break

            if i >= j:
                break

            util.exchange(a, i, j)

        util.exchange(a, lo, j)
        return j


class ThreeWayQuickSort(object):
    CUTOFF = 7

    @staticmethod
    def sort(a, lo=None, hi=None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a) - 1

        if lo >= hi:
            return

        if hi - lo + 1 < ThreeWayQuickSort.CUTOFF:
            InsertionSort.sort(a, lo, hi)
            return

        i = lo
        lt = lo
        gt = hi

        while i <= gt:
            if util.less(a[i], a[lo]):
                util.exchange(a, i, lt)
                i += 1
                lt += 1
            elif util.less(a[lo], a[i]):
                util.exchange(a, i, gt)
                gt -= 1
            else:
                i += 1

        ThreeWayQuickSort.sort(a, lo, lt - 1)
        ThreeWayQuickSort.sort(a, gt + 1, hi)


class HeapSort(object):
    @staticmethod
    def sort(a):
        n = len(a)

        print(a)
        for k in range(n // 2, 0, -1):
            HeapSort.sink(a, k, n)

        while n > 1:
            util.exchange(a, HeapSort.index(1), HeapSort.index(n))
            n -= 1
            HeapSort.sink(a, 1, n)

    @staticmethod
    def sink(a, k, n):
        while k * 2 <= n:
            child = 2 * k
            if child < n and util.greater(a[HeapSort.index(child+1)], a[HeapSort.index(child)]):
                child = child + 1
            if util.greater(a[HeapSort.index(child)], a[HeapSort.index(k)]):
                util.exchange(a, HeapSort.index(child), HeapSort.index(k))
                k = child
            else:
                break

    @staticmethod
    def index(k):
        return k-1


1			import pyalgs.algorithms.commons.util as util
2
3			class SelectionSort(object):
4			""" Order of Growth: N^2
5			"""
6
7			@staticmethod
8			def sort(a):
9			N = len(a)
10			for i in range(N):
11			k = i
12			for j in range(i + 1, N):
13			if util.less(a[j], a[k]):
14			k = j
15			util.exchange(a, i, k)
16
17
18			class InsertionSort(object):
19			@staticmethod
20			def sort(a, lo=None, hi=None):
21			if lo is None:
22			lo = 0
23			if hi is None:
24			hi = len(a) - 1
25
26			for i in range(lo, hi + 1):
27			for j in reversed(range(1, i + 1)):
28			if util.less(a[j], a[j - 1]):
29			util.exchange(a, j, j - 1)
30			else:
31			break
32
33
34			class ShellSort(object):
35			@staticmethod
36			def sort(a):
37			N = len(a)
38			H = 0
39			while H < N // 3:
40			H = 3 * H + 1
41
42			for h in reversed(range(1, H)):
43			for i in range(h, N):
44			for j in range(i, h - 1, -h):
45			if util.less(a[j], a[j - h]):
46			util.exchange(a, j, j - h)
47			else:
48			break
49
50
51			class MergeSort(object):
52			CUTOFF = 7
53
54			@staticmethod
55			def sort(a, lo=None, hi=None):
56			if lo is None:
57			lo = 0
58			if hi is None:
59			hi = len(a) - 1
60
61			aux = [0] * len(a)
62			MergeSort._sort(a, aux, lo, hi)
63
64			@staticmethod
65			def _sort(a, aux, lo, hi):
66			if lo >= hi:
67			return
68
69			if hi - lo + 1 < MergeSort.CUTOFF:
70			InsertionSort.sort(a, lo, hi)
71			return
72
73			mid = lo + (hi - lo) // 2
74			MergeSort._sort(a, aux, lo, mid)
75			MergeSort._sort(a, aux, mid + 1, hi)
76			MergeSort._merge(a, aux, lo, mid, hi)
77
78			@staticmethod
79			def _merge(a, aux, lo, mid, hi):
80			i = lo
81			j = mid + 1
82
83			for k in range(lo, hi + 1):
84			aux[k] = a[k]
85
86			for k in range(lo, hi + 1):
87			if i > mid:
88			a[k] = aux[j]
89			j += 1
90			elif j > hi:
91			a[k] = aux[i]
92			i += 1
93			elif util.less(aux[i], aux[j]):
94			a[k] = aux[i]
95			i += 1
96			else:
97			a[k] = aux[j]
98			j += 1
99
100
101			class QuickSort(object):
102			CUTOFF = 7
103
104			@staticmethod
105			def sort(a, lo=None, hi=None):
106			if lo is None:
107			lo = 0
108			if hi is None:
109			hi = len(a) - 1
110
111			if lo >= hi:
112			return
113
114			if hi - lo + 1 < QuickSort.CUTOFF:
115			InsertionSort.sort(a, lo, hi)
116			return
117
118			j = QuickSort.partition(a, lo, hi)
119
120			QuickSort.sort(a, lo, j - 1)
121			QuickSort.sort(a, j + 1, hi)
122
123			@staticmethod
124			def partition(a, lo, hi):
125			i = lo
126			j = hi
127
128			while True:
129			while not util.less(a[lo], a[i]):
130			i += 1
131			if i >= hi:
132			break
133
134			while util.less(a[lo], a[j]):
135			j -= 1
136			if j <= lo:
137			break
138
139			if i >= j:
140			break
141
142			util.exchange(a, i, j)
143
144			util.exchange(a, lo, j)
145			return j
146
147
148			class ThreeWayQuickSort(object):
149			CUTOFF = 7
150
151			@staticmethod
152			def sort(a, lo=None, hi=None):
153			if lo is None:
154			lo = 0
155			if hi is None:
156			hi = len(a) - 1
157
158			if lo >= hi:
159			return
160
161			if hi - lo + 1 < ThreeWayQuickSort.CUTOFF:
162			InsertionSort.sort(a, lo, hi)
163			return
164
165			i = lo
166			lt = lo
167			gt = hi
168
169			while i <= gt:
170			if util.less(a[i], a[lo]):
171			util.exchange(a, i, lt)
172			i += 1
173			lt += 1
174			elif util.less(a[lo], a[i]):
175			util.exchange(a, i, gt)
176			gt -= 1
177			else:
178			i += 1
179
180			ThreeWayQuickSort.sort(a, lo, lt - 1)
181			ThreeWayQuickSort.sort(a, gt + 1, hi)
182
183
184			class HeapSort(object):
185			@staticmethod
186			def sort(a):
187			n = len(a)
188
189			print(a)
190			for k in range(n // 2, 0, -1):
191			HeapSort.sink(a, k, n)
192
193			while n > 1:
194			util.exchange(a, HeapSort.index(1), HeapSort.index(n))
195			n -= 1
196			HeapSort.sink(a, 1, n)
197
198			@staticmethod
199			def sink(a, k, n):
200			while k * 2 <= n:
201			child = 2 * k
202			if child < n and util.greater(a[HeapSort.index(child+1)], a[HeapSort.index(child)]):
203			child = child + 1
204			if util.greater(a[HeapSort.index(child)], a[HeapSort.index(k)]):
205			util.exchange(a, HeapSort.index(child), HeapSort.index(k))
206			k = child
207			else:
208			break
209
210			@staticmethod
211			def index(k):
212			return k-1
213

chen0040 / pyalgs

QuickSort.partition() C last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

QuickSort.partition() C
last analyzed 2017-05-26 05:56 UTC