07: sorting #2 & kth min

Quicksort | Kth Min | Introsort | Radix Sort | Counting Sort | External Sorting | C++ Sorting

Quick Sort

Quick Sort maintains the invariant that items in a left hand side of a partition are less than a key and items in the right hand side are greater.
  1. Start:
    QuickSort
  2. Move the largest element to the back. Swap the first and middle element and make the first the bound
    QuickSort
  3. Setup the lower and upper fingers
    QuickSort
  4. Advance lower finger until bound is less than data[lower]
    QuickSort
  5. Advance upper finger until data[upper] is greater than bound
    QuickSort
  6. If lower < upper swap at fingers and advance fingers
    QuickSort
  7. If lower < upper swap at fingers and advance fingers
    QuickSort
  8. Lower is equal to upper, so increment lower and break out of the while loop
    QuickSort
  9. Exchange upper and first. 6 here is in it's final sorted position. Also, 12 is in the final sorted position.
    QuickSort
  10. Recursively call quicksort
    QuickSort
  11. Lhs: advance upper
    QuickSort
  12. Lhs: Swap at fingers and advance pointers
    QuickSort
  13. Lhs: Lower is equal to upper, so increment lower and break out of the while loop
    QuickSort
  14. Lhs: Exchange upper and first. 4 here is in it's final sorted position. Also, we are done
    QuickSort
  15. Final Result
    QuickSort

Complexity

  • Worst Case Time Complexity: O(n^2). When does this happen?
  • Average Time Complexity: O(nlg(n)). When does this happen?
  • Quick Sort is often faster in practice than other O(nlg(n)) algorithms and works well with the cache [2]
  • This in place version uses O(1) additional storage

