Mizan-Tepi University
School of Computing and Informatics
Department of Computer Science
Chapter-2
Simple Sorting and Searching Algorithms
By:
Melkamu D. (M.Sc)
May, 2023
MTU, Ethiopia
Mizan-Tepi University
Chapter overview
Simple Sorting algorithms
Selection sort
Bubble sort
Insertion sort
Simple searching algorithms
Linear/sequential searching
Binary searching
Mizan-Tepi University
Sorting algorithms
Sorting
Sorting is the process of reordering a list of items in either
increasing or decreasing order.
Efficiency of sorting algorithm is measured using:
the number of comparisons and
the number of data movements made by the algorithms.
Sorting algorithms are categorized as:
Simple/elementary and
Advanced.(Chapter 7)
Simple sorting algorithms, like Selection sort, Bubble sort and Insertion
sort, are only used to sort small-sized list of items.
Mizan-Tepi University
Selection Sort
Given an array of length n:
Search elements 0 through n-1 and select the smallest.
Swap it with the element in location 0.
Search elements 1 through n-1 and select the smallest.
Swap it with the element in location 1.
Search elements 2 through n-1 and select the smallest.
Swap it with the element in location 2.
Search elements 3 through n-1 and select the smallest.
Swap it with the element in location 3.
Continue in this fashion until there’s nothing left to search.
Mizan-Tepi University
Cont…
i.e. The basic idea is
Loop through the array from i=0 to n-1.
Select the smallest element in the array from i to n
Swap this value with value at position i.
we repeatedly find the next largest (or smallest) element in the array and
move it to its final position in the sorted array.
Note: the list/array is divided into two parts:
the sub-list of items already sorted and
the sub-list of items remaining to be sorted
Mizan-Tepi University
Cont…
Analysis:
The outer loop executes n-1 times 7 2 8 5 4
The inner loop executes about n(n-1)/2
times on average (from n to 2 times) 2 7 8 5 4
Work done in the inner loop is
constant (swap two array elements) 2 4 8 5 7
Time required is roughly (n-1)*[n(n-1)/2]
You should recognize this as O(n2) 2 4 5 8 7
i.e.
How many comparisons? 2 4 5 7 8
(n-1)+(n-2)+…+1 = O(n2)
How many swaps?
n = O(n)
Mizan-Tepi University
Cont…
void selectionSort(int[] a)
{
int i, j, min;
for (i= 0; i <n - 1; i++)
{
int min = i;
for (j = i + 1; j < n; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
if(min!=i) {
swap a[i], a[min];
}}
}//end of function
Mizan-Tepi University
Bubble Sort
Also called Exchange sort
simplest algorithm to implement and the slowest algorithm on very large inputs.
Basic Idea:
Loop through array from i=0 to n and swap adjacent elements if they are out of order.
repeatedly compares adjacent elements of an array.
Compare each element (except the last one) with its neighbor to the right
If they are out of order, swap them
This puts the largest element at the very end
The last element is now in the correct and final place
Compare each element (except the last two) with its neighbor to the right
If they are out of order, swap them
This puts the second largest element next to last
The last two elements are now in their correct and final places
Compare each element (except the last three) with its neighbor to the right
Continue as above until you have no unsorted elements on the left
Mizan-Tepi University
Bubble Sort Example …..Cont…
7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 5 7 4 8 2 4 5 7 8
2 7 5 8 4 2 5 4 7 8
2 7 5 4 8
Mizan-Tepi University
Code for Bubble Sort …Cont…
void bubbleSort(int[] a)
{
int i, j;
for (i = 0; i <n-1; i+++)
flag=0;
{
for (j = 0; j <n-1- i; j++)
{
if (a[j] > a[j + 1]
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag=1;
}
}
}
If(flag==0)
break;
}
Mizan-Tepi University
Analysis for Bubble Sort ...cont’d
Let n = a.length = size of the array
The outer loop is executed n-1 times
Each time the outer loop is executed, the inner loop is executed
Inner loop executes n-1 times at first, linearly dropping to just once
On average, inner loop executes about n(n-1)/2 times for each execution of the outer
loop
In the inner loop, the comparison is always done (constant time), the swap might be
done (also constant time)
Result is (n-1) * [ n(n-1)/2 ] + k, that is, O(n2)
i.e.
How many comparisons?
(n-1)+(n-2)+…+1= O(n2)
How many swaps?
(n-1)+(n-2)+…+1= O(n2)
Mizan-Tepi University
Insertion sort
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.
Basic Idea:
Find the location for an element and move all others up, and insert the
element.
The approach is the same approach that we use for sorting a set of
cards in our hand.
While playing cards, we pick up a card, start at the beginning of our hand
and find the place to insert the new card, insert it and move all the others up
one place.
Mizan-Tepi University
Cont…
The algorithm is as follows
1. The left most value can be said to be sorted relative to itself. Thus, we don’t
need to do anything.
2. Check to see if the second value is smaller than the first one. If it is,
swap these two values. The first two values are now relatively sorted.
3. Next, we need to insert the third value in to the relatively sorted portion
so that after insertion, the portion will still be relatively sorted.
4. Remove the third value first. Slide the second value to make room for
insertion. Insert the value in the appropriate position.
5. Now the first three are relatively sorted.
6. Do the same for the remaining items in the list.
Mizan-Tepi University
Insertion sort example ...cont’d
Sort: 34 8 64 51 32 21
34 8 64 51 32 21
The algorithm sees that 8 is smaller than 34 so it swaps.
8 34 64 51 32 21
51 is smaller than 64, so they swap.
8 34 51 64 32 21
The algorithm sees 32 as another smaller number and moves it to its appropriate
location between 8 and 34.
8 32 34 51 64 21
The algorithm sees 21 as another smaller number and moves into between 8 and 32.
Final sorted numbers:
8 21 32 34 51 64
Mizan-Tepi University
Cont…
void insertionSort(int[] array)
{
int i, j;
for (i =1; i < n; i++)
{
int temp =a[i];
j=i-1;
while (i>= 0 && a[j ] >temp)
{
a[j+1] =a[j];
j--;
}
a[j+1] =temp;
}
}
Mizan-Tepi University
Analysis of Insertion sort ...cont’d
We run once through the outer loop, inserting each of n elements; this is a factor of n
On average, there are n/2 elements already sorted
The inner loop looks at (and moves) half of these
This gives a second factor of n/4
Hence, the time required for an insertion sort of an array of n elements is proportional to
n2/4
Discarding constants, we find that insertion sort is O(n2)
i.e.
How many comparisons?
1+2+3+…+(n-1)= O(n2)
How many swaps?
1+2+3+…+(n-1)= O(n2)
Mizan-Tepi University
Summary of sorting algorithms
Bubble Sort, Selection Sort, and Insertion Sort are all O(n2)
Within O(n2),
Bubble Sort is very slow, and should probably never be used for anything.
Selection Sort is intermediate in speed.
Insertion Sort is usually the fastest of the three--in fact, for small arrays
(like 10 or 15 elements), insertion sort is faster than more complicated
sorting algorithms.
Selection Sort and Insertion Sort are “good enough” for small arrays.
Mizan-Tepi University
Searching algorithms
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.
Two simple searching algorithms:
Sequential / Linear Search, and
Binary Search
Linear Searching
Also called sequential searching
Simplest type of searching process
Easy to implement
Can be used on very small data sets
Not practical for searching large collections
The idea is:
Loop through the array starting at the first/last element until the value of target matches one of the array
elements or until all elements are visited.
If a match is not found, return –1.
Analysis:
Time is proportional to the size of input n
time complexity O(n)
Mizan-Tepi University
Cont…
Algorithm for Sequential/Linear Search
1. Initialize searcharray, key/number to be searched, length
2. Initialize index=0,
3. Repeat step 4 till index<=length.
4. if searcharray[index]=key
return index
else
increment index by 1.
Mizan-Tepi University
Implementation of Linear Searching …cont’d
int linearSearch(int list[ ], int key)
{
int index=0;
int found=0;
do
{
if(key==list[index])
found=1;
else
index++;
}while(found==0&&index<n);
if(found==0)
index=-1;
return index;
}
Mizan-Tepi University
Binary Searching
This searching algorithms works only on an ordered list.
It uses principle of divide and conquer
Though additional cost has to do with keeping list in order, it is more
efficient than linear search
The basic idea is:
Locate midpoint of array to search
Determine if target is in lower half or upper half of an array.
If in lower half, make this half the array to search
If in the upper half, make this half the array to search
Loop back to step 1 until the size of the array to search is one, and this
element does not match, in which case return –1.
Mizan-Tepi University
Cont…
Analysis:
computational time for this algorithm is proportional to log2n
Therefore the time complexity is O(log n)
Algorithm for Binary Search
1. Initialize an ordered array, search_array, key, length.
2. Initialize left=0 and right=length
3. Repeat step 4 till left<=right
4. Middle =(left + right) / 2
5. if search_array[middle]=key
Search is successful
return middle.
else
if key<search_array[middle]
right=middle - 1
else
left=middle + 1.
Mizan-Tepi University
Implementation of binary Searching …cont’d
int Binary_Search(int list[ ],int k)
{
int left=0;
int right=n-1;
int found=0;
do{
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);
if(found==0)
index=-1;
else
index=mid;
return index;
}
Mizan-Tepi University
Analysis of growth functions
nlogn
n
Mizan-Tepi University
End of chapter two
Questions ???
