Chapter Three:
Simple Searching and Sorting Algorithm
Jimma, Ethiopia.
Sorting and searching algorithms are the most common & useful tasks in any
software development.
They take more than 25% of the running time of computer tasks.
Example:
Searching documents over the internet
Searching files and folders in a hard disk
Sorting students by their name, year, and so on
Sorting files and search results by file name, date created, and so on
Deleting and recording data from a database
Searching for the keys that locate records is often the most time-consuming action in a
program, and, therefore,
the way the records are arranged and the choice of method used for searching can make a
substantial difference in the program’s performance.
Sorting is the process of taking a list of n objects a0, a1, ..., an – 1 and rearranging
these into a list a'0, a'1, ..., a'n – 1 such that
• a'0 ≤ a'1 ≤ ··· ≤ a'n – 1.
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 }
3
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 meaningful 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
4
The simplest algorithm to implement
The slowest algorithm on very large inputs.
Bubble sort:
Makes a number of passes through an array:
• First bubble the largest element put in the last position, by iteratively
comparing & swapping adjacent elements starting with the start of the list.
• Next bubble, next largest element, put to last-1 position
• Repeat until all are placed apart from the first element.
Basic Idea:
Loop through the array from i=0 to n and swap adjacent elements if they are out
of order.
5
6
Example data element= E,B,C,A,D Sort them by bubble sorting Algorithm
Sort the following elements using the bubble sort
algorithm
9 6 8 4 3
7
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
5 1 2 23 9 56 8 10 100
6 1 2 23 9 8 56 10 100
7 1 2 23 9 8 10 56 100
---- Finish the first traversal ----
---- start again ----
1 1 2 23 9 8 10 56 100
2 1 2 9 23 8 10 56 100
3 1 2 9 8 23 10 56 100
4 1 2 9 8 10 23 56 100
---- Finish the second traversal ----
---- start again ----
8
Pseudo code
for i 0 to n-1
Set flag = false//Flag to track if any swapping happens
for j 0 to n-1-i
if A[j] >A[j+1] then
Swapp(A[j], A[j+1]
flag = true
End if
end for
if flag = = false //If no swapping occurred, the array is already sorted
loop terminates
End for
9
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 the list and compare each
for(j=0; j<n-1-i; j++){ adjacent element. If the condition is true swap the
if(list[j]>list[j+1]){ elements.
temp=list[j]; • The loop iterate until the n-1-i .i.e after the first loop
list[j]=list[j +1]; last index is sorted, after the second loop the last
list[j +1]=temp; index-1 is sorted …etc
flag=1
}//swap adjacent elements
}//end of the inner loop
if(flag==0) Used to check if the array is already sorted or
not
break;
}//end of the outer loop
}//end of bubble_sort
10
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.
11
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 the ith step, the first i element is sorted. All elements are bigger than the first i
elements
12
13
Selection sort is:
The simplest sorting techniques.
a good algorithm to sort a small number of elements
Selection sort is inefficient for large lists.
Incremental algorithms process the input elements one-by-one and maintain the
solution for the elements processed so far.
14
Original array: 6 3 5 4 9 2 7
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)
15
Input: An array A[1..n] of n elements.
Output: A[1...n] sorted in non-decreasing order.
for i 0 to n - 1
minIndex i
for j i + 1 to n {Find the i th smallest element.}
if A[j] < A[minIndex] then
minIndex j
end if
end for
if minIndex i then
interchange A[i] and A[k]
end if
End for
16
void selection_sort(int list[]){
int i,j, smallest;
for(i=0;i<n-1;i++){
smallest=i;//minIndex
for(j=i+1;j<n;j++){
if(list[j]<list[smallest])
smallest=j;//update minIndex
}//end of inner loop
if (smallest!=i){
temp=list[smallest];
list[smallest]=list[i];
list[i]=temp;
}
} //end of outer loop
17 }//end 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.
18
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 from 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.
19
The insertion sort works just like its name suggests—it inserts each item into its
proper place in the final list.
The simplest implementation of this requires two list structures - the source list and
the list into which sorted items are inserted.
To save memory, most implementations use an in-place sort that works by
moving the current item past the already sorted items and repeatedly swapping it
with the preceding item until it is in place.
It's the most instinctive type of sorting algorithm.
The approach is the same approach that you use for sorting a set of cards in your
hand.
20
23 17 45 18 12 22
Given some numbered cards.
Our aim is to put them in increasing order.
21
23 17 45 18 12 22
1 2 3 4 5 6
1 2 3 4 5 6
22
17 45 18 12 22
1 2 3 4 5 6
23
1 2 3 4 5 6
23
45 18 12 22
1 2 3 4 5 6
17 23
1 2 3 4 5 6
24
18 12 22
1 2 3 4 5 6
17 23 45
1 2 3 4 5 6
25
12 22
1 2 3 4 5 6
17 18 23 45
1 2 3 4 5 6
26
1 2 3 4 5 6
12 17 18 22 23 45
1 2 3 4 5 6
27
28
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. j i-1
4. while (j >-1) and (A[j] > x)
5. A[j + 1] A[j]
6. jj-1
7. end while
8. A[j + 1] x
9. end for
29
void insertion_sort(int list[]){
int temp;
for(int i=1;i<n;i++){
temp=list[i];
j=i-1;
while(j>-1 && list[j]>temp) { // work backwards through the array finding
where temp should go
list[j+1]=list[j];
j--;
} //end of inner loop
list[j+1]=temp;
} //end of outer loop
} //end of insertion_sort
30
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 as time-consuming as a swap.
Empirically it’s known that the Insertion sort is over twice as fast as the bubble sort and is just as
easy to implement as the selection sort.
31
When the input array has not been sorted, we have little choice but to do a
linear sequential search that steps through the array sequentially until a
match is found.
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 the list from the beginning until the key is found or the end of the
list is reached.
32
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
an item in A.
Set loc = – 1, if the search is unsuccessful.
Example
33
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 (A[i] == item)
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
34 Efficiency of linear search algorithm runs in O(n) time
int Linear_Search(int list[],int n, 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;
}
35
The time complexity of the linear search is found by a 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).
36
Binary search is an extremely efficient algorithm when it is compared to
linear search.
The binary search technique searches for “item” in the 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
37
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 key to be searched, and then there are the
following three cases.
I. If it is a desired element, then the search is successful.
II. If it is greater than the desired data, then search only the first half of the array, i.e.,
the elements that come to the left side of the middle element.
III. If it is less than the desired data, then search only the second half of the array, i.e.,
the elements that come to the right side of the middle element.
3. Repeat the same step until an element is found or exhausts the search area.
38
39
input “n” elements of the array and the element going to be searched “x”;
initialize i=0 and repeat through step 3 if (i<n)
do step “ 4” while left < right and flag =0
mid = (right + left) / 2;
if array[mid]==x then
flag=1
return mid
end if
if array[mid] < x then
left=mid+1
else
right= mid-1
End of if
if flag = 0
index= -1 // otherwise index=mid
return index
End if
40
int Binary_Search(int list[],int k){ if(found==0)
int left=0; loc=-1;
int right=n-1; else
int found=0; loc=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);
41
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 are 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.
42