DDIT

Chapter Two
Elementary Sorting and Searching Algorithms
2.1 Searching
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 simple searching algorithms:
• Sequential Search, and

• Binary Search

2.1.1. Linear Search (Sequential Search)

Pseudo code
Loop through the array starting at the first element until the value of target matches one of the array
elements.
If a match is not found, return –1.
Time is proportional to the size of input (n) and
We call this time complexity O(n)
Example Implementation:
intLinear Search(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;
}

Page 1 of 8
 DDIT

2.1.2. Binary Search

This searching algorithms work only on an ordered list.
The basic idea is:
• Locate midpoint of array to search

• Determine if target is in lower half or upper half of an array.

o If in lower half, make this half the array to search
o 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.
The computational time for this algorithm is proportional to log2 n
Therefore the time complexity is O(log n)
Example Implementation:
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;
}

2.2. Sorting Algorithms

Page 2 of 8
 DDIT

Sorting is one of the most important operations performed by computers. Sorting is a process of
reordering a list of items in either increasing or decreasing order. The following are simple sorting
algorithms used to sort small-sized lists.
 Insertion Sort
 Selection Sort
 Bubble Sort

2.2.1. Insertion Sort

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. While playing cards, you pick up a card, start at the beginning
of your hand and find the place to insert the new card, insert it and move all the others up one place.
Basic Idea:
Find the location for an element and move all others up, and insert the element. The process
involved in insertion sort 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.
Implementation
void insertion_sort(int list[])
{

Page 3 of 8
 DDIT

int temp;
for(int i=1;i<n; i++){
temp= list[i];
for(int j=i; j>0 && temp<list[j-1];j--)
{ // work backwards through the array finding where temp should go
list[j]=list[j-1];
list[j-1]=temp;
}//end of inner loop
}//end of outer loop
}//end of insertion_sort

Analysis
How many comparisons?
1+2+3+…+(n-1)= n(n-1)/2=O(n2)
How many swaps?
1+2+3+…+(n-1)= O(n2)
How much space? In-place algorithm
Example 2.1 Sort the following list using insertion sort algorithm by showing
the necessary steps and intermediate form of the array bellow.
5 9 3 1 7 6 4 8 2

Solution:
i =1, temp=list[i]=list[1]=9
i=2, temp=list[2]=3
j Swa List[9]
p
j Swa List[9]
1 p- 5 9 3 1 7 6 4 8 2
Page 4 of 8
2 (9,3 5 3 9 1 7 6 4 8 2
)
1 (5,3 3 5 9 1 7 6 4 8 2
)
 DDIT

i=3,temp=list[2]=1 i=7, temp= list[7] = 8

j Swa List[9]
p j Swa List[9]
3 (9,1 3 5 1 9 7 6 4 8 2 p
) 8 (9,2 1 3 4 5 6 7 8 2 9
2 (5,1 3 1 5 9 7 6 4 8 2 )
i=4, 7 (8,2 1 3 4 5 6 7 2 8 9
)
)
1 (3,1 1 3 5 9 7 6 4 8 2 temp=
) 6 (7,2 1 3 4 5 6 2 7 8 9
)
list[4]= 7
5 (6,2 1 3 4 5 2 6 7 8 9
) i=8,
j Swa List[9]
4 (5,2 1 3 4 2 5 2 7 8 9
p
)
4 (9,7 1 3 5 7 9 6 4 8 2
3 (4,2 1 3 2 4 5 2 7 8 9
)
)
3 - 1 3 5 7 9 6 4 8 2
2 (3,2 1 2 3 4 5 2 7 8 9
2 - 1 3 5 7 9 6 4 8 2 )
1 - 1 3 5 7 9 6 4 8 2 1 - 1 2 3 4 5 2 7 8 9
i=5,
temp = list[5] =6 temp = list[8]= 2

