Sort
~5 mins read
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quick_sort(data):
# base case
if len(data) < 2:
return data
# recursion
else:
less = list()
greater = list()
equal = list()
pivot = data[int(len(data)/2)]
for i in data:
if i < pivot:
less.append(i)
elif i == pivot:
equal.append(i)
else:
greater.append(i)
return quick_sort(less) + equal + quick_sort(greater)
if __name__ == "__main__":
print(quick_sort([9, 7, 5, 4, 6, 8, 12, 1, 26, 1, 1]))
1
2
3
4
5
6
7
8
9
def selection_sort(data):
sorted_list = list()
for i in range(len(data)):
smallest_index = data.index(min(data))
sorted_list.append(data.pop(smallest_index))
return sorted_list
if __name__ == "__main__":
print(selection_sort([9, 7, 5, 4, 6, 8, 12, 1, 26, 1, 1]))
1
2
3
4
5
6
7
8
9
10
11
function findUnsortedSubarray(nums){
return nums.slice()
.sort((a, b) => a - b)
.reduce((acc, curr, idx) => acc + (curr === nums[idx] ? ' ' : 'x'), '')
.trim().length;
}
let ans = findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15])
console.log(ans)
// answer is 5
// it's enough to sort [6, 4, 8, 10, 9] to make all sorted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findUnsortedSubarray(nums) -> int:
is_same = [a == b for a, b in zip(nums, sorted(nums))]
if all(is_same):
return 0
else:
first_index = is_same.index(False)
last_index = len(nums) - is_same[::-1].index(False)
return last_index - first_index
"""
[2, 6, 4, 8, 10, 9, 15]
[t,f,... f,t]
0,1, .. 5,6
false starts at index 1, ends at 5
"""
assert findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]) == 5
1
2
3
4
5
6
7
8
9
10
11
12
from heapq import heappush, heappop
def heapsort(iterable):
h = []
for val in iterable:
heappush(h, val)
# or just h = heapify(iterable)
return [heappop(h) for i in range(len(h))]
assert heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]