Implementation Issues

  • We move the largest element to the back, because if we didn't, the first inner while loop would need to be:
    while(lower < last && data[lower] < bound) {
    This is needed if the bound is the largest element of the array. The lower < last comparison is for a rarely occuring case.

  • Selecting a pivot value
    • In the first versions of Quick Sort the first element was chosen. This is a bad choice for already sorted arrays
    • The middle value (given code) gives an O(nlg(n)) complexity for sorted arrays
    • Some implementations take the average of the first, middle and last and choose that as the pivot
    • A pivot can also be randomly chosen
  • Sorting small sub-arrays
    • It has been suggested that for sub-arrays of size smaller than 30, insertion sort should be used [3]
    • Insertion sort has O(n) time complexity for sorted arrays.

K-th Min

K-th Min or the Selection Problem is to find the K-th largest value in an array

A naive implementation can sort the array in O(nlg(n)) time and pick the value at the kth index. This is useful if you need to select many values.

Another implementation sorts the begining of the array until k is met. This takes O(kn) time.
1:  
// selection1.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
exch(
std:
:
vector<
int
>
&
 
data, 
int
 
index1, 
int
 
index2)
{

7:  
 
 
int
 
lhs 
=
 
data[
index1]
;

8:  
 
 
int
 
rhs 
=
 
data[
index2]
;

9:  
 
 
data[
index1]
 
=
 
rhs;

10: 
 
 
data[
index2]
 
=
 
lhs;

11: 
}

12: 

13: 
int
 
select(
std:
:
vector<
int
>
&
 
data, 
int
 
k)
{

14: 
 
 
for
(
int
 
=
 
0;
 
<
=
 
k;
 
++i)
{

15: 
 
 
 
 
int
 
min_index 
=
 
i;

16: 
 
 
 
 
int
 
min_value 
=
 
data[
i]
;

17: 
 
 
 
 
for
(
int
 
=
 
1;
 
<
 
data.size(
)
;
 
++j)
{

18: 
 
 
 
 
 
 
if
(
data[
j]
 
<
 
min_value)
{

19: 
 
 
 
 
 
 
 
 
min_index 
=
 
j;

20: 
 
 
 
 
 
 
 
 
min_value 
=
 
data[
j]
;

21: 
 
 
 
 
 
 
}

22: 
 
 
 
 
}

23: 
 
 
 
 
exch(
data, 
i, 
min_index)
;
 
 
 
 

24: 
 
 
}

25: 
 
 
return
 
data[
k]
;

26: 
}

27: 

28: 
int
 
main(
int
 
argc, 
char
 
*argv[
]
)
{

29: 
 
 

30: 
 
 
std:
:
vector<
int
>
 
data;

31: 
 
 
data.push_back(
20)
;

32: 
 
 
data.push_back(
5)
;

33: 
 
 
data.push_back(
10)
;

34: 
 
 
data.push_back(
6)
;

35: 
 
 
std:
:
cout 
<
<
 
"1st min: "
 
<
<
 
select(
data, 
1)
 
<
<
 
std:
:
endl;

36: 
 
 
//prints: 1st min: 6

37: 

38: 
 
 
return
 
0;

39: 
}

A select based on the quicksort partitioning takes O(n) time if a good pivot is chosen each time. Otherwise it can be O(n^2)
1:  
// selection2.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
exch(
std:
:
vector<
int
>
&
 
data, 
int
 
index1, 
int
 
index2)
{

7:  
 
 
int
 
lhs 
=
 
data[
index1]
;

8:  
 
 
int
 
rhs 
=
 
data[
index2]
;

9:  
 
 
data[
index1]
 
=
 
rhs;

10: 
 
 
data[
index2]
 
=
 
lhs;

11: 
}

12: 

13: 
int
 
partition(
std:
:
vector<
int
>
&
 
data, 
int
 
left, 
int
 
right, 
int
 
pivot_index)
{

14: 
 
 
int
 
bound 
=
 
data[
pivot_index]
;

15: 
 
 
exch(
data, 
pivot_index, 
right)
;

16: 
 
 
int
 
store_index 
=
 
left;

17: 
 
 
for
(
int
 
=
 
left;
 
<
=
 
right;
 
++i)
{

18: 
 
 
 
 
if
(
data[
i]
 
<
 
bound 
&
&
 
store_index 
!=
 
i)
{

19: 
 
 
 
 
 
 
exch(
data, 
store_index, 
i)
;

20: 
 
 
 
 
 
 
store_index++;

21: 
 
 
 
 
}

22: 
 
 
}

23: 
 
 
exch(
data, 
right, 
store_index)
;

24: 
 
 
return
 
store_index;

25: 
}

26: 

27: 
int
 
select(
std:
:
vector<
int
>
&
 
data, 
int
 
left, 
int
 
right, 
int
 
k)
{

28: 
 
 
if
(
left 
=
=
 
right)
{

29: 
 
 
 
 
//if the list contains only one element, return it.

30: 
 
 
 
 
return
 
data[
left]
;

31: 
 
 
}

32: 
 
 
//select pivot index between left and right

33: 
 
 
int
 
pivot_index 
=
 
(
left 
right)
 
2;

34: 
 
 
int
 
pivot_new_index 
=
 
partition(
data, 
left, 
right, 
pivot_index)
;

35: 
 
 
int
 
pivot_dist 
=
 
pivot_new_index 
left;

36: 
 
 
//the pivot is in its final sorted position, so pivot_dist reflects its 1-based position if data were sorted

37: 
 
 
if
(
pivot_dist 
=
=
 
k)
{

38: 
 
 
 
 
return
 
data[
pivot_new_index]
;

39: 
 
 
}
 
else
 
if
(
<
 
pivot_dist)
{

40: 
 
 
 
 
return
 
select(
data, 
left, 
pivot_new_index 
1, 
k)
;

41: 
 
 
}
 
else
 
{

42: 
 
 
 
 
return
 
select(
data, 
pivot_new_index 
1, 
right, 
pivot_dist 
1;

43: 
 
 
}

44: 
}

45: 

46: 
int
 
main(
int
 
argc, 
char
 
*argv[
]
)
{

47: 

48: 
 
 
std:
:
vector<
int
>
 
data;

49: 
 
 
data.push_back(
20)
;

50: 
 
 
data.push_back(
5)
;

51: 
 
 
data.push_back(
10)
;

52: 
 
 
data.push_back(
6)
;

53: 
 
 
data.push_back(
7)
;

54: 
 
 
data.push_back(
8)
;

55: 
 
 
data.push_back(
20)
;

56: 
 
 
data.push_back(
30)
;

57: 
 
 
data.push_back(
40)
;

58: 
 
 
std:
:
cout 
<
<
 
"6th min: "
 
<
<
 
select(
data, 
0, 
data.size(
)
 
1, 
6)
 
<
<
 
std:
:
endl;

59: 
 
 
//prints: 6th min: 20

60: 

61: 
 
 
return
 
0;

62: 
}

63: 

  1. Start. Looking for k=6:
    Selection
  2. Partition: select bound and exchange
    Selection
  3. At i = 2, data[i] < bound. exch 0 and 2.
    Selection
  4. At i = 4, data[i] < bound. exch 1 and 4.
    Selection
  5. At i = 5, data[i] < bound. exch 2 and 5.
    Selection
  6. At i = 7, data[i] < bound. exch 3 and 7.
    Selection
  7. Place the pivot into its final place. Now we are looking for k = 0 on the right side.
    Selection
  8. Pick 9 as the median element.
    Selection
  9. Exchange 0 and 2.
    Selection
  10. Recurse on the left side. Now looking for k = 0.
    Selection

Linear Time Selection: Choosing a good pivot

The median of median's algorithm guarentees good pivots are chosen giving an O(n) worst case time complexity.
  • Divide the sub-array into smaller sub-arrays with 5 elements each
  • Choose the median of each sub-array
  • Choose the median of all the medians

Introsort

Introsort uses quicksort and when the recursive depth reaches lgn, it does an inplace heapsort.
  • Start:
    Introsort
  • level 1: (Pivot = 5)
    Introsort
  • level 2: (Pivot = 8)
    Introsort
  • level 3: (Pivot = 10)
    Introsort
  • in-place heapsort:
    Introsort
  • done:
    Introsort

Radix Sort

Radix Sort uses the digits in numbers to form a sorting algorithm.
  • Using the digits left to right (most significant digit, MSD) is good for lexiographic sorting of words
  • Using the digits right to left (least significant digit, LSD) is good for sorting numbers
Pseudo-code:
1: 
// radixSortPseudo.cpp - download here

2: 

3: 
radixSort(
)
{

4: 
 
 
for
(
 
=
 
to 
the 
position 
of 
the 
leftmost 
digit 
of 
longest 
number)
{

5: 
 
 
 
 
1. 
distribute 
all 
numbers 
into 
piles 
through 
according 
to 
digit

6: 
 
 
 
 
2. 
put 
all 
the 
integers 
in 
one 
list

7: 
 
 
}

8: 
}

Sorting the numbers [93 63 64 94] with a stack
  • pile 3: 63 93
  • pile 4: 94 64
Combine piles: [63 93 94 64]. Sort according to leftmost digit
  • pile 6: 64 63
  • pile 9: 94 93
Combine piles: [64 63 94 93]

If we used a queue instead of a stack it would be in sorted order.
1:  
// radixSort.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  
#include
 
<
queue>

6:  

7:  
void
 
radixSort(
std:
:
vector<
long
>
&
 
data)
{

8:  
 
 
const
 
int
 
radix 
=
 
10;

9:  
 
 
const
 
int
 
digits 
=
 
10;
 
 
//(max number of digits for a long)

10: 
 
 
std:
:
queue<
long
>
 
queues[
radix]
;

11: 
 
 
for
(
int
 
=
 
0, 
factor 
=
 
1;
 
<
 
digits;
 
factor 
*=
 
radix, 
++i)
{

12: 
 
 
 
 
//fill up the queues

13: 
 
 
 
 
for
(
int
 
=
 
0;
 
<
 
data.size(
)
;
 
++j)
{

14: 
 
 
 
 
 
 
queues[
(
data[
j]
 
factor)
 
radix]
.push(
data[
j]
)
;

15: 
 
 
 
 
}

16: 
 
 
 
 
//empty the queues 

17: 
 
 
 
 
int
 
=
 
0;

18: 
 
 
 
 
for
(
int
 
=
 
0;
 
<
 
radix;
 
++j)
{

19: 
 
 
 
 
 
 
while
(
!queues[
j]
.empty(
)
)
{

20: 
 
 
 
 
 
 
 
 
data[
k]
 
=
 
queues[
j]
.front(
)
;

21: 
 
 
 
 
 
 
 
 
queues[
j]
.pop(
)
;

22: 
 
 
 
 
 
 
 
 
++k;

23: 
 
 
 
 
 
 
}

24: 
 
 
 
 
}

25: 
 
 
}

26: 
}

27: 

28: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

29: 

30: 
 
 
std:
:
vector<
long
>
 
array;

31: 
 
 
array.push_back(
10)
;

32: 
 
 
array.push_back(
5)
;

33: 
 
 
array.push_back(
15)
;

34: 
 
 
array.push_back(
7)
;

35: 
 
 
array.push_back(
1)
;

36: 
 
 
array.push_back(
6)
;

37: 
 
 
array.push_back(
8)
;

38: 
 
 
array.push_back(
3)
;

39: 
 
 
array.push_back(
2)
;

40: 
 
 
array.push_back(
4)
;

41: 
 
 
array.push_back(
16)
;

42: 
 
 
array.push_back(
12)
;

43: 
 
 
array.push_back(
13)
;

44: 
 
 
array.push_back(
11)
;

45: 
 
 
array.push_back(
9)
;

46: 
 
 
array.push_back(
14)
;

47: 
 
 
array.push_back(
17)
;

48: 

49: 
 
 
radixSort(
array)
;

50: 

51: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
array.size(
)
;
 
++i)
{

52: 
 
 
 
 
std:
:
cout 
<
<
 
array[
i]
 
<
<
 
" "
;

53: 
 
 
}

54: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

55: 
 
 
//prints: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

56: 

57: 
 
 
return
 
0;

58: 
}