j Swa List[9]
p
5 (9,6 1 3 5 7 6 9 4 8 2
)
4 (7,6 1 3 5 6 7 9 4 8 2
)
3 - 1 3 5 6 7 9 4 8 2
2 - 1 3 5 6 7 9 4 8 2
1 - 1 3 5 6 7 9 4 8 2
i=6 , temp= list[6] = 4

j Swa List[9]
p
6 (9,4 1 3 5 6 7 4 9 8 2
)
5 (7,4 1 3 5 6 4 7 9 8 2
)
4 (6,4 1 3 5 4 6 7 9 8 2
2.2.2. Selection Sort )
3 (5,4 1 3 4 5 6 7 9 8 2
Basic Idea: )
2 - 1 3 4 5 6 7 9 8 2
 Loop through the array from i=0 to n-1. 1
j -
Swa 1 3 4 5List[9]
6 7 9 8 2
p
 Select the smallest element in the array from 7 (9,8 1 3 4 5 6 7 8 9 2 i+1
)
to n
6 - 1 3 4 5 6 7 8 9 2
 Swap this value with value at position i. 5 - 1 3 4 5 6 7 8 9 2
4 - 1 3 4 5 6 7 8 9 2
3 - 1 3 4 5 6 7 8 9 2
Page 5 of 8
2 - 1 3 4 5 6 7 8 9 2
1 - 1 3 4 5 6 7 8 9 2
 DDIT

Implementation:
void selection_sort(int list[])
{
int i,j, smallest;
for(i=0;i<n-1;i++){
smallest=i;
for(j=i+1;j<n;j++){
if(list[j]<list[smallest])
smallest=j;
}//end of inner loop
temp=list[smallest];
list[smallest]=list[i];
list[i]=temp;
} //end of outer loop
}//end of selection_sort
Analysis
How many comparisons?
(n-1)+(n-2)+…+1= O(n2)
How many swaps?
n=O(n)
Example 2.1 Sort the following list using selection sort algorithm by showing
the necessary steps and intermediate form of the array bellow.
5 9 3 1 7 6 4 8 2
Solution
j( i+1 to n -1) Initial list i(from 0 to n-2)
J 0 1 2 3 4 5 6 7 8
1 5 1 1 1 1 1 1 1 1 1
2 9 9 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3
4 1 5 5 5 4 4 4 4 4 4
5 7 7 7 7 7 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 6
7 4 4 4 4 5 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8
9 2 2 9 9 9 9 9 9 9 9

Page 6 of 8
 DDIT

2.2.3. Bubble Sort

Bubble sort is the 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.
Implementation:
voidbubble_sort(list[])
{
inti,j,temp;
for(i=0;i<n; i++){
for(j=n-1;j>i; j--){
if(list[j]<list[j-1]){
temp=list[j];
list[j]=list[j-1];
list[j-1]=temp;
}//swap adjacent elements
}//end of inner loop
}//end of outer loop
}//end of bubble sort
Analysis of Bubble Sort
How many comparisons?
(n-1)+(n-2)+…+1= O(n2)
How many swaps?
(n-1)+(n-2)+…+1= O(n2)
Exercise: Sort the following list using bubble sort algorithm by showing the
necessary steps and intermediate form of the array bellow.
5 9 3 1 7 6 4 8 2
General Comments

Page 7 of 8
 DDIT

Each of these algorithms requires n-1 passes: each pass places one item in its correct place. The ith
pass makes either i or n - i comparisons and moves. So: or O(n2). Thus these algorithms are only
suitable for small problems where their simple code makes them faster than the more complex code
of the O(nlogn) algorithm. As a rule of thumb, expect to find an O(nlogn) algorithm faster for n>10 -
but the exact value depends very much on individual machines!.
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. In short, there really isn't any reason to use the selection sort - use
the insertion sort instead.
If you really want to use the selection sort for some reason, try to avoid sorting lists of more than a
1000 items with it or repetitively sorting lists of more than a couple hundred items.

Question: What is the deference between selection sort and bubble sort?

Page 8 of 8