Sorting and Searching Algorithms

1. Sorting in General
• Sorting is the process that organizes collections of data into either ascending or descending order.
• Many of the applications you will deal with will require sorting; it is easier to understand data if it
is organized.

• There are two categories of sorting algorithms

- Internal sorting requires that all of your data fit into memory (an array or a LL).
- External sorting is used when your data can't fit into memory all at once (maybe you have
a very large database), and so sorting is done using disk files.

• The efficiency of our algorithms is dependent on the

- number of comparisons we have to make with our keys.
- In addition, we will learn that sorting will also depend on how frequently we must move
items around numerically or alphabetically in order.

Types of Sort Algorithms

1. Selection Sort
Selection sort is a sort algorithm, specifically an in-place comparison sort. It has O(n2) time
complexity, making it inefficient on large lists, and generally performs worse than the similar
insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over
more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

• Imagine the case where we can look at all of the data at once...and to sort it...find the largest item
and put it in its correct place.
• Then, we find the second largest and put it in its place, etc.
• If we were to think about cards again,
– it would be like looking at our entire hand of cards and ordering them by selecting the largest
first and putting at the end, and then selecting the rest of the cards in order of size.

• This is called a selection sort.

- It means that to sort a list, we first need to search for the largest key.
- Because we will want the largest key to be at the last position, we will need to swap the
last item with the largest item.
• The next step will allow us to ignore the last (i.e. largest) item in the list.
– This is because we know that it is the largest item...we don't have to look at it again or move it
again!

• So, we can once again search for the largest item...in a list one smaller than before.
• When we find it, we swap it with the last item (which is really the next to the last item in the
original list).
• We continue doing this until there is only 1 item left.
Here is an example of this sort algorithm sorting five elements:
64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

C++ Implementation
void selectionSort(int A[],int n){
for(int i=0;i<n-1;i++){
int iMin=i;
for(int j=i+1;j<n;j++){
if(A[j]<A[iMin])
iMin=j;
}
if(iMin!=i){
swap(A[i],A[iMin]);
}
}
}

Example 2.
29, 64, 73, 34, 20,
20, 64, 73, 34, 29,
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73

• Selection sort requires both comparisons and exchanges (i.e., swaps).

- Start analyzing it by counting the number of comparisons and exchanges for an array of N
elements.

-Remember the selection sort first searches for the largest key and swaps the last item with
the largest item found.
• Remember that means for the first time around there would be N-1 comparisons.
- The next time around there would be N-2 comparisons (because we can exclude comparing
the previously found largest! Its already in the correct spot!).
- The third time around there would be N-3 comparisons.
- So...the number of comparisons would be: (N-1)+(N-2)+...+ 1 = N*(N-1)/2
• Next, think about exchanges.
• Every time we find the largest...we perform a swap.
• This causes 3 data moves (3 assignments).
• This happens N-1 times!
• Therefore, a selection sort of N elements requires 3*(N-1) moves.
• Lastly, put all of this together: N*(N-1)/2 + 3*(N-1)
• which is: N*N/2 - N/2 + 6N/2 - 3
• which is: N*N/2 + 5N/2 - 3
• Put this in perspective of what we learned about with the BIG O method: 1/2 N*N + O(N)
• Or, O(N2)

• Given this, we can make a couple of interesting observations.

- The efficiency DOES NOT depend on the initial arrangement of the data.
- This is an advantage of the selection sort.
- However, O(N2) grows very rapidly, so the performance gets worse quickly as the number
of items to sort increases.

2. Bubble Sort
Bubble sort, is a simple sort algorithm that repeatedly steps through the list to be sorted, compares
each pair of adjacent items and swap them if they are in the wrong order. The pass through the list
is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is
a comparison sort, is named for the way smaller elements "bubble" to the top of the list. Although
the algorithm is simple, it is too slow and impractical for most problems even when compared to
insertion sort.

• The bubble sort simply compares adjacent elements and exchanges them if they are out of order.
• To do this, you need to make several passes over the data.
• During the first pass, you compare the first two elements in the list.
- If they are out of order, you exchange them.
- Then you compare the next pair of elements (positions 2 and 3).
- If they are out of order, you exchange them.
- This algorithm continues comparing and exchanging pairs of elements until you reach the
end of the list.

• Notice that the list is not sorted after this first pass.
- We have just "bubbled" the largest element up to its proper position at the end of the list!
- During the second pass, you do the exact same thing....but excluding the largest (last)
element in the array since it should already be in sorted order.
- After the second pass, the second largest element in the array will be in its proper position
(next to the last position).

Here is example of bubble sort

First Pass
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does
not swap them.
Second Pass

(14258) (14258)
(14258) ( 1 2 4 5 8 ), Swap since 4 > 2
(12458) (12458)
(12458) (12458)
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm
needs one whole pass without any swap to know it is sorted.
Third Pass

(12458) (12458)
(12458) (12458)
(12458) (12458)
(12458) (12458)
C++ Implementation
void bubbleSort(int B[],int n){
for(int k=0;k<n;k++){
int flag=0;
for(int i=0;i<n-1;i++){
if(B[i]>B[i+1]){
swap(B[i],B[i+1]);
flag=1;
}
}
if(flag==0){
break;
}
}
}

3. Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a
time. It is much less efficient on large lists than more advanced algorithms such as quicksort,
heapsort, or merge sort. However, insertion sort provides several advantages:
 Efficient for (quite) small data sets, much like other quadratic sorting algorithms
 More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as