Sort with least significant digit
  • pile 0: 10
  • pile 1: 1 11
  • pile 2: 2 12
  • pile 3: 3 13
  • pile 4: 4 14
  • pile 5: 5 15
  • pile 6: 6 16
  • pile 7: 7 17
  • pile 8: 8
  • pile 9: 9
Combine piles: [10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 9]
Sort with next digit
  • pile 0: 01 02 03 04 05 06 07 08 09
  • pile 1: 10 11 12 13 14 15 16 17
  • pile 2:
  • pile 3:
  • pile 4:
  • pile 5:
  • pile 6:
  • pile 7:
  • pile 8:
  • pile 9:
Combine piles: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17]

Radix Sort Notes

  • Worst Case Time Complexity: O(kn) where k is number of digits at a radix
  • Worst Case Space Complexity: O(kn) where k is number of digits at a radix
  • It may be complicated to use radix sort when the sort criteria is formed with two or more comparisons since it is not a comparison sort.

Counting Sort

Counting Sort can sort a small range of integers in linear time. The maximum value of integer to be sorted must be known. It can be used as a subroutine in radix sort
1:  
// countingSort.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
countingSort(
std:
:
vector<
int
>
&
 
data)
{

7:  
 
 
const
 
int
 
max_value 
=
 
10;

8:  
 
 
int
 
counts[
max_value]
;

9:  

10: 
 
 
//clear counts

11: 
 
 
for
(
int
 
=
 
0;
 
<
 
max_value;
 
++i)
{

12: 
 
 
 
 
counts[
i]
 
=
 
0;

13: 
 
 
}

14: 

15: 
 
 
//calculate count of each number

16: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
data.size(
)
;
 
++i)
{

17: 
 
 
 
 
++counts[
data[
i]
]
;

18: 
 
 
}

