SORTING:
Sorting means arranging
the data in ascending or descending order using various Sorting algorithms.
Sorting arranges data in a sequence which makes searching easier.
Usage:
An important key to algorithm design is to use
sorting as a basic building block, because once a set of items is sorted, many
other problems become easy.
Common
Applications of Sorting:
- Searching - Binary search enables you to test whether an item is in a dictionary in O (lg n) time, once the keys are all sorted. Search pre-processing is perhaps the single most important application of sorting.
- Closest pair - Given a set of n numbers, how do you find the pair of numbers that have the smallest difference between them? After the numbers are sorted, the closest pair of numbers will lie next to each other somewhere in sorted order.
- Element uniqueness - Are there any duplicates in a given a set of nitems? The most efficient algorithm is to sort them and then do a linear scan though them checking all adjacent pairs.
- Frequency distribution - Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting.
- Selection - What is the kth largest item in the set? If the keys are placed in sorted order in an array, the kth largest can be found in constant time by simply looking at the kth position of the array.
- Convex hulls - Given n points in two dimensions, what is the polygon of smallest area that contains them all? The convex hull is like a rubber band stretched over the points in the plane and then released. But how can we use sorting to construct the convex hull? Once you have the points sorted by x-coordinate, the points can be inserted from left to right into the hull. Since the rightmost point is always on the boundary, we know that it will be inserted into the hull. Adding this new rightmost point might cause others to be deleted, but we can quickly identify these points because they lie inside the polygon formed by adding the new point. These points to delete will be neighbours of the previous point we inserted, so they will be easy to find. The total time is linear after the sorting has been done.
Real World Applications of Sorting:
·
Merge
Sort: Databases use an external merge sort to sort set of data that are
too large to be loaded entirely into memory. The driving factor in this sort is
the reduction in the number of disk I/Os.
·
Bubble
Sort: Bubble sort is used in programming TV remote to sort channels on the
basis of longer viewing time.
·
Heap Sort: Heap
sort is used in reading barcodes on plastic cards. The service allows to
communicate with the database to constantly run checks to ensure that they were
all still online and had to constantly report statistics on which readers were
performing the worst, which ones got the most/least user activity, etc.
·
Quick
Sort: Sports scores are organised by quick sort on the basis of win-loss
ratio.
·
Radix Sort: eBay
allows you to sort listings by the current Bid amount leveraging radix sort.
·
Selection
Sort: K12 education portal allows sorting list of pupils alphabetically
through selection sort.
Different Sorting Algorithms
Ø
Bubble Sort
Ø
Selection Sort
Ø
Insertion Sort
Ø
Merge Sort
Ø
Quick Sort
Ø
Heap Sort
Ø
Bucket Sort
Ø
Radix Sort
Ø
Tim Sort
Ø
Shell Sort
Ø
Address Calculation Sort
Algorithm
|
Best Time Complexity
|
Average Time Complexity
|
Worst Time Complexity
|
Worst Space Complexity
|
Bubble Sort
|
O(n)
|
O(n^2)
|
O(n^2)
|
O(1)
|
Selection Sort
|
O(n^2)
|
O(n^2)
|
O(n^2)
|
O(1)
|
Insertion Sort
|
O(n)
|
O(n^2)
|
O(n^2)
|
O(1)
|
Merge Sort
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Quick Sort
|
O(nlogn)
|
O(nlogn)
|
O(n^2)
|
O(logn)
|
Heap Sort
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(1)
|
Bucket Sort
|
O(n+k)
|
O(n+k)
|
O(n^2)
|
O(nk)
|
Radix Sort
|
O(nk)
|
O(nk)
|
O(nk)
|
O(n+k)
|
Tim Sort
|
O(n)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Shell Sort
|
O(n)
|
O((nlog(n))^2)
|
O((nlog(n))^2)
|
O(1)
|
Address Calculation Sort
|
O(n)
|
O(n^2)
|
O(n^2)
|
O(1)
|
BUBBLE SORT:
Bubble
Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in wrong order.
Code:
boolean swapped =
true;
for(int
j=arr.length-1; j>=0 && swapped; j--)
{
swapped
= false;
for(int
k=0; k<j; k++)
{
if(arr[k]
> arr[k+1])
{
int
temp = arr[k];
arr[k]
= arr[k+1];
arr[k+1]
= temp;
swapped
= true;
}
}
}
Advantage of bubble sort over other sorting techniques:
àit can detect whether
the input is already sorted i.e Best case time complexity is O(n)
Disadvantage:
its poor efficiency when dealing with a huge list of items.
selection
sort:
The selection sort
algorithm sorts an array by repeatedly finding the minimum element from
unsorted part and putting it at the beginning.
Code:
for
(i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] <
arr[min_idx])
{
min_idx = j;
int temp = arr[min_idx];
arr[min_idx]
= arr[i];
arr[i] = temp;
}
}
}
Advantage
: it performs well on a small list.
Disadvantage:
its poor efficiency when dealing with a huge list of items.
Insertion
Sort:
Insertion sort is a simple
sorting algorithm that works the way we sort playing cards in our hands.
CODE:
int i, key, j;
for
(i = 1; i < n; i++)
{
key
= arr[i];
j
= i-1;
while
(j >= 0 && arr[j] > key)
{
arr[j+1]
= arr[j];
j = j-1;
}
arr[j+1]
= key;
}
Advantage:
The insertion
sort is an in-place sorting algorithm so the space requirement is minimal.
Disadvantage:
The insertion
sort does not deal well with a huge list.
Merge
Sort:
Merge Sort is a Divide and
Conquer algorithm. It divides input array in two halves, calls itself for
the two halves and then merges the two sorted halves.
CODE:
void mergesort(int a[],int
i,int j)
{
int mid;
if(i<j)
{
mid=(i+j)/2;
mergesort(a,i,mid); //left
recursion
mergesort(a,mid+1,j); //right
recursion
merge(a,i,mid,mid+1,j); //merging
of two sorted sub-arrays
}
}
void merge(int a[],int
i1,int j1,int i2,int j2)
{
int temp[50],int i,j,k;
i=i1; //beginning of
the first list
j=i2; //beginning of
the second list
k=0;
while(i<=j1 && j<=j2) //while
elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=j1) //copy remaining
elements of the first list
temp[k++]=a[i++];
while(j<=j2) //copy remaining
elements of the second list
temp[k++]=a[j++];
//Transfer elements from temp[] back
to a[]
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j];
}
Advantage: It can be applied to files of
any size.
Disadvantage: Merge Sort requires more space
and less efficient than other sort.
QuickSort:
QuickSort is a Divide
and Conquer algorithm. It picks an element as pivot and partitions the given
array around the picked pivot. There are many ways to pick as a pivot like
pick first element as pivot, pick last element as pivot, Pick median as pivot
,Pick a random element as pivot.
Put the all smaller
elements before pivot, and put all greater elements after pivot.
CODE:
void quick_sort(int a[],int
l,int u)
{ int
j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(int a[],int
l,int u)
{
int v,i,j,temp;
v=a[l], i=l, j=u+1;
do
{ do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i]; a[i]=a[j]; a[j]=temp;
}
}while(i<j);
a[l]=a[j]; a[j]=v;
return(j);
}
Advantage:
It is able to
deal well with a huge list of items.(best sorting algorithm)
Disadvantage:
Ø
If
the list is already sorted than bubble sort is much more efficient than quick
sort
Ø
If
the sorting element is integers than radix sort is more efficient than quick
sort.
Heap
Sort:
Ø Heap
sort is a comparison based sorting technique based on Binary Heap data structure. A
complete binary tree is a binary tree in which every level, except possibly the
last, is completely filled, and all nodes are as far left as possible.
Ø CODE:
Ø void HeapSort(int heap[],int n)
{
int t,i;
for(i=n;i>=1;i--)
{
build_heap(heap,i);
t=heap[1];
heap[1]=heap[i];
heap[i]=t;
}
}
{
int t,i;
for(i=n;i>=1;i--)
{
build_heap(heap,i);
t=heap[1];
heap[1]=heap[i];
heap[i]=t;
}
}
Ø void build_heap(int H[],int n)
{
int i,j,k,v,heap;
for(i=n/2;i>=1;i--)
{
k=I; v=H[k]; heap=0;
while(heap==0 && (2*k)<=n)
{ j=2*k;
if(j<n)
{ if(H[j]<H[j+1]) j++; }
if(v>=H[j]) heap=1;
else
{ H[k]=H[j]; k=j; }
}
H[k]=v;
}
}
{
int i,j,k,v,heap;
for(i=n/2;i>=1;i--)
{
k=I; v=H[k]; heap=0;
while(heap==0 && (2*k)<=n)
{ j=2*k;
if(j<n)
{ if(H[j]<H[j+1]) j++; }
if(v>=H[j]) heap=1;
else
{ H[k]=H[j]; k=j; }
}
H[k]=v;
}
}
Ø Advantage: The Heap sort algorithm is widely
used because of its efficiency.
Ø Disadvantage: Heap sort requires more space for
sorting.
No comments:
Post a Comment