Data Structures and Algorithms
Insertion Sort:
Input: sequence of n numbers
: Output: sorted permutation of the input
•
Efficient algorithm for sorting a small
number of elements
•
Algorithm sorts the input numbers in
place: it rearranges the numbers within
the array A, with at most a constant
number of them stored outside the array
at any time.
Best case performance: execute the while loop the least as possible. The array is already sorted
so the comparison test always fails. For the best case time complexity T(n) is in Θ(n)
Worst case performance: execute the while loop as many times as possible. The array is sorted
in a reversed way, so the comparison test always succeeds. T(n) = an + bn + c so T(n) is in Θ(n )
2 2
Insertion sort can be stable: the order of equal elements is respected. If the comparison would be
>= instead of > then it is not stable anymore.
Rate of growth:
Theta notation says something about the rate of growth, so we want this to be as low as
possible. To find Θ, we want to drop the lower order terms and we want to drop constants.
② asymptotic tight bound (=) 3M€ -042) 3N # ② (M) 3 € -04 )
0 asymptotic upper bound (<=) 3M€ 0cm) Îdoes not
3N C- OCN increase
r asymptotic lower bound (>=)
Useful properties big-O
na € Ocnb ) for AEB
109dm) E (nb) for alt a. b) 0
na 0lb ) for
"
c- an a> 0 ,
b > 1
for
109A ( n ) E
109ns (n ) alt a.
b > 0
IJ
,Merge sort
How do we sort?
Stop condition: if the sequence contains less than 2 elements; otherwise:
⑥
Split the sequence into 2 parts of (almost) equal length
•
Sort the two subsequences using merge sort (recursion)
•
Merge the two sorted sublists
How do we merge?
Loop: as long as both sequences are non-empty
•
Compare the first elements of both sequences
•
Remove the smallest and move it to the end of the output sequence
Last: if one of the sequences is empty, add the other to the tail of the output sequence
: Worst-case time complexity via tree analysis:
Height is log(n) for n the length of the input array (example has height log2(8) = 3)
Number of levels is log(n) + 1 (example has 3 + 1 = 4 levels)
Number of leaves is n (example has 8 leaves
T(n) = c x n x log(n) + d x n
Time complexity of merge sort is in Θ (nlog(n))
Shape of the input is unimportant. Best case = worst case time complexity
Divide is Θ(1), conquer is recursive, combine is Θ(n), so:
Time complexity via recurrence equations:
First assume n = 2
Then: 1- ( )
base
n
case
d=
it
{
Ê
if
2T ( E
=
I
) +
so
en
i =
if
109 (n)
na
n> 1
ËË
Substitute this 1-( n) n 1- ( i )
109 (n) c. n c.
Nog (n ) + d- n
=
: = .
+ .
Hence T is in ②(
mogen) )
The worst-case time complexity is better than for insertion sort, but this algorithm is
not in-place, whereas insertion sort is in-place (drawback)
, Trees:
Set of nodes with a parent-child relation
-
There is a unique distinguished node root (top node)
: Every non-root has a unique parent
A node may have successors / children
-
A node without successors is a leaf (lowest ones)
: A node with successors is internal
The depth of a node is the length of the path to the root.
: The height of a node is the maximum length of a path to the leaf.
The height of a tree is the height of the root or the maximal depth.
: A level or layer of a tree consists of all nodes of the same depth.
\
The number of levels of a tree is the height of the tree + 1
Binary tree:
- Every node has zero, one or two successors.
- Binary tree is complete if all levels are completely filled.
Binary tree is almost complete if all levels are completely filled, except possibly the lowest one
: which is filled left-to-right.
If a binary tree is complete, it is also almost complete, and therefore also normal binary.
Consider an almost binary tree of height h:
I If the lowest level contains 1 element, then number of elements n = 2^h
If the lowest level is full, then the number of elements is n = 2^(h+1) - 1
I So h = Ilog(n)I . So round down
I
X . P
if xp = nil ,
it is root
Divide and conquer paradigm: - quick sort
Divide: divide the problem into smaller sub problems - merge sort
: Conquer: solve the sub problems using recursion
-
Combine: combine the solutions to the sub problems to a solution of the original problem
Max-heap:
Max-heap is a data structure used for sorting: if we walk down the tree, the keys decrease.
: Condition on the shape: an almost complete tree.
-
Every node is labeled with a key.
s
Max-heap property on the keys: on every path from the root to a leaf, the keys are non-increasing,
that means H[parent(i)] >= H[i].
'
Hence, the max key is the root.
116 \ [ 16.14.10 11.7.9]
14 10
,
.
A min-heap would have keys that increase walking downwards. I I I
11 7
9
Insertion Sort:
Input: sequence of n numbers
: Output: sorted permutation of the input
•
Efficient algorithm for sorting a small
number of elements
•
Algorithm sorts the input numbers in
place: it rearranges the numbers within
the array A, with at most a constant
number of them stored outside the array
at any time.
Best case performance: execute the while loop the least as possible. The array is already sorted
so the comparison test always fails. For the best case time complexity T(n) is in Θ(n)
Worst case performance: execute the while loop as many times as possible. The array is sorted
in a reversed way, so the comparison test always succeeds. T(n) = an + bn + c so T(n) is in Θ(n )
2 2
Insertion sort can be stable: the order of equal elements is respected. If the comparison would be
>= instead of > then it is not stable anymore.
Rate of growth:
Theta notation says something about the rate of growth, so we want this to be as low as
possible. To find Θ, we want to drop the lower order terms and we want to drop constants.
② asymptotic tight bound (=) 3M€ -042) 3N # ② (M) 3 € -04 )
0 asymptotic upper bound (<=) 3M€ 0cm) Îdoes not
3N C- OCN increase
r asymptotic lower bound (>=)
Useful properties big-O
na € Ocnb ) for AEB
109dm) E (nb) for alt a. b) 0
na 0lb ) for
"
c- an a> 0 ,
b > 1
for
109A ( n ) E
109ns (n ) alt a.
b > 0
IJ
,Merge sort
How do we sort?
Stop condition: if the sequence contains less than 2 elements; otherwise:
⑥
Split the sequence into 2 parts of (almost) equal length
•
Sort the two subsequences using merge sort (recursion)
•
Merge the two sorted sublists
How do we merge?
Loop: as long as both sequences are non-empty
•
Compare the first elements of both sequences
•
Remove the smallest and move it to the end of the output sequence
Last: if one of the sequences is empty, add the other to the tail of the output sequence
: Worst-case time complexity via tree analysis:
Height is log(n) for n the length of the input array (example has height log2(8) = 3)
Number of levels is log(n) + 1 (example has 3 + 1 = 4 levels)
Number of leaves is n (example has 8 leaves
T(n) = c x n x log(n) + d x n
Time complexity of merge sort is in Θ (nlog(n))
Shape of the input is unimportant. Best case = worst case time complexity
Divide is Θ(1), conquer is recursive, combine is Θ(n), so:
Time complexity via recurrence equations:
First assume n = 2
Then: 1- ( )
base
n
case
d=
it
{
Ê
if
2T ( E
=
I
) +
so
en
i =
if
109 (n)
na
n> 1
ËË
Substitute this 1-( n) n 1- ( i )
109 (n) c. n c.
Nog (n ) + d- n
=
: = .
+ .
Hence T is in ②(
mogen) )
The worst-case time complexity is better than for insertion sort, but this algorithm is
not in-place, whereas insertion sort is in-place (drawback)
, Trees:
Set of nodes with a parent-child relation
-
There is a unique distinguished node root (top node)
: Every non-root has a unique parent
A node may have successors / children
-
A node without successors is a leaf (lowest ones)
: A node with successors is internal
The depth of a node is the length of the path to the root.
: The height of a node is the maximum length of a path to the leaf.
The height of a tree is the height of the root or the maximal depth.
: A level or layer of a tree consists of all nodes of the same depth.
\
The number of levels of a tree is the height of the tree + 1
Binary tree:
- Every node has zero, one or two successors.
- Binary tree is complete if all levels are completely filled.
Binary tree is almost complete if all levels are completely filled, except possibly the lowest one
: which is filled left-to-right.
If a binary tree is complete, it is also almost complete, and therefore also normal binary.
Consider an almost binary tree of height h:
I If the lowest level contains 1 element, then number of elements n = 2^h
If the lowest level is full, then the number of elements is n = 2^(h+1) - 1
I So h = Ilog(n)I . So round down
I
X . P
if xp = nil ,
it is root
Divide and conquer paradigm: - quick sort
Divide: divide the problem into smaller sub problems - merge sort
: Conquer: solve the sub problems using recursion
-
Combine: combine the solutions to the sub problems to a solution of the original problem
Max-heap:
Max-heap is a data structure used for sorting: if we walk down the tree, the keys decrease.
: Condition on the shape: an almost complete tree.
-
Every node is labeled with a key.
s
Max-heap property on the keys: on every path from the root to a leaf, the keys are non-increasing,
that means H[parent(i)] >= H[i].
'
Hence, the max key is the root.
116 \ [ 16.14.10 11.7.9]
14 10
,
.
A min-heap would have keys that increase walking downwards. I I I
11 7
9