19: 

20: 
 
 
//write back to the array

21: 
 
 
data.clear(
)
;

22: 
 
 
for
(
int
 
=
 
0;
 
<
 
max_value;
 
++i)
{

23: 
 
 
 
 
int
 
=
 
counts[
i]
;

24: 
 
 
 
 
for
(
int
 
=
 
0;
 
<
 
c;
 
++j)
{

25: 
 
 
 
 
 
 
data.push_back(
i)
;

26: 
 
 
 
 
}
 

27: 
 
 
}

28: 
}

29: 

30: 
int
 
main(
int
 
argc, 
char
 
*argv[
]
)
{

31: 

32: 
 
 
std:
:
vector<
int
>
 
data;

33: 
 
 
data.push_back(
0)
;

34: 
 
 
data.push_back(
5)
;

35: 
 
 
data.push_back(
5)
;

36: 
 
 
data.push_back(
4)
;

37: 
 
 
data.push_back(
4)
;

38: 
 
 
data.push_back(
2)
;

39: 
 
 
data.push_back(
1)
;

40: 

41: 
 
 
countingSort(
data)
;

42: 
 
 

43: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
data.size(
)
;
 
++i)
{

44: 
 
 
 
 
std:
:
cout 
<
<
 
data[
i]
 
<
<
 
" "
;

45: 
 
 
}

