Prepared by :
Mohamed Zaghloul
Algorithms
Algorithms
Algorithms
An algorithm is a step by step method of
solving a problem .
types of Algorithms
Sorting algorithms searching
algorithms
Algorithms
We compare between algorithms in
two factors :
1- execution time of algorithm(Time
complexity).
2- the amount of memory used by
the algorithm (Space complexity) .
sorting algorithms
1- selection sort
selection sort
The selection sort algorithm sorts an array by
repeatedly finding the minimum element
(considering ascending order) from unsorted
part and putting it at the beginning. The
algorithm maintains two sub arrays in a given
array:
1) The sub array which is already sorted.
2) Remaining sub array which is unsorted.
In every iteration of selection sort, the
minimum element (considering ascending
order) from the unsorted sub array is picked
and moved to the sorted sub array
selection sort
selection sort
selection sort.h
selection sort
selection sort.c
selection sort
Example
output
selection sort
Space Complexity: O(1)
2-Bubble sort
Bubble sort
Bubble Sort is the simplest sorting
algorithm that works by repeatedly
swapping the adjacent elements if they
are in wrong order.
Bubble sort
Bubble sort
Bubble sort.h
Bubble sort
Bubble sort.c
Bubble sort
Example
output
Bubble sort
The bubble sort gets its name because
elements tend to move up into the
correct order like bubbles rising to the
surface .
Time and space complexity
3- insertion sort
insertion sort
insertion sort
insertion sort.h
insertion sort
insertion sort.c
insertion sort
Example
output
insertion sort
Time complexity
Space Complexity: O(1)
4-Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
Merge sort
merge sort.h
Merge sort
merge sort.c
Merge sort
Merge sort
Merge sort
Example
output
Master method for calculating
time complexity
Time complexity of merge sort
in merge sort
Time complexity of merge sort
in merge sort
by using Master method a=2,b=2
(case 2),so:
comparison
searching algorithms
1-Linear (Sequential) Searching
Algorithm
Linear Searching Algorithm
Start at first element of array.
Compare value to value (key) for which you are
searching
Continue with next element of the array until you
find a match or reach the last element in the array.
code
code
output
complexity of Linear Searching Algorithm
Time complexity
Space complexity
O(1)
2-Binary search
algorithm
Binary search algorithm
Binary Search Example1
Binary Search Example1
Binary Search Example 1
Binary Search Example2
Binary Search Example2
Binary Search Example2
code
code
output
complexity of Binary search
algorithm
By applying master method to get time
complexity , a=1,b=2 (case 2)