-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.py
129 lines (102 loc) · 3.34 KB
/
sort.py
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
def mergesort(seq, in_place=True):
"""Sorts `seq` using the mergesort algorithm.
`seq` is the sequence to be sorted. If `in_place` is `True`
the sequence itself will be sorted and returned, else a copy
of the original sequence is used.
"""
seq = seq if in_place else seq[:]
_mergesort(seq, 0, len(seq) - 1)
return seq
def straight_mergesort(seq, in_place=True):
"""Sorts `seq` using the straight-mergesort algorithm.
`seq` is the sequence to be sorted. If `in_place` is `True`
the sequence itself will be sorted and returned, else a copy
of the original sequence is used.
"""
seq = seq if in_place else seq[:]
size, length = 1, len(seq)
while size <= length:
right = -1
while right + size < length:
left = right + 1
mid = left + size - 1
right = mid + size if mid + size < length else length - 1
_merge(seq, left, mid, right)
size *= 2
return seq
def _mergesort(seq, left, right):
if left >= right:
return
mid = (left + right) // 2
_mergesort(seq, left, mid)
_mergesort(seq, mid + 1, right)
_merge(seq, left, mid, right)
def _merge(seq, left, mid, right):
result = []
i, j = left, mid + 1
while i <= mid and j <= right:
if seq[i] <= seq[j]:
result.append(seq[i])
i += 1
else:
result.append(seq[j])
j += 1
if i > mid:
result += seq[j:right + 1]
else:
result += seq[i:mid + 1]
seq[left:right + 1] = result
def quicksort(seq, in_place=True):
"""Sorts `seq` using the quicksort algorithm.
`seq` is the sequence to be sorted. If `in_place` is `True`
the sequence itself will be sorted and returned, else a copy
of the original sequence is used.
This variant uses recursive calls.
"""
seq = seq if in_place else seq[:]
_quicksort(seq, 0, len(seq) - 1)
return seq
def _quicksort(seq, left, right):
if left >= right:
return
pivot = seq[right]
i, j = left, right
while True:
while seq[i] <= pivot and i < right:
i += 1
while seq[j] >= pivot and j > i:
j -= 1
if i >= j:
break
_swap(seq, i, j)
_swap(seq, i, right)
_quicksort(seq, left, i - 1)
_quicksort(seq, i + 1, right)
def sortquick(seq):
if not seq:
return seq
pivot = seq[0]
bigger = sortquick([x for x in seq[1:] if x > pivot])
smaller = sortquick([x for x in seq[1:] if x <= pivot])
return smaller + [pivot] + bigger
def bubblesort(seq, in_place=True):
"""Sorts `seq` using the bubblesort algorithm.
`seq` is the sequence to be sorted. If `in_place` is `True`
the sequence itself will be sorted and returned, else a copy
of the original sequence is used.
The bubblesort algorithm walks through the sequence to be sorted
and swaps any two subsequent elements which do not obey the sort
order.
"""
seq = seq if in_place else seq[:]
for n in range(len(seq), 1, -1):
swapped = False
for i in range(n - 1):
if seq[i] > seq[i + 1]:
_swap(seq, i, i + 1)
swapped = True
if not swapped:
break
return seq
def _swap(seq, first, second):
seq[first], seq[second] = seq[second], seq[first]