Chapter 8

Searching and Sorting
Introduction
Searching and Sorting are fundamental operation is computer science.
Searching refers to the operation of finding the location of a given item in a collection
of items.
Sorting refers to the operation of arranging data in some given order, such as
increasing or decreasing, with numerical data, or alphabetically, with character data.
Searching
Type of Searching.
• LINEAR (SEQUENTIAL) SEARCH
• BINARY SEARCH
Linear (Sequential) Search
 The linear search is a conventional method of searching data. The linear search is a
method of searching a target element in a list sequence.
 The expected element is to be searched in the entire data structure in a sequential
method from starting to last element.
 Though, it is simple and straightforward, it has serious limitations. It consumes
more time and reduces the retrieval rate of the system.
 The linear or sequential name implies that the items are stored in systematic
manner. The linear search can be applied on sorted or unsorted linear data structure.
Binary Search
If we have an ordered list and we know how many things are in the list (i.e., number of
records ), we can use a different strategy.
The binary search gets its name because the algorithm continually divides the list into
two parts.
How a Binary Search Works
 Always look at the center value. Each time

you get to discard half of the remaining list.

Is this fast ?
Example:
int binarysearch(int search[],int search_value,int low,int high)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(search[mid]==search_value)
return 1;
else if(search_value<search[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}
Sorting
There are different types of sorting algorithms, the primary ones are:
• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
Bubble Sort
Bubble sort is the most basic way to sort a collection. It works by sequentially going through
your array and comparing two values at a time, swapping them if necessary. It then repeats the
process until no swaps are required .
Bubble Sort
void bubblesort(int sort[],int length)
{
int i,j;
for(i=0;i<length;i++)
{
for(j=0;j<length-i;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
Selection Sort
 The selection sort improves on the bubble sort by making only one exchange for every
pass through the list.
 In order to do this, a selection sort looks for the largest(or minimum) value as it makes
a pass and, after completing the pass, places it in the proper location.
 As with a bubble sort, after the first pass, the largest item is in the correct place. After
the second pass, the next largest is in place.
 This process continues and requires n−1 passes to sort n items, since the final item
must be in place after the (n−1) st pass.
Example
Selection Sort
void selectionsort(int sort[] ,int length)
{
int i , j,min,temp;
for(i=0;i<length-1;i++)
{
min=i;
for(j=i+1;j<length;j++)
{
if(sort[min]>sort[j])
{
min=j;
}
}
temp=sort[i];
sort[i]=sort[min];
sort[min]=temp;
}
}
Insertion Sort
Where a bubble sort relies on a number of small swaps, insertion sort relies on
inserting a single element in the right for a given iteration. Every iteration through the
collection leaves a greater segment sorted.
Insertion Sort
void insertion(int sort[],int length)
{
int i,j;
int temp;
for(i=1;i<length;i++)
{
temp=sort[i];
for(j=i;j>0&&sort[j-1]>temp; j--)
{
sort[j]=sort[j-1];
}
sort[j]=temp;
}
}
Quick Sort
• A more efficient exchange sorting scheme than bubble sort

• Quicksort uses a divide-and-conquer strategy
– A recursive approach
– The original problem partitioned into simpler sub-problems,
– Each sub problem considered independently.
• Subdivision continues until sub problems obtained are simple enough to be solved
directly
Quicksort
• Choose some element called a pivot

• Perform a sequence of exchanges so that
– All elements that are less than this pivot are to its left and
– All elements that are greater than the pivot are to its right.
• Divides the (sub)list into two smaller sub lists,
• Each of which may then be sorted independently in the same way.
Quicksort Example
• Given to sort:
75, 70, 65, 84, 98, 78, 100, 93, 55, 61, 81, 68
• Select, arbitrarily, the first element, 75, as pivot.
• Search from right for elements <= 75, stop at first element <=75
• Search from left for elements > 75, stop at first element >75
• Swap these two elements, and then repeat this process
Quicksort Example
75, 70, 65, 68, 61, 55, 100, 93, 78, 98, 81, 84
• When done, swap with pivot

• This SPLIT operation placed pivot 75 so that all elements to the left were <= 75
and all elements to the right were >75.
• 75 is now placed appropriately
• Need to sort sublists on either side of 75
Quicksort Example
• Need to sort (independently):

55, 70, 65, 68, 61 and
100, 93, 78, 98, 81, 84
• Let pivot be 55, look from each end for values larger/smaller than 55, swap
• Same for 2nd list, pivot is 100
• Sort the resulting sublists in the same manner until sublist is trivial (size 0 or 1)
• View quicksort() recursive function
Quick Sort
int quicksort(int sort[],int low,int high )
{
int i,j, temp,num;
if(low>=high)
return -1;
i=low-1; j=high;
num=sort[high];
while(i<j)
{
while(sort[++i]<num);
while(j>=0 && sort[--j]>num);
if(i<j)
{
temp=sort[i];
sort[i]=sort[j];
sort[j]=temp;
}
}
temp=sort[i];
sort[i]=sort[high];
sort[high]=temp;
quicksort(sort,low,i-1);
quicksort(sort,i+1,high);
}

Chapter 8

Uploaded by

Copyright:

Available Formats

Chapter 8

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 8

Uploaded by

Copyright:

Available Formats

Searching and Sorting

Searching and Sorting are fundamental operation is computer science.

• LINEAR (SEQUENTIAL) SEARCH

 Always look at the center value. Each time

• A more efficient exchange sorting scheme than bubble sort

• Choose some element called a pivot

• When done, swap with pivot

• Need to sort (independently):

You might also like