Jimma University
Faculty of Computing and
Informatics.
Chapter 2
Simple Sorting and Searching Algorithms
Jimma, Ethiopia.
Outline
At the end of this session the students should be able to:
Design and implement simple sorting algorithms
Compare the efficiency of the sorting algorithms in terms of Big-O
complexity requirements to sort small number of elements.
Design and implement simple searching algorithms
Discuss the efficiency of simple searching algorithms
Sorting Algorithms
Sorting algorithms commonly consist of two types of operation: comparisons
and data movements.
A comparison is simply comparing one value in a list with another, and a data
movement (swapping) is an assignment.
A = { 3 1 6 2 1 3 4 5 9 0 }
A = { 0 1 1 2 3 3 4 5 6 9 }
Cont...
Sorting is one of the most important operations performed by computers.
It is a process of reordering a list of items in either increasing or decreasing
order.
Sorting is used to arrange names or numbers in meaning full ways.
By default sorting is performed in ascending order.
The following are simple sorting algorithms used to sort small-sized lists.
Bubble Sort
Selection Sort
Insertion Sort
Bubble Sort
The simplest algorithm to implement
The slowest algorithm on very large inputs.
Bubble sort:
Makes a number of passes through array:
• First bubble the largest element putted in last position, by
iteratively comparing & swapping adjacent elements starting
with the start of the list
• Next bubble next largest element putted to last-1 position
• etc. until all apart from first element placed
Basic Idea:
Loop through array from i=0 to n and swap adjacent elements if they
are out of order.
Example
Example data element= E,B,C,A,D Sort them by bubble sorting Algorithm
Cont...
Example-Bubble Sort
Original array:
1 23 2 56 9 8 10 100
1 1 23 2 56 9 8 10 100
2 1 23 2 56 9 8 10 100
3 1 2 23 56 9 8 10 100
4 1 2 23 56 9 8 10 100 Sort the following elements using
5 1 2 23 9 56 8 10 100 bubble sort algorithm
6 1 2 23 9 8 56 10 100
7 1 2 23 9 8 10 56 100 8 5 7 3 2
---- finish the first traversal ----
---- start again ----
8 1 2 23 9 8 10 56 100
9 1 2 9 23 8 10 56 100
10 1 2 9 8 23 10 56 100
11 1 2 9 8 10 23 56 100
---- finish the second traversal ----
---- start again ----
Algorithm for Bubble Sort
Pseudo code
Set flag = false
1. Traverse the array and compare pairs of two elements
1.1 If E1 E2
- OK
1.2 If E1 > E2 then
Switch(E1, E2) and set flag = true
2. If flag = true goto 1.
Implementation
void bubble_sort(list[], int n){
int i,j,temp, flag;
for(i=0;i<n-1; i++){
Used to iterate over the all data(number of passing
flag=0; • Used to iterate over list and compare each
adjacent element. If the condition true
for(j=0; j<n-1-i; j++){
swap the elements.
if(list[j]>list[j+1]){ • The loop iterate until the n-1-i .i.e after first
temp=list[j]; loop last index is sorted, after second loop
the last index-1 is sorted …etc
list[j]=list[j +1];
list[j +1]=temp;
flag=1
}//swap adjacent elements
}//end of inner loop Used to check if the array is already sorted or not
if(flag==0)
break;
}//end of outer loop
}//end of bubble_sort
Efficiency of Bubble Sort
How many comparisons?
(n-1)+(n-2)+…+1= n*(n-1)/2=n2/2
(n-1)+(n-2)+…+1= O(n2)
How many swaps?
(n-1)+(n-2)+…+1= O(n2)
where n is the number of items in the array. This is slow.
Selection Sort
Each element is swapped directly with the element that occupies its correct position
How does it work:
First find the smallest in the array and exchange it with the element in the first
position,
then find the second smallest element and exchange it with the element in the
second position, and
• Then repeat these operations with the remaining n-1 items
until only one item— the largest -- is left..
Keep the left portion n-1 is sorted.
At ith step, first i element is sorted. All element are bigger that first i elements
Example
Original array: 6354927
1st pass -> 2 3 5 4 9 6 7 (2 and 6 were swapped)
2nd pass -> 2 3 4 5 9 6 7 (4 and 5 were swapped)
3rd pass -> 2 3 4 5 6 9 7 (6 and 9 were swapped)
4th pass -> 2 3 4 5 6 7 9 (7 and 9 were swapped)
5th pass -> 2 3 4 5 6 7 9 (no swap)
6th pass -> 2 3 4 5 6 7 9 (no swap)
Algorithm for Selection Sort
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in non decreasing order.
1. for i 0 to n - 1
2. ki
3. for j i + 1 to n {Find the i th smallest element.}
4. if A[j] < A[k] then k j
5. end for
6. if k i then interchange A[i] and A[k]
7. end for
Implementation
void selection_sort(int list[]){
int i,j, smallest;
for(i=0;i<n;i++){
smallest=i;
for(j=i+1;j<n;j++){
if(list[j]<list[smallest])
smallest=j;
}//end of inner loop
if (smallest!=i){
temp=list[smallest];
list[smallest]=list[i];
list[i]=temp;
}
} //end of outer loop
Efficiency of Selection Sort
How many comparisons?
(n-1)+(n-2)+…+1= n*(n-1)/2=n2/2
(n-1)+(n-2)+…+1= O(n2)-running time
How many swaps?
(n-1)+(n-2)+…+1= O(n) (reduced)
where n is the number of items in the array
This is faster for smaller values of n.
a good algorithm to sort a small number of elements.
Insertion Sort
Insertion sort keeps making the left side of the array sorted until the whole array
is sorted.
A[ i ] is inserted in its proper position in the ith iteration in the sorted subarray
A[0 .. i-1]
In the ith step, the elements from index i-1 down to 0 are scanned, each time
comparing A[i] with the element at the correct position.
In each iteration an element is shifted one position up to a higher index.
The process of comparison and shifting continues until:
Either an element ≤ A[i] is found or
When all the sorted sequence so far is scanned.
Then A[ i ] element is inserted in its proper position.
Example: sorting numbered cards
23 17 45 18 12 22
Given some numbered cards.
Our aim is to put them in increasing order.
20
Example: sorting numbered cards
23 17 45 18 12 22
1 2 3 4 5 6
1 2 3 4 5 6
21
Example: sorting numbered cards
17 45 18 12 22
1 2 3 4 5 6
23
1 2 3 4 5 6
22
Example: sorting numbered cards
45 18 12 22
1 2 3 4 5 6
17 23
1 2 3 4 5 6
23
Example: sorting numbered cards
18 12 22
1 2 3 4 5 6
17 23 45
1 2 3 4 5 6
24
Example: sorting numbered cards
12 22
1 2 3 4 5 6
17 18 23 45
1 2 3 4 5 6
25
Example: sorting numbered cards
1 2 3 4 5 6
12 17 18 22 23 45
1 2 3 4 5 6
26
Algorithm: INSERTION SORT
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in non decreasing order.
1. for i 1 to n
2. x A[i]
3. ji
4. while (j >0) and (A[j] > x)
5. A[j + 1] A[j]
6. jj-1
7. end while
8. A[j + 1] x
9. end for
Implemention
void insertion_sort(int list[]){
int temp;
for(int i=1;i<n;i++){
temp=list[i];
j=i;
while(j>0 && list[j-1]>temp) { // work backwards through the array finding where temp
should go
list[j]=list[j-1];
j--;
} //end of inner loop
list[j]=temp;
} //end of outer loop
} //end of insertion_sort
Analysis of Insertion Sort
How many comparisons?
1+ 2+ 3+ …+ (n-1)= n*(n-1)/2
1+ 2+ 3+ …+ (n-1)= O(n2)- running time
How many copies?
1+ 2+ 3+ …+ (n-1)= O(n2)
compares a maximum of 1 item in the first pass.
A copy isn’t time consuming as swap.
Empirically it’s known that Insertion sort is over twice as fast as the bubble sort
and is just as easy to implement as the selection sort.
Searching Algorithm
Linear Searching
Binary Searching
Cont...
Searching is a process of looking for a specific element in a list of items or
determining that the item is not in the list.
There are two elementary searching algorithms:
Sequential Search (Linear), and
Binary Search
Sequential (Linear) Search
It is natural way of searching
The algorithm does not assume that the data is sorted.
The basic idea is:
The sequential search algorithm begins at the first position in the
array and looks at each value in turn until, the K is found. Once K is
found, the algorithm stops.
NOTE: consider K as an item being looked for.
Algorithm:
Search list from the beginning until key is found or end of list
reached.
Cont...
Each element of an array is read one by one sequentially and it is compared with
the search key.
Let A be an array of having n elements, A[0], A[1], A[2], ......, A[n-1]. “item” is
the element to be searched. Then this algorithm will find the location “loc” of
item in A.
Set loc = – 1, if the search is unsuccessful.
Example
List index 0 1 2 3 4 5 6 7
Data C A E F N Q R K
Key=Q after 6 comparison the algorithm returns 1, i.e. found
Key=X after 8 comparison the algorithm returns -1 i.e. found false
Algorithm for linear search
1. Input an array A of n elements and “item” to be searched and initialize
loc = – 1.
2. Initialize i = 0; and repeat through step 3 if (i < n) by incrementing i by
one.
3. If (item == A[i])
loc = i
GOTO step 4
4. If (loc >= 0)
Display “item is found and searching is successful”
5. else
Display “item is not found and searching is unsuccessful”
6. exit
Efficiency of linear search algorithm runs in O(n) time
Implementation
int Linear_Search(int list[], int key){
int i=0;
int loc= -1;
do{
if(key==list[i])
loc=i;
else
i++;
}while(loc==-1&&i<n);
if(loc>=0)
cout<<““item is found and searching is successful”;
return loc;
}
Time complexity
Time Complexity of the linear search is found by number of comparisons made
in searching a record.
In the best case, the desired element is present in the first position of the
array, i.e., only one comparison is made. So f(n) = O(1).
In the Average case, the desired element is found in the half position of the
array, then f(n) = O[(n + 1)/2].
In the worst case the desired element is present in the nth (or last) position
of the array, so n comparisons are made, then f(n)=O(n+1).
Binary Search algorithm
Binary search is an extremely efficient algorithm when it is compared to linear
search.
Binary search technique searches “item” in minimum possible comparisons.
Assumption
the given array is a sorted one, otherwise first we have to sort the array
elements.
This searching algorithm works only on an ordered list.
Binary search begins by examining the value in the middle position of the array;
call this position mid and the corresponding value k mid.
If k mid = K, then Processing can stop immediately
The basic idea of binary search
1. Find the middle element of the array (i.e., n/2 is the middle element if the
array or the sub-array contains n elements).
2. Compare the middle element with the data to be searched, and then there
are following three cases.
1. If it is a desired element, then search is successful.
2. If it is greater than desired data, then search only the first half of the
array, i.e. the elements which come to the left side of the middle
element.
3. If it is less than the desired data, then search only the second half of
the array, i.e., the elements which come to the right side of the middle
element.
3. Repeat the same step until an element is found or exhaust the search area.
Example
Algorithm for Binary Search
1. input “n” elements of the array and the element going to be searched “x”;
2. initialize i=0 and repeat through step 3 if (i<n)
3. do step “ 4” while left < right and flag =0
4. mid=(right+left)/2;
if(array[mid]==x){
flag=1
return mid
}
if(array[mid]<x)
left=mid+1
otherwise
right= mid-1
5. if flag = 0 index= -1 otherwise index=mid
6. return index
Implementation
int Binary_Search(int list[],int k){
if(found==0)
int left=0; index=-1;
int right=n-1; else
int found=0; index=mid;
do{ return index;
mid=(left+right)/2; }
if(key==list[mid])
found=1;
else{
if(key<list[mid])
right=mid-1;
else
left=mid+1;
}
}while(found==0&&left<right);
Time Complexity
Time Complexity is measured by the number f (n) of comparisons to locate
“data” in A, which contain n elements.
Observe that in each comparison the size of the search area is reduced by
half.
Hence in the worst case, at most logn comparisons required. So f(n)= O([log n ]
+1).
Time Complexity in the average case is almost approximately equal to the
running time of the worst case.
Cont...
The End !!
45
