@GarethDwyer1/

# quicksort

## No description

Files
• main.py
main.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
```
```def partition(xs, start, end):
follower = leader = start
while leader < end:
if xs[leader] <= xs[end]:
xs[follower], xs[leader] = xs[leader], xs[follower]
follower += 1
leader += 1
xs[follower], xs[end] = xs[end], xs[follower]
return follower

def _quicksort(xs, start, end):
if start >= end:
return
p = partition(xs, start, end)
_quicksort(xs, start, p-1)
_quicksort(xs, p+1, end)

def quicksort(xs):
_quicksort(xs, 0, len(xs)-1)

from datetime import datetime
import random

# create 100000 random numbers between 1 and 1000
xs = [random.randrange(1000) for _ in range(100000)]

# look at the first few and last few
print(xs[:10], xs[-10:])

# start the clock
t1 = datetime.now()
quicksort(xs)
t2 = datetime.now()
print("Sorted list of size {} in {}".format(len(xs), t2 - t1))

# have a look at the results
print(xs[:10], xs[-10:])

```
Fetching token