46: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

47: 
 
 
//prints: 0 1 2 4 4 5 5

48: 
 
 
return
 
0;

49: 
}

Stable Sorts

A Stable Sort is a sorting algorithm that doesn't change the order of elements whose keys are equal

Out of the sorting algorithms we are covering, these are stable [7]. Composite sorts can be done with radix sort by first sorting with key1 then sorting with key2.
  • Bubble Sort
  • Insertion Sort
  • Merge Sort
  • Counting Sort
  • Radix Sort
  • Odd-Even Sort (at the end of the semester)
These are not stable
  • Selection Sort
  • Shell Sort
  • Heap Sort
  • Smooth Sort
  • Quick Sort

Index and Pointer Sorting

If you are sorting large items, it is probably a good idea to first sort indexes or pointers. Then after if you need the objects in a sorted order, you can do the whole move at once (requiring O(n) moves rather than O(n*lg(n)).

External Sorting [7]

External Sorting is when a file is too large to fit into ram.

Two basic primitive operations:
  • Read data from disk to ram
  • Write data from ram to disk
In this style of sorting, the cost of these two is much larger than sorting individual blocks and we ignore the sorting time completely.

Restrictions on algorithm:
  • Read/writes from/to disk must be done in large blocks
  • Some storage devices operate at peak performance when read sequentially (like tape drives)
External sorting algorithms use mutliple storage devices and the time complexity is characterized by the number of passes over the data.

Assumptions:
  • N records to be sorted, on one external device
  • space in ram to hold M records
  • 2P external devices available
Labels:
  • Label 0: input device
  • Labels 1 to 2P - 1: other devices
The goal is to put records back to device 0 in sorted order

Balanced Multiway Merging

  • A sort-merge approach
Distribution pass:
  • Distribute input among devices P to 2P-1 in sorted blocks of M records
  • Use modulus distribution if there are more blocks than than P. (place block 0 on device P and block P on device P...)
Multiway merging passes:
  • Devices P to 2P-1 are input devices
  • Devices 0 to P-1 are output devices
P-way merging is done to merge sorted blocks of size M on input devices into sorted blocks of size PM on output devices
  • Modulus distribution is used again
We repeat this until there is one sorted block remaining on device 0.

Example:
A S O R T I N G A N D M E R G I N G E X A M P L E W I T H F O R T Y F I V E R E C O R D S
 
A O S D M N A E X F H T E R V
I R T E G R L M P O R T C E O
A G N G I N E I W F I Y D R S
 
A A G I N O R S T F F H I O R T T Y
D E G G I M N N R C D E E O R R S V
A E E I L M P W X  
 
A A A D E E E G G G I I I L M M N N N O P R R S T W X
C D E E F F H I O O R R R S T T V Y
 
A A A C D D E E E E E F F G G G H I I I I L M M N N N O O O P R R R R R S S T T T V W X Y
Using a priority queue of size P we can do the P-way merging in time M*P*lg(P). (A pointer to the index used in mergesort merge is kept with the item placed in the priority queue. The priority queue never has more than P elements in it.)

  • With 2P tapes and M sized ram, balanced multiway merging takes 1 + ceil(log_P(N/M)) passes.
Here P, N and M are:
  • P = 3 (num tapes divided by two. each pass has 3 input tapes and 3 output tapes)
  • N = 45 (num items)
  • M = 3 (memory size)
log_P (or log_3) means how many times to divide N/M by 3 until you get to one.
  • N/M = 15, you can see that there are 15 groups to merge to start out with
  • Then groups of 3 are merged together using 3 tapes and you get 15 / 3 = 5
  • 5 is the number of groups that are input to the next pass

Replacement Selection [7][8]

Replacement selection has the same effect as increasing the amount of internal memory. It is an optimization of the first sorting step of the previous algorithm

A priority queue of size M is used.
  • Initialization step: M records are read into the priority queue (using, say, a min-heap)
  • Replacement step: (creates a single run)
    • Remove the smallest element from the priority queue and write out
    • Read an element from the input tape. If the read element is smaller than the last output element, mark it as greater than all elements in the priority queue.
    • Stop a run when a marked element reaches the top of the queue
Example sorting 2M elements with M = 5:
Sequence: [0 18 14 17 19 8 13 6 4 23 0 12 15 11 4]
Result: [0 8 13 14 17 18 19 23] and [0 4 4 6 11 12 15]
ReplacementSelection
ReplacementSelection
ReplacementSelection

  • For random files and P=2, one merging pass is saved
  • For sorted files (or no key has more than M larger keys before in the file), no merging will be necessary

C++ Sorting

1:  
// stl_sorting.cpp - download here

2:  

3:  
#include
 
<
algorithm
>

4:  
#include
 
<
vector>

5:  
#include
 
<
iostream>

6:  

7:  
bool
 
forward(
int
 
lhs, 
int
 
rhs)
{

8:  
 
 
if
(
lhs 
<
 
rhs)
{

9:  
 
 
 
 
return
 
true;

10: 
 
 
}

11: 
 
 
return
 
false;

12: 
}

13: 

14: 
bool
 
reverse(
int
 
lhs, 
int
 
rhs)
{

15: 
 
 
if
(
rhs 
<
 
lhs)
{

16: 
 
 
 
 
return
 
true;

17: 
 
 
}

18: 
 
 
return
 
false;

19: 
}

20: 

21: 
bool
 
even(
int
 
lhs, 
int
 
rhs)
{

22: 
 
 
if
(
lhs 
=
=
 
&
&
 
rhs 
=
=
 
0)
{

23: 
 
 
 
 
return
 
true;

24: 
 
 
}

25: 
 
 
return
 
false;

26: 
}

27: 

28: 
void
 
print(
std:
:
vector<
int
>
&
 
numbers, 
const
 
char
 
label)
{

29: 
 
 
std:
:
cout 
<
<
 
label 
<
<
 
": ["
;

30: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
numbers.size(
)
;
 
++i)
{

31: 
 
 
 
 
std:
:
cout 
<
<
 
numbers[
i]
;

32: 
 
 
 
 
if
(
<
 
numbers.size(
)
 
1)
{

33: 
 
 
 
 
 
 
std:
:
cout 
<
<
 
","
;

34: 
 
 
 
 
}

35: 
 
 
}

36: 
 
 
std:
:
cout 
<
<
 
"]"
 
<
<
 
std:
:
endl;

37: 
}

38: 

39: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

40: 
 
 
std:
:
vector<
int
>
 
numbers;

41: 
 
 
numbers.push_back(
10)
;

42: 
 
 
numbers.push_back(
20)
;

43: 
 
 
numbers.push_back(
0)
;

44: 
 
 
numbers.push_back(
15)
;

45: 
 
 
numbers.push_back(
9)
;

46: 

47: 
 
 
std:
:
sort(
numbers.begin(
)
numbers.end(
)
forward)
;

48: 
 
 
print(
numbers, 
"forward"
)
;

49: 
 
 
std:
:
sort(
numbers.begin(
)
numbers.end(
)
reverse)
;

50: 
 
 
print(
numbers, 
"reverse"
)
;

51: 
 
 
std:
:
sort(
numbers.begin(
)
numbers.end(
)
even)
;

52: 
 
 
print(
numbers, 
"evenodd"
)
;

53: 

54: 
 
 
return
 
0;

55: 
}

results:
forward: [0,9,10,15,20]
reverse: [20,15,10,9,0]
evenodd: [0,10,20,15,9]