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
|
Given sequence 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, sort the sequence using the
following algorithms, and illustrate the details of the execution of the
algorithms:
a. merge-sort algorithm.
```plaintext
[3,1,4,1,5,9,2,6,5,3,5,]
[3,1,4,1,5,9,]
[3,1,4,]
[3,1,]
[3,]
[3,1,]
[1,3,4,]
[1,3,4,1,5,9,]
[1,3,4,1,5,]
[1,3,4,1,]
[1,3,4,1,5,]
[1,3,4,1,5,9,]
[1,1,3,4,5,9,2,6,5,3,5,]
[1,1,3,4,5,9,2,6,5,]
[1,1,3,4,5,9,2,6,]
[1,1,3,4,5,9,2,]
[1,1,3,4,5,9,2,6,]
[1,1,3,4,5,9,2,6,5,]
[1,1,3,4,5,9,2,5,6,3,5,]
[1,1,3,4,5,9,2,5,6,3,]
[1,1,3,4,5,9,2,5,6,3,5,]
```
b. quick-sort algorithm.
* Choose a partitioning strategy you like to pick a pivot element from the sequence.
* Analyze how different portioning strategies may impact on the performance of the sorting algorithm.
For choosing a pivot I chose to use the value in the last element of the sequence.
Alternative, strategies include choosing a random pivot in each sub-sequence.
Using the last item in the sub-sequence as the pivot:
```plaintext
[3,1,4,1,5,9,2,6,5,3,]
[3,1,4,1,2,]
[1,1,]
[1,]
[]
[1,]
[1,1,]
[1,1,2,3,4,]
[1,1,2,]
[1,1,2,3,3,]
[1,1,2,3,3,4,5,6,5,9,]
[1,1,2,3,3,4,]
[1,1,2,3,3,4,5,5,5,9,]
[1,1,2,3,3,4,5,5,]
[1,1,2,3,3,4,5,5,5,6,]
```
|