selection sort or bubble sort
 Adaptive, i.e., efficient for data sets that are already substantially sorted: the time
complexity is O(nk) when each element in the input is no more than k places away from its
sorted position
 Stable; i.e., does not change the relative order of elements with equal keys
 In-place; i.e., only requires a constant amount O(1) of additional memory space
• The insertion sort divides the data into a sorted and unsorted region.
• Initially, the entire list is unsorted.
• Then, at each step, the insertion sort takes the first item of the unsorted region and places it into its
correct position in the sorted region.

Example: The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}. In
each step, the key under consideration is underlined. The key that was moved (or left in place
because it was biggest yet considered) in the previous step is shown in bold.
37495261
37495261
37495261
34795261
34795261
34579261
23457961
23456791
12345679

2. Introduction to Search Algorithms

• A search algorithm is a method of locating a specific item of information in a larger
collection of data. This section discusses two algorithms for searching the contents of an
array.
2.1 The Linear Search
• This is a very simple algorithm.
• It uses a loop to sequentially step through an array, starting with the first element.
• It compares each element with the value being searched for and stops when that value is
found or the end of the array is reached.
Implementation linear search

Function:
int linearSearch(int A[],int n,int key){
for(int i=0;i<n;i++){
if(key==A[i]){
return i;
}
}
return -1;
}

Function for Linked List:

void addbegn(){
node *temp;
temp=new node;
cout<<"Enter Id :";
cin>>temp->id;
cout<<"Enter Age :";
cin>>temp->age;
cout<<"Enter Name :";
cin>>temp->name;
temp->next=NULL;
if(Head == NULL)
Head = temp;
else
{
temp->next = Head;
Head = temp;
}
}
void searchid(){
int k;
cout<<"Enter id you want :"<<endl;
cin>>k;
cout<<"_________________________"<<endl;
node *temp=new node;
if(Head != NULL)
temp=Head;
while(temp != NULL){
if(temp->id == k){
cout<<setw(10)<<"ID"<<setw(14)<<"AGE"<<setw(13)<<"NAME"<<endl;
cout<<setw(10)<<temp->id<<setw(15)<<temp->age<<setw(15)<<temp-
>name<<endl;
cout<<"__________________________"<<endl;
return;
}
temp=temp->next;
}
cout<<"the key is not found!!!!!\n\n";
}
void searchname(){
char k[30];
cout<<"Enter Name You Want :";
cin>>k;
node *temp=new node;
if(Head != NULL)
temp=Head;
while(temp != NULL){
if(strcmp(temp->name,k)==0){
cout<<setw(10)<<"ID"<<setw(14)<<"AGE"<<setw(13)<<"NAME"<<endl;
cout<<setw(10)<<temp->id<<setw(15)<<temp->age<<setw(15)<<temp-
>name<<endl;
cout<<"__________________________"<<endl;
return;
}
temp=temp->next;
}
cout<<"the key is not found!!!!!\n\n";
}
void display(){
node *temp=new node;

if(Head != NULL){
temp=Head;
cout<<"The Elements Are : "<<endl;
cout<<"_______________________"<<endl;
cout<<setw(11)<<"ID"<<setw(16)<<"AGE"<<setw(12)<<"NAME"<<endl;
while(temp != NULL)
{
cout<<setw(10)<<temp->id<<setw(15)<<temp->age<<setw(15)<<temp->name<<endl;
cout<<"-------------------------------------------------"<<endl;
temp=temp->next;
}
cout<<"________________________"<<endl;
}
else
cout<<"the list is empty!!!\n";
}
Efficiency of the Linear Search
• The advantage is its simplicity.
– It is easy to understand
– Easy to implement
– Does not require the array to be in order
• The disadvantage is its inefficiency
– If there are 20,000 items in the array and what you are looking for is in the 19,999th
element, you need to search through the entire list.

2.2 Binary search algorithm

Generally, to find a value in unsorted array, we should look through elements of an array one by
one, until searched value is found. In case of searched value is absent from array, we go through all
elements. In average, complexity of such an algorithm is proportional to the length of the array.
Situation changes significantly, when array is sorted. If we know it, random access capability can be
utilized very efficiently to find searched value quick. Cost of searching algorithm reduces to binary
logarithm of the array length. For reference, log2(1 000 000) ≈ 20. It means, that in worst case,
algorithm makes 20 steps to find a value in sorted array of a million elements or to say, that it
doesn't present it the array.

Binary search is a fast search algorithm with run-time complexity of Οlogn. This search algorithm
works on the principle of divide and conquer. For this algorithm to work properly the data
collection should be in sorted form.
Binary search search a particular item by comparing the middle most item of the collection. If
match occurs then index of item is returned. If middle item is greater than item then item is
searched in sub-array to the right of the middle item other wise item is search in sub-array to the
left of the middle item. This process continues on sub-array as well until the size of sub-array
reduces to zero.

Algorithm
Algorithm is quite simple. It can be done either recursively or iteratively:
1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
• searched value is less, than the middle element. In this case, go to the step 1 for the
part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for
the part of the array, after middle element.
Function:
int binarySearch(int A[],int n,int key){
int low=0;
int high=n-1;
int mid;
while(low<=high){
mid=(low+high)/2;
if(A[mid]==key){
return mid;
}else if(A[mid]<key){
high=mid-1;
}else if(A[mid]>key){
low=mid+1;
}
}
return -1;
}