DATA STRUCTURES
AND ALGORITHMS
DR. FATMA ELGENDY
1. Sorting Algorithms
2. Searching Algorithms
SELECTION SORT EXAMPLE
60 40 50 30 10 20
Round # 1 10 40 50 30 60 20
Round # 2 10 20 50 30 60 40
Round # 3 10 20 30 50 60 40
Round # 4 10 20 30 40 60 50
Round # 5 10 20 30 40 50 60
SELECTION SORT ALGORITHM
SELECTION SORT CODE
COMPLEXITY OF SELECTION SORT
• Time Complexity
▪ Worst Case Performance O(n2)
▪ Average Case Performance O(n2)
▪ Best Case Performance O(n2)
• Space Complexity
O(1)
BUBBLE SORT EXAMPLE
60 40 50 30 10 20
Round # 1 40 50 30 10 20 60
Round # 2 40 30 10 20 50 60
Round # 3 30 10 20 40 50 60
Round # 4
10 20 30 40 50 60
Round # 4 10 20 30 40 50 60
BUBBLE SORT ALGORITHM
BUBBLE SORT CODE
BUBBLE SORT COMPLEXITY
• Time Complexity
▪ Worst Case Performance O(n2)
▪ Best Case Performance O(n2)
▪ Average Case Performance O(n2)
• Space Complexity
▪ O(1)
INSERTION SORT EXAMPLE
z 60 40 50 30 10 20
Round # 1 40 60 50 30 10 20
Round # 2 40 50 60 30 10 20
Round # 3 30 40 50 60 10 20
Round # 4 10 30 40 50 60 20
Round # 5
10 20 30 40 50 60
INSERTION SORT ALGORITHM
INSERTION SORT CODE
TIME COMPLEXITY
• Time Complexity
• Worst Case Performance O(n2)
• Best Case Performance(nearly) O(n)
• Average Case Performance O(n2)
• Space Complexity
• O(1)
SEQUENTIAL SEARCH
SEQUENTIAL SEARCH ALGORITHM
SEQUENTIAL SEARCH CODE
• Note: the function returns true if the item is present. Else, it returns false
• Note: the function returns the item index if the item is present. Else, it returns -1
SEARCHING FOR MINIMUM VALUE
SEARCHING FOR MAXIMUM VALUE
COMPLEXITY OF SEQUENTIAL SEARCH
• Time Complexity
case Best case Average case Worst case
If item is present O(1) O(n/2) O(n)
If item isn’t present O(n) O(n) O(n)
• Space complexity
• O(1)
BINARY SEARCH ALGORITHM
BINARY SEARCH CODE
COMPLEXITY OF BINARY SEARCH
• Time Complexity
case Best case Average case Worst case
If item is present O(1) O(log n) O(log n)
If item isn’t present O(log n) O(log n) O(log n)
• Space complexity
• O(1)
