Tutorial 9
Hashing and Sorting
R. Tharmarasa
Department of Electrical and Computer Engineering
McMaster University
January 2022
Performance of Closed Hashing
The set of all possible keys is the set of all integers from 0 to 19 inclusive.
Consider a hash table of size 𝑀 = 10 and the hash function: ℎ(𝑥) = 𝑥
mod 10 with linear probing. Fill the table and calculate the average number
of probes required when an element is present.
Index Element ℎ(𝑥) # Probes
0 10
1 11
2 01
3
4 14
5 04
6
7 17
8
9 19
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 2/8
Performance of Closed Hashing
The set of all possible keys is the set of all integers from 0 to 19 inclusive.
Consider a hash table of size 𝑀 = 10 and the hash function: ℎ(𝑥) = 𝑥
mod 10 with linear probing. Fill the table and calculate the average number
of probes required when an element is present.
Index Element ℎ(𝑥) # Probes
0 10 0 1
1 11 1 1
2 01 1 2
3
4 14 4 1
5 04 4 2
6
7 17 7 1
8
9 19 9 1
1+1+2+1+2+1+1
𝑆𝑛 = 7 = 9/7
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 3/8
Performance of Closed Hashing
The set of all possible keys is the set of all integers from 0 to 19 inclusive.
Consider a hash table of size 𝑀 = 10 and the hash function: ℎ(𝑥) = 𝑥
mod 10 with linear probing. Fill the table and calculate the average number
of probes required when an element is not present (unsuccesful search).
Index Element Not found keys with ℎ(𝑥) = Index # Probes for failure
0 10
1 11
2 01
3
4 14
5 04
6
7 17
8
9 19
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 4/8
Performance of Closed Hashing
The set of all possible keys is the set of all integers from 0 to 19 inclusive.
Consider a hash table of size 𝑀 = 10 and the hash function: ℎ(𝑥) = 𝑥
mod 10 with linear probing. Fill the table and calculate the average number
of probes required when an element is not present (unsuccesful search).
Index Element keys not found with ℎ(𝑥) = Index # Probes for failure
0 10 00 4
1 11 3
2 01 02,12 2
3 03,13 1
4 14 3
5 04 05,15 2
6 06,16 1
7 17 07 2
8 08,18 1
9 19 09 5
4∗1+2∗2+1∗2+2∗2+1∗2+2∗1+1∗2+5∗1 25
𝑈𝑛 = 13 = 13
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 5/8
Inversions
Write all the inversions in the following array
[3 4 2 1 5]
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 6/8
Inversions
Write all the inversions in the following array
[3 4 2 1 5]
(3,2), (3,1), (4,2), (4,1), (2,1)
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 6/8
Bubble Sort
Consider sorting the following array
{3, 26, 42, 2, 50, 5, 7, 22, 20}
in ascending order using Bubble Sort.
Show the swaps performed during the first pass through the array.
Then show the swaps performed during the second pass through the array.
After how many passes will the algorithm stop?
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 7/8
Bubble Sort
Consider sorting the following array
{3, 26, 42, 2, 50, 5, 7, 22, 20}
in ascending order using Bubble Sort.
Show the swaps performed during the first pass through the array.
Swaps after first pass: (42, 2), (50, 5), (50, 7), (50, 22), (50, 20)
Array content after first pass: 3, 26, 2, 42, 5, 7, 22, 20, 50
Then show the swaps performed during the second pass through the array.
After how many passes will the algorithm stop?
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 7/8
Bubble Sort
Consider sorting the following array
{3, 26, 42, 2, 50, 5, 7, 22, 20}
in ascending order using Bubble Sort.
Show the swaps performed during the first pass through the array.
Swaps after first pass: (42, 2), (50, 5), (50, 7), (50, 22), (50, 20)
Array content after first pass: 3, 26, 2, 42, 5, 7, 22, 20, 50
Then show the swaps performed during the second pass through the array.
Swaps after second pass: (26, 2), (42, 5), (42, 7), (42, 22), (42, 20
Array content after second pass: 3, 2, 26, 5, 7, 22, 20, 42, 50
After how many passes will the algorithm stop?
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 7/8
Bubble Sort
Consider sorting the following array
{3, 26, 42, 2, 50, 5, 7, 22, 20}
in ascending order using Bubble Sort.
Show the swaps performed during the first pass through the array.
Swaps after first pass: (42, 2), (50, 5), (50, 7), (50, 22), (50, 20)
Array content after first pass: 3, 26, 2, 42, 5, 7, 22, 20, 50
Then show the swaps performed during the second pass through the array.
Swaps after second pass: (26, 2), (42, 5), (42, 7), (42, 22), (42, 20
Array content after second pass: 3, 2, 26, 5, 7, 22, 20, 42, 50
After how many passes will the algorithm stop?
Array content after third pass: 2, 3, 5, 7, 22, 20, 26, 42, 50
Array content after fourth pass: 2, 3, 5, 7, 20, 22, 26, 42, 50
Array content after fifth pass: 2, 3, 5, 7, 20, 22, 26, 42, 50 (no swap, so stop)
The algorithm stops after 5 passes.
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 7/8
Bubble Sort
Is bubble sort a stable sorting algorithm?
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 8/8
Bubble Sort
Is bubble sort a stable sorting algorithm?
Yes
Tutorial 9: Hashing and Sorting CompEng 2SI3 - Winter 2022 8/8