Searching and Sorting Algorithms
Searching is common task computers perform.
- whether the list is sorted
- whether all the elements in the list are unique or have duplicate values.
Linear Search(for unsorted lists)
The simplest way to find an element in a list is to check if it matches the
required after value.
Worst case: when the value is in the last position or not found(the entire list
must be searched linearly).
Average case: requires searching half of the list.
Best case: when the value is in the first position in the list
Algorithm:
for all elements in the list do
if element == value_to_find
then return position_of(element)
end # if
end # for
If the list has duplicate elements, you cannot assume that once one element is
found, the search is done, thus you need to continue searching through the entire
list.
//linear search function that searches the key in arr
int linearSearch(int *arr, int size, int key)
{
// starting traversal
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
int main()
{
int arr[10] = {3,4,1,7,5,8,11,42,3,13};
int size = sizeof(arr)/sizeof[0]);
int key = 4;
//calling linearSearch
int index = linearSearch(arr,size,key);
//printing result based on value returned by linearSearch()
if(index == -1) {
printf("The element is not present in the arr.");
}
else {
printf("The element is present at arr[%d].", index);
}
return 0;
}
Binary Search(for sorted lists)
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
// Repeat until low and high meet each other
while (low <= high) {
int mid = low + (high-low)/2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3,4,5,6,7,8,9};
int n = sizeof(array) /sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n-1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}
Sorting Algorithms
Sorting in non-decreasing order.
Sorting in non-increasing order.
Issues in Sorting techniques
How to rearrange a given set of data?
Which data structures are more suitable to store data prior to their sorting?
How fast the sorting can be achieved?
How sorting can be done in memory constraint situation?
How to sort various types of data?
Sorting by Comparison
A data item is compared with other items in the list of items in order to find its
place in the sorted list.
Insertion
From a given list of items, one item is considered at a time.
The item chosen is then inserted into an appropriate position relative to the
previously sorted items of the same list or to a d/t list.
Insertion Sort
Compare and shift till x[i] is larger.
void insertionSort (int list[], int size)
{
int i,j,item;
for (i=1; i<size; i++)
{
item = list[i] ;
for (j=i-1; (j>=0)&& (list[j] > item); j--)
list[j+1] = list[j];
list[j] = item;
}
}
int main ()
{
int x [] = {-45, 89,-65,87,0,3,,-23,19,56,21,76,-50);
int i;
for (i = 0; i<12; i++)
printf("%d ", x[i]);
printf("\n");
insertionSort(x,12);
for(i=0;i<12;i++)
printf("%d ", x[i]);
printf("\n");
}
Selection
First the smallest(or largest) item is located and it is separated from the rest;
then the next smallest(or net largest) is selected and so on until all item are
separated.
Selection Sort, Heap Sort
Selection Sort
find smallest element, mval, in x[k....size-1]
swap smallest element with x[k], then increase k.
/* Yield location of smallest element in x[k...size-1];*/
int findMinLoc (int x[], int k, int size)
{
int j, pos; /* x[pos] is the smallest element found so far */
pos = k;
for (j=k+1; j<size; j++)
if (x[j] < x[pos])
pos = j;
return pos;
}
/* The main sorting function */
/* Sort x[0...size-1] in non-decreasing order */
int selectionSort (int x[], int size)
{
int k, m;
for (k=0; k<size-1; k++)
{
m = findMinLoc(x, k, size);
temp = a[k];
a[k] = a[m];
a[m] = temp;
}
}
Exchange
If two items are found to be out of order, they are interchanged. The process is
repeated until no more exchange is required.
Bubble Sort, Shell Sort, and Quick Sort
Bubble Sort
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void bubble_sort(int x[], int n)
{
int i,j;
int flag = 0;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++)
if (x[j] > x[j+1])
{
swap(&x[j], &x[j+1]);
flag = 1;
}
if (flag == 0)
return;
}
}
int main()
{
int x[] = {-45, 89,-65,87,0,3,-23,19,56,21,76,-50);
int i;
for (i = 0; i<12; i++)
printf("%d ",x[i];
printf("\n");
bubble_sort(x,12);
for (i=0;i<12;i++)
printf("%d ", x[i]);
printf("\n");
}
Quick Sort
here code
Enumeration
Two or more input lists are merged into an output list and while merging the items,
an input list is chosen following the required sorting order.
Merge Sort
here code
Sorting by Distribution
All items under sorting are distributed over an auxiliary storage space based on
the constituent element in each and then grouped them together to get the sorted
list.
Distributions of items based on the ff choices.
Radix: An item is placed in a space decided by the bases (or radix) of its
components with which it is composed of.
Counting: Items are sorted based on their relative counts.
Hashing: Items are hashed, that is dispersed into a list based on hash function.
Efficient Sorting algorithms
Basic concept of divide and conquer method:
sort (list)
{
if the list has length greater than 1
{
Partition the list into lowlist and highlist;
sort(lowlist);
sort(highlist);
combine(lowlist, highlist);
}
}
Quick Sort: hard division, easy combination
partition in the divide step of the divide and conquer framework
hence combine step does nothing
an equal sub division is not guaranteed.
Merge Sort: easy division, hard combination
merge in the combine step
the divide step in this frame work does one simple calculation only.
two sub problems are of almost equal size always.
The difference b/t the two sorting methods appears as the deciding factor of their
run time performances.
