Sorting Algorithms in Data Structures
undefined
W
e
l
c
o
m
e
t
o
C
S
2
3
5
D
a
t
a
S
t
r
u
c
t
u
r
e
s
S
o
r
t
i
n
g
(
3
4
)
C
h
a
p
t
e
r
1
0
.
1
-
3
,
p
g
s
.
5
5
5
-
5
6
4
A
t
t
e
n
d
a
n
c
e
Q
u
i
z
#
3
3
Sort (34)
2
T
i
p
#
3
4
:
N
o
n
-
c
o
m
p
i
l
e
r
P
e
r
f
o
r
m
a
n
c
e
1.
D
o
n
'
t
d
e
f
i
n
e
o
b
j
e
c
t
v
a
r
i
a
b
l
e
s
b
e
f
o
r
e
t
h
e
i
r
u
s
e
/
i
n
i
t
i
a
l
i
z
a
t
i
o
n
,
w
h
i
c
h
n
e
c
e
s
s
i
t
a
t
e
s
t
h
a
t
t
h
e
c
o
n
s
t
r
u
c
t
o
r
A
N
D
a
s
s
i
g
n
m
e
n
t
o
p
e
r
a
t
o
r
f
u
n
c
t
i
o
n
s
w
i
l
l
r
u
n
–
c
o
u
l
d
b
e
c
o
s
t
l
y
f
o
r
c
o
m
p
l
e
x
o
b
j
e
c
t
s
.
2.
C
o
n
s
i
d
e
r
t
h
e
o
r
d
e
r
o
f
e
v
a
l
u
a
t
i
o
n
o
f
c
o
m
p
o
u
n
d
c
o
n
d
i
t
i
o
n
a
l
s
.
e
.
g
.
,
g
i
v
e
n
i
f
(
a
&
&
b
)
,
i
f
b
i
s
m
o
r
e
l
i
k
e
l
y
t
o
b
e
f
a
l
s
e
,
p
l
a
c
e
i
t
f
i
r
s
t
t
o
s
a
v
e
t
h
e
e
v
a
l
u
a
t
i
o
n
o
f
a
.
3.
M
i
n
i
m
i
z
e
t
h
e
u
s
e
o
f
t
e
m
p
o
r
a
r
i
e
s
(
p
a
r
t
i
c
u
l
a
r
l
y
w
i
t
h
s
t
r
i
n
g
-
b
a
s
e
d
p
r
o
c
e
s
s
i
n
g
)
.
4.
U
s
e
h
e
a
p
m
e
m
o
r
y
(
d
y
n
a
m
i
c
a
l
l
o
c
a
t
i
o
n
)
o
n
l
y
w
h
e
n
n
e
c
e
s
s
a
r
y
a
s
d
y
n
a
m
i
c
a
l
l
o
c
a
t
i
o
n
s
a
n
d
d
e
a
l
l
o
c
a
t
i
o
n
s
a
r
e
e
x
p
e
n
s
i
v
e
.
(
M
a
n
y
C
+
+
p
r
o
g
r
a
m
m
e
r
s
o
v
e
r
-
u
s
e
t
h
e
h
e
a
p
.
)
5.
K
n
o
w
y
o
u
r
c
o
m
p
i
l
e
r
/
l
i
n
k
e
r
o
p
t
i
o
n
s
,
e
s
p
e
c
i
a
l
l
y
w
h
i
c
h
o
n
e
s
c
a
u
s
e
n
o
n
-
s
t
a
n
d
a
r
d
b
e
h
a
v
i
o
r
.
T
h
e
s
e
d
r
a
m
a
t
i
c
a
l
l
y
a
f
f
e
c
t
r
u
n
t
i
m
e
p
e
r
f
o
r
m
a
n
c
e
.
6.
K
n
o
w
t
h
e
p
e
r
f
o
r
m
a
n
c
e
/
f
u
n
c
t
i
o
n
a
l
i
t
y
t
r
a
d
e
o
f
f
s
o
f
t
h
e
S
T
L
c
o
n
t
a
i
n
e
r
s
(
e
.
g
.
,
d
o
n
'
t
f
r
e
q
u
e
n
t
l
y
i
n
s
e
r
t
i
n
t
o
a
v
e
c
t
o
r
,
u
s
e
a
l
i
s
t
)
.
Sort (34)
3
L09 - Pokémon
4
A
s
s
o
c
i
a
t
i
v
e
S
e
t
/
M
a
p
I
m
p
l
e
m
e
n
t
a
t
i
o
n
s
Sort (34)
5
cat
dog
horse
pig
Unordered Hash Map (Chained)
Bucketed ordered list
unordered, unique (?)
(1
)
average search
Ordered Set (BST)
ordered, unique
(
log n)
search
cat
dog
horse
pig
Unordered Hash Map (Open addressing)
Linear or Quadratic probe
unordered, unique
(1
)
average search
Ordered Set (Linked List)
unordered, duplicates
push_front(item) -> addNode(item);
(
n)
search
P
o
k
é
m
o
n
M
a
p
s
a
n
d
S
e
t
s
Pokemon
:
Charmander fire
(1)
Bulbasaur grass
(1)
Squirtle water
(1)
HashMap<string,string> pokemon;
pair<string,string>
Effectivities
:
fire grass ice bug
(2)
water ground rock fire
(4)
grass water ground rock
(4)
Ineffectivities
:
fire fire water rock
(2)
water water grass
(4)
grass grass bug fire
(4)
Moves
:
flamethrower fire
(3)
water_gun water
(2)
razor_leaf grass
(2)
HashMap<string,string> moves;
HashMap<string,Set<string>> ineffectivities;
HashMap<string,Set<string>> effectivities;
pair<string,string>
pair<string,Set<string>>
Set<string>
pair<string,Set<string>>
Set<string>
Sort (34)
6
10.1, pgs. 570-572
10.1 Using C++ Sorting Functions
7
C
h
a
p
t
e
r
O
b
j
e
c
t
i
v
e
s
■
To learn how to use the standard sorting functions in algorithm.h.
■
To learn how to implement the following sorting algorithms:
■
selection sort
■
bubble sort
■
insertion sort
■
Shell sort
■
merge sort
■
heapsort
■
quicksort
■
To understand the difference in performance of these algorithms, and which to use
for small, medium, and large arrays.
■
Sorting entails arranging data in decreasing (or non-increasing) or increasing (or
non-decreasing) order
■
Familiarity with sorting algorithms is an important programming skill.
■
T
h
e
s
t
u
d
y
o
f
s
o
r
t
i
n
g
a
l
g
o
r
i
t
h
m
s
p
r
o
v
i
d
e
s
i
n
s
i
g
h
t
i
n
t
o
p
r
o
b
l
e
m
s
o
l
v
i
n
g
t
e
c
h
n
i
q
u
e
s
s
u
c
h
a
s
d
i
v
i
d
e
a
n
d
c
o
n
q
u
e
r
.
■
the analysis and comparison of algorithms which perform the same task.
Sort (34)
8
U
s
i
n
g
C
+
+
S
o
r
t
i
n
g
M
e
t
h
o
d
s
■
The Standard C++ Library (in algorithm.h) provides versions of sorting functions
using a pair of random-access iterators:
Sort (34)
9
template<typename RI>
void sort(RI first, RI last);
template<typename RI, typename Compare>
void sort(RI first, RI last, Compare comp);
■
Because these functions require random-access iterators, they can be used only
with vectors, deques, and ordinary C pointers (for sorting arrays).
■
Note: The
list
container supports only bidirectional iterators, so it provides its own sort
member function.
■
If we use the second version of function
sort
, we must also pass an object that
implements a comparison function (functor).
■
If
people_list
is a vector of
Person
objects, then:
sort(people_list.begin(), people_list.end(),
Compare_Person());
sorts the elements in
people_list
in ascending order based on their names.
The
Compare_Person
function class is used to compare objects:
Sort (34)
U
s
i
n
g
C
+
+
S
o
r
t
i
n
g
M
e
t
h
o
d
s
struct Compare_Person
{bool operator()(const Person& p1, const Person& p2)
{return ((p1.family_name < p2.family_name) ||
((p1.family_name == p2.family_name)
&& (p1.given_name < p2.given_name));
}
}
10
10
■
If array
items
stores a collection of 16 integers, the array is sorted by:
sort(items, items + 16);
■
This statement sorts only the first half of the array, leaving the rest
untouched:
sort(items, items + 8);
■
This function call sorts the array in descending order:
sort(items, items + 16, greater<int>());
where
greater<int>
implements the comparison
operator>
for integers
(defined in library
functional
).
Sort (34)
U
s
i
n
g
C
+
+
S
o
r
t
i
n
g
M
e
t
h
o
d
s
11
11
■
There are also two functions named
stable_sort
, which are similar to
the sort functions.
■
T
h
e
p
r
i
m
a
r
y
d
i
f
f
e
r
e
n
c
e
i
s
t
h
a
t
e
l
e
m
e
n
t
s
t
h
a
t
a
r
e
e
q
u
a
l
m
a
y
n
o
t
r
e
t
a
i
n
t
h
e
i
r
r
e
l
a
t
i
v
e
o
r
d
e
r
i
n
g
w
h
e
n
s
o
r
t
i
s
u
s
e
d
,
b
u
t
t
h
e
y
w
i
l
l
r
e
t
a
i
n
t
h
e
i
r
r
e
l
a
t
i
v
e
o
r
d
e
r
i
n
g
w
h
e
n
s
t
a
b
l
e
_
s
o
r
t
i
s
u
s
e
d
.
■
I
n
o
t
h
e
r
w
o
r
d
s
,
i
f
t
h
e
r
e
a
r
e
t
w
o
o
c
c
u
r
r
e
n
c
e
s
o
f
a
n
i
t
e
m
,
t
h
e
o
n
e
t
h
a
t
i
s
f
i
r
s
t
i
n
t
h
e
u
n
s
o
r
t
e
d
a
r
r
a
y
i
s
g
u
a
r
a
n
t
e
e
d
t
o
b
e
f
i
r
s
t
i
n
t
h
e
s
o
r
t
e
d
a
r
r
a
y
o
n
l
y
i
f
s
t
a
b
l
e
_
s
o
r
t
i
s
u
s
e
d
.
■
This function call sorts an array in descending order:
stable_sort(items, items + 16, greater<int>());
■
The
sort
function is slightly faster than
stable_sort
, so it should be
used whenever the relative ordering of equal elements is unimportant.
Sort (34)
U
s
i
n
g
C
+
+
S
o
r
t
i
n
g
M
e
t
h
o
d
s
12
12
10.2, pgs. 572-580
13
13
S
e
l
e
c
t
i
o
n
S
o
r
t
a
n
d
B
u
b
b
l
e
S
o
r
t
■
S
e
l
e
c
t
i
o
n
s
o
r
t
i
s
r
e
l
a
t
i
v
e
l
y
e
a
s
y
t
o
u
n
d
e
r
s
t
a
n
d
.
■
The array is sorted by making several passes through the array, selecting
a next smallest item in the array each time and placing it where it belongs
in the array.
■
B
u
b
b
l
e
s
o
r
t
(
a
l
s
o
k
n
o
w
n
a
s
s
i
n
k
i
n
g
s
o
r
t
)
i
s
a
l
s
o
a
s
i
m
p
l
e
s
o
r
t
i
n
g
a
l
g
o
r
i
t
h
m
■
The array is sorted by repeatedly stepping through the array, comparing
adjacent pairs, and swapping them if they are in the wrong order, until the
array is sorted.
■
Smaller values bubble up to the top of the array and larger values sink to
the bottom; hence the name.
■
S
e
l
e
c
t
i
o
n
s
o
r
t
a
n
d
B
u
b
b
l
e
s
o
r
t
a
r
e
q
u
a
d
r
a
t
i
c
s
o
r
t
s
.
Sort (34)
14
14
S
e
l
e
c
t
i
o
n
S
o
r
t
■
Selection sort is relatively easy to understand.
■
It sorts an array by making several passes through the array, exchanging
items if smaller.
■
For simplicity, we illustrate all the sorting algorithms using an array of integer
values.
Sort (34)
15
15
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
16
16
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
17
17
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
18
18
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
19
19
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
20
20
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
21
21
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
22
22
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
23
23
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
24
24
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
Sort (34)
25
25
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
26
26
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
27
27
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
Sort (34)
28
28
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
29
29
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
30
30
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
Sort (34)
31
31
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
32
32
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
33
33
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
34
34
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
35
35
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
36
36
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
37
37
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
38
38
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
39
39
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
40
40
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
41
41
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
Sort (34)
42
42
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
43
43
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
44
44
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
45
45
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
46
46
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
Sort (34)
47
47
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
48
48
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
49
49
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
50
50
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
T
r
a
c
e
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Sort (34)
51
51
1.
for fill = 0 to n – 2
2.
for next = fill + 1 to n – 1
3.
if item[next] < item[fill]
4.
e
xchange item[pos_min],item[fill]
5.
endfor
6.
endfor
A
r
r
a
y
i
s
s
o
r
t
e
d
!
S
o
r
t
t
h
e
f
o
l
l
o
w
i
n
g
i
n
t
e
g
e
r
a
r
r
a
y
i
n
a
s
c
e
n
d
i
n
g
o
r
d
e
r
u
s
i
n
g
s
e
l
e
c
t
i
o
n
s
o
r
t
.
S
h
o
w
e
a
c
h
s
t
e
p
.
How many exchanges?
This loop is
performed n-1 times
Sort (34)
53
53
A
n
a
l
y
s
i
s
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
There are n-1
exchanges
1.
for fill = 0 to n – 2
2.
pos_min = fill
3.
for next = fill + 1 to n – 1
4.
if item[next] < item[pos_min]
5.
pos_min = next
6.
endfor
7.
exchange item[pos_min],item[fill]
8.
endfor
This comparison is performed
(
n
– 1 -
fill
)
times for each value of
fill
and can
be represented by the following
series:
(
n
-1) + (
n
-2) + ... + 3 + 2 + 1
For very large
n
we can ignore all but the
significant term in the expression, so the
number of
•
comparisons is O(
n
2
)
•
exchanges is O(
n
)
A
n
O
(
n
2
)
s
o
r
t
i
s
c
a
l
l
e
d
a
q
u
a
d
r
a
t
i
c
s
o
r
t
Sort (34)
54
54
C
o
d
e
f
o
r
S
e
l
e
c
t
i
o
n
S
o
r
t
/** Sort data in the specified range using selection sort.
@param RI An iterator that meets the random-access iterator requirements
@param first Iterator that references the beginning of the sort sequence
@param last Iterator that references 1 past the end of the sort sequence
@param comp An object that implements a comparison function
*/
template<typename RI, typename Compare>
void selection_sort(RI first, RI last, Compare comp)
{for (RI fill = first; fill != last - 1; ++fill)
{// Invariant: Elements at positions first through fill - 1 are sorted.
RI pos_min = fill;
for (RI next = fill + 1; next != last; ++next)
{// Invariant: pos_min references the smallest item in
// positions fill through next - 1.
if (comp(*next, *pos_min)) pos_min = next;
}
// Assert: pos_min references the smallest item from fill through last - 1.
// If the next smallest item is not at fill, exchange *fill and *pos_min.
if (fill != pos_min) std::iter_swap(pos_min, fill);
}
return;
}
10.3, pgs. 577-580
10.3 Bubble Sort
Analysis of Bubble Sort
Code for Bubble Sort
55
55
B
u
b
b
l
e
S
o
r
t
■
S
e
l
e
c
t
i
o
n
s
o
r
t
i
s
r
e
l
a
t
i
v
e
l
y
e
a
s
y
t
o
u
n
d
e
r
s
t
a
n
d
.
■
The array is sorted by making several passes through the array, selecting
a next smallest item in the array each time and placing it where it belongs
in the array.
■
B
u
b
b
l
e
s
o
r
t
(
a
l
s
o
k
n
o
w
n
a
s
s
i
n
k
i
n
g
s
o
r
t
)
i
s
a
l
s
o
a
s
i
m
p
l
e
s
o
r
t
i
n
g
a
l
g
o
r
i
t
h
m
■
The array is sorted by repeatedly stepping through the array, comparing
adjacent pairs, and swapping them if they are in the wrong order, until the
array is sorted.
■
Smaller values bubble up to the top of the array and larger values sink to
the bottom; hence the name.
■
S
e
l
e
c
t
i
o
n
s
o
r
t
a
n
d
B
u
b
b
l
e
s
o
r
t
a
r
e
q
u
a
d
r
a
t
i
c
s
o
r
t
s
.
Sort (34)
56
56
Sort (34)
57
57
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
58
58
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
59
59
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
60
60
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
61
61
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
62
62
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
At the end of pass 1, the last
item (index [4]) is guaranteed
to be in its correct position.
There is no need to test it
again in the next pass
Sort (34)
63
63
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
64
64
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
65
65
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
66
66
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
67
67
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
68
68
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
69
69
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
70
70
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
71
71
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
72
72
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
73
73
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
74
74
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Sort (34)
75
75
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
Where
n
is the length of the array,
after the completion of
n
– 1 passes
(4, in this example) the array is sorted
Sometimes an array will be sorted before
n
– 1 passes. This can be detected if there
are no exchanges made during a pass
through the array
Sort (34)
76
76
T
r
a
c
e
o
f
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
S
o
r
t
t
h
e
f
o
l
l
o
w
i
n
g
i
n
t
e
g
e
r
a
r
r
a
y
i
n
a
s
c
e
n
d
i
n
g
o
r
d
e
r
u
s
i
n
g
b
u
b
b
l
e
s
o
r
t
.
S
h
o
w
e
a
c
h
s
t
e
p
.
How many exchanges?
The algorithm can be modified to detect
exchanges
Sort (34)
78
78
R
e
f
i
n
e
d
B
u
b
b
l
e
S
o
r
t
1.
do
2.
for each adjacent pair
3.
if item[i] > item[i+1]
4.
exchange item[i],item[i+1]
5.
endfor
6.
while the array is not sorted
1.
do
2.
exchanges = false
3.
for each adjacent pair
4.
if item[i] > item[i+1]
5.
exchange item[i],item[i+1]
6.
exchanges = true
7.
endfor
8.
while
exchanges == true
S
o
r
t
t
h
e
f
o
l
l
o
w
i
n
g
i
n
t
e
g
e
r
a
r
r
a
y
i
n
a
s
c
e
n
d
i
n
g
o
r
d
e
r
u
s
i
n
g
r
e
f
i
n
e
d
b
u
b
b
l
e
s
o
r
t
.
S
h
o
w
e
a
c
h
s
t
e
p
.
How many exchanges?
■
The number of comparisons and exchanges is represented by
(n – 1) + (n – 2) + ... + 3 + 2 + 1
■
Worst case:
■
number of comparisons is O(
n
2
).
■
number of exchanges is O(
n
2
).
■
Compared to selection sort with its O(
n
2
) comparisons and O(
n
)
exchanges, bubble sort usually performs worse.
■
If the array is sorted early, the later comparisons and
exchanges are not performed and performance is improved.
■
The best case occurs when the array is sorted already
■
one pass is required (O(n) comparisons).
■
no exchanges are required (O(1) exchanges).
■
Bubble sort works well on arrays nearly sorted and worst on
inverted arrays (elements are in reverse sorted order).
Sort (34)
80
80
A
n
a
l
y
s
i
s
o
f
B
u
b
b
l
e
S
o
r
t
Sort (34)
81
81
#ifndef BUBBLESORT_H_
#define BUBBLESORT_H_
#include <algorithm>
/** Sort data in the specified sequence using bubble sort.
@param first An iterator that references the first element in the sequence to be sorted
@param last An iterator that references 1 past the end of the sequence
*/
template<typename RI>
void bubble_sort(RI first, RI last)
{int pass = 1;
bool exchanges;
do
{ // Invariant: Elements after position last - pass are in place.
exchanges = false;
// No exchanges yet.
// Compare each pair of adjacent elements.
for (RI first_of_pair = first; first_of_pair != last - pass; ++first_of_pair)
{RI second_of_pair = first_of_pair + 1;
if (*second_of_pair < *first_of_pair)
{ // Exchange pair.
std::iter_swap(first_of_pair, second_of_pair);
exchanges = true;
// Set flag.
}
}
pass++;
} while (exchanges);
return;
}
#endif
B
u
b
b
l
e
S
o
r
t
I
m
p
l
e
m
e
n
t
a
t
i
o
n
Be Safe
Delve into the world of sorting algorithms in data structures through comprehensive coverage of concepts, performance optimization tips, and associative set/map implementations. Explore various sorting strategies and understand the importance of efficient coding practices for enhanced runtime performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Welcome to CS 235 Data Structures Sorting (34) Chapter 10.1-3, pgs. 555-564
Attendance Quiz #33 2 Sort (34)
Tip #34: Non-compiler Performance 3 Sort (34) 1. Don't define object variables before their use/initialization, which necessitates that the constructor AND assignment operator functions will run could be costly for complex objects. 2. Consider the order of evaluation of compound conditionals. e.g., given if (a && b), if b is more likely to be false, place it first to save the evaluation of a. 3. Minimize the use of temporaries (particularly with string-based processing). 4. Use heap memory (dynamic allocation) only when necessary as dynamic allocations and deallocations are expensive. (Many C++ programmers over-use the heap.) 5. Know your compiler/linker options, especially which ones cause non-standard behavior. These dramatically affect runtime performance. 6. Know the performance/functionality tradeoffs of the STL containers (e.g., don't frequently insert into a vector, use a list).
Associative Set/Map Implementations 5 Sort (34) Ordered Set (Linked List) unordered, duplicates push_front(item) -> addNode(item); (n) search or Ordered Set (BST) ordered, unique (log n) search cat dog dog cat pig horse horse pig Unordered Hash Map (Chained) Bucketed ordered list unordered, unique (?) (1) average search Unordered Hash Map (Open addressing) Linear or Quadratic probe unordered, unique (1) average search Quadratic probe cat cat cat cat dog dog dog dog horse horse pig pig pig pig horse horse
Pokmon Maps and Sets 6 Sort (34) HashMap<string,string> pokemon; HashMap<string,string> moves; Pokemon: Charmander fire (1) Bulbasaur grass (1) Squirtle water (1) pair<string,string> pair<string,string> "" "razor_leaf" "water_gun" "flamethrower" "" "" "grass" "water" "fire" "" "Squirtle" "Charmander" "Bulbasaur" "" "" "water" "fire" "grass" "" "" [0] [0] [1] [1] [2] [2] [3] [3] [4] [4] Moves: flamethrower fire (3) water_gun water (2) razor_leaf grass (2) HashMap<string,Set<string>> effectivities; pair<string,Set<string>> Set<string> "ground" "rock" "water" "grass" "" "fire" "" "water" [0] NULL [1] "bug" "grass" "ice" [2] Effectivities: fire grass ice bug (2) water ground rock fire (4) grass water ground rock (4) NULL "fire" "ground" "rock" [3] [4] HashMap<string,Set<string>> ineffectivities; pair<string,Set<string>> Set<string> "bug" "fire" "grass" "grass" "" "fire" "" "water" [0] Ineffectivities: fire fire water rock (2) water water grass (4) grass grass bug fire (4) NULL [1] "fire" "water" "rock" [2] NULL "grass" "water" [3] [4]
10.1 Using C++ Sorting Functions 10.1, pgs. 570-572 7
Chapter Objectives 8 Sort (34) To learn how to use the standard sorting functions in algorithm.h. To learn how to implement the following sorting algorithms: selection sort bubble sort insertion sort Shell sort merge sort heapsort quicksort To understand the difference in performance of these algorithms, and which to use for small, medium, and large arrays. Sorting entails arranging data in decreasing (or non-increasing) or increasing (or non-decreasing) order Familiarity with sorting algorithms is an important programming skill. The study of sorting algorithms provides insight into problem solving techniques such as divide and conquer. the analysis and comparison of algorithms which perform the same task.
Using C++ Sorting Methods 9 Sort (34) The Standard C++ Library (in algorithm.h) provides versions of sorting functions using a pair of random-access iterators: template<typename RI> void sort(RI first, RI last); template<typename RI, typename Compare> void sort(RI first, RI last, Compare comp); Because these functions require random-access iterators, they can be used only with vectors, deques, and ordinary C pointers (for sorting arrays). Note: The list container supports only bidirectional iterators, so it provides its own sort member function. If we use the second version of function sort, we must also pass an object that implements a comparison function (functor).
Using C++ Sorting Methods 10 Sort (34) If people_list is a vector of Person objects, then: sort(people_list.begin(), people_list.end(), Compare_Person()); sorts the elements in people_list in ascending order based on their names. The Compare_Person function class is used to compare objects: struct Compare_Person { bool operator()(const Person& p1, const Person& p2) { return ((p1.family_name < p2.family_name) || ((p1.family_name == p2.family_name) && (p1.given_name < p2.given_name)); } }
Using C++ Sorting Methods 11 Sort (34) If array items stores a collection of 16 integers, the array is sorted by: sort(items, items + 16); This statement sorts only the first half of the array, leaving the rest untouched: sort(items, items + 8); This function call sorts the array in descending order: sort(items, items + 16, greater<int>()); where greater<int> implements the comparison operator> for integers (defined in library functional).
Using C++ Sorting Methods 12 Sort (34) There are also two functions named stable_sort, which are similar to the sort functions. The primary difference is that elements that are equal may not retain their relative ordering when sort is used, but they will retain their relative ordering when stable_sortis used. In other words, if there are two occurrences of an item, the one that is first in the unsorted array is guaranteed to be first in the sorted array only if stable_sortis used. This function call sorts an array in descending order: stable_sort(items, items + 16, greater<int>()); The sort function is slightly faster than stable_sort, so it should be used whenever the relative ordering of equal elements is unimportant.
10.2 Selection Sort 10.3 Bubble Sort 10.2, pgs. 572-580 13
Selection Sort and Bubble Sort 14 Sort (34) Selection sort is relatively easy to understand. The array is sorted by making several passes through the array, selecting a next smallest item in the array each time and placing it where it belongs in the array. Bubble sort (also known as sinking sort) is also a simple sorting algorithm The array is sorted by repeatedly stepping through the array, comparing adjacent pairs, and swapping them if they are in the wrong order, until the array is sorted. Smaller values bubble up to the top of the array and larger values sink to the bottom; hence the name. Selection sort and Bubble sort are quadratic sorts.
Selection Sort 15 Sort (34) Selection sort is relatively easy to understand. It sorts an array by making several passes through the array, exchanging items if smaller. For simplicity, we illustrate all the sorting algorithms using an array of integer values. 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 0 1 2 3 4 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 35 65 30 60 20 5. endfor 6. endfor
Trace of Selection Sort 16 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 35 65 30 60 20 fill 0 next fill
Trace of Selection Sort 17 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 35 65 30 60 20 fill 0 next 1 fill next
Trace of Selection Sort 18 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 35 65 30 60 20 fill 0 next 1 fill next
Trace of Selection Sort 19 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 35 65 30 60 20 fill 0 next 2 fill next
Trace of Selection Sort 20 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 35 65 30 60 20 fill 0 next 2 fill next
Trace of Selection Sort 21 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 30 65 35 60 20 fill 0 next 2 fill next
Trace of Selection Sort 22 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 30 65 35 60 20 fill 0 next 3 fill next
Trace of Selection Sort 23 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 30 65 35 60 20 fill 0 next 3 fill next
Trace of Selection Sort 24 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 30 65 35 60 20 fill 0 next 4 fill next
Trace of Selection Sort 25 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 30 65 35 60 20 fill 0 next 4 fill next
Trace of Selection Sort 26 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 65 35 60 30 fill 0 next 4 fill next
Trace of Selection Sort 27 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 65 35 60 30 fill 0 next 5 fill next
Trace of Selection Sort 28 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 65 35 60 30 fill 1 next 4 fill next
Trace of Selection Sort 29 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 65 35 60 30 fill 1 next 2 fill next
Trace of Selection Sort 30 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 65 35 60 30 fill 1 next 2 fill next
Trace of Selection Sort 31 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 35 65 60 30 fill 1 next 2 fill next
Trace of Selection Sort 32 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 35 65 60 30 fill 1 next 3 fill next
Trace of Selection Sort 33 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 35 65 60 30 fill 1 next 3 fill next
Trace of Selection Sort 34 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 35 65 60 30 fill 1 next 4 fill next
Trace of Selection Sort 35 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 35 65 60 30 fill 1 next 4 fill next
Trace of Selection Sort 36 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 65 60 35 fill 1 next 4 fill next
Trace of Selection Sort 37 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 65 60 35 fill 1 next 5 fill next
Trace of Selection Sort 38 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 65 60 35 fill 2 next 5 fill next
Trace of Selection Sort 39 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 65 60 35 fill 2 next 3 fill next
Trace of Selection Sort 40 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 65 60 35 fill 2 next 3 fill next
Trace of Selection Sort 41 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 60 65 35 fill 2 next 3 fill next
Trace of Selection Sort 42 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 60 65 35 fill 2 next 4 fill next
Trace of Selection Sort 43 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 60 65 35 fill 2 next 4 fill next
Trace of Selection Sort 44 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 65 60 fill 2 next 4 fill next
Trace of Selection Sort 45 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 65 60 fill 2 next 5 fill next
Trace of Selection Sort 46 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 65 60 fill 3 next 5 fill next
Trace of Selection Sort 47 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 65 60 fill 3 next 4 fill next
Trace of Selection Sort 48 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 65 60 fill 3 next 4 fill next
Trace of Selection Sort 49 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 60 65 fill 3 next 4 fill next
Trace of Selection Sort 50 Sort (34) 1. for fill = 0 to n 2 2. for next = fill + 1 to n 1 3. if item[next] < item[fill] 4. exchange item[pos_min],item[fill] 5. endfor 6. endfor 0 1 2 3 4 n 5 20 30 35 60 65 fill 3 next 5 fill next
