SORTING
Definition : Sorting is a process of storing data in sorted order. It can be done in both ascending and descending order. Sorting arranges the data in a sequence which makes searching easier and saves time and memory space.
Different Types of Sorting Algorithm :
1.Bubble Sort
2.Selection Sort
3.Insertion Sort
4.Quick Sort
5.Merge Sort
6.Heap Sort
Bubble Sort : Bubble sort is one of the simplest sorting algorithm . It works by repeatedly swapping and comparing the adjacent elements and moving the largest element to the highest index position (for ascending order ) of the array segment if they are placed in wrong order. This process will continue till the entire array is sorted. It can be sorted in both ascending and descending order.
*** If the elements are to be sorted in descending order, then in first pass the smallest element is moved to the highest index of the array.
Algorithm of Bubble Sort :
Bubblesort(a,n) :
Step 1: Repeat Step 2 For 1 = 0 to n-1
Step 2: Repeat For j = 0 to n - i
Step 3: IF A[j] > A[j + 1]
SWAP A[j] and A[j+1]
[END OF INNER LOOP]
[END OF OUTER LOOP]
Step 4: EXIT
C Program For Bubble Sort On Code Blocks :
#include<stdio.h>
int main()
{
int a[20],n,i,j,temp;
printf("How many data do you want to sort.\n");
scanf("%d",&n);
printf("Enter a number one by one.\n");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
for(i=0; i<n-1; i++)
{
for(j=0; j<n-1-i; j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("The sorted array. ");
for(i=0; i<n; i++)
printf("%d \n",a[i]);
return 0;
}
Example:
The number of comparisons is in each pass n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,,
Thus, the output
(n – 1) +( n – 2) + . . . . . + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
SELECTION SORT
Definition: A Selection Sort is a Sorting algorithm which finds the smallest element in the array and swaps with the first element then with the second element and continues until the entire array is sorted. It sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
***It sorts the numbers of an array in ascending order. With a little modification, it arranges numbers in descending order.
Algorithm For Selection Sort in C:
Algorithm Selectl(a, n, k):
// Selects the kth-smallest element in a[1:n] and places it
// in the kth position of a[].The remaining elements are
// rearranged such that a[m] <a[k] for 1< m <k, and
// a[m] >a[k] for k < m <n.
{
low :=1; up :=n +1;
a[n+ 1]:=infinity; // a[n+1] is set to infinity.
repeat
{
// Each time the loop is entered,
// 1<low <k <up<n+ 1.
j :=Partition(a,low,up)',
// j is such that a[j] is the jth-smallest value in a[].
if (k = j) then return;
else if (k <j) then up :=j; // j is the new upper limit.
else low :=j +1; // j +1is the new lower limit.
}
until(false); }
Programming of Selection Sort On Code Blocks :
#include<stdio.h>
int main()
{
int n,a[20],i,j,m,t;
printf("How many elements do you want to execute.");
scanf("%d",&n);
printf("Enter the elements ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
m=i;
for(j=i;j<n;j++)
{
if(a[m]>a[j])
m=j;
}
t=a[m];
a[m]=a[i];
a[i]=t;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
Example:
Time Complexity For Selection Sort:
Average-case performance: O(n2)
Best-case performance: О(n2)
Worst-case performance: О(n2)
Space Complexity :O(1)
INSERTION SORT
Definition: It is a simple and efficient sorting algorithm. Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order.
The analogy can be understood from the style we arrange a deck of cards. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put at their right place.
Algorithm For Insertion Sort:
INSERTION SORT(A):
for i = 1 to n
key ← A [i]
j ← i – 1
while j > = 0 and A[j] > key
A[j+1] ← A[j]
j ← j – 1
End while
A[j+1] ← key
End for
C Program For Insertion Sort On Code Blocks :
#include<stdio.h>
int main()
{
int n,a[20],i,m,t;
printf("How many number do you want to execute.");
scanf("%d",&n);
printf("Enter the elements one by one.");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
m=i;
while(m>0 && a[m-1]>a[m])
{
t=a[m];
a[m]=a[m-1];
a[m-1]=t;
m--;
}
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
Example:
Time Complexity of Insertion Sort :
If, we provide a sorted array to the insertion sort algorithm .It executes the outer loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
For an unsorted array, it takes for an element to compare with all the other elements which mean every n element compared with all other n elements. Thus, making it for n x n, i.e., n2 comparisons.
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
Definition: Quicksort is based on a divide and conquer method.
It works recursively, by first selecting a random “PIVOT VALUE” from the array.
Then the partition function works in a way that the elements that are less than pivot value is placed left of pivot value and the elements are greater is placed right of the pivot value, it works recursively until the elements are placed in sorted order.
Quicksort, sometimes called partition-exchange sort.
Algorithm for Quick Sort:
a) Algorithm for partition the unsorted array.
Partition(a,lb,ub)
{
pivot=a[lb];
start=lb; // pivot is a random value.
end=ub; //lb is lower bound of array & ub is upper bound.
while(start<end)
{
while(a[start]<=pivot)
start++;
while(a[end]>pv)
end--;
if(start<end)
{
temp=a[start]; // swapping function works.
a[start]=a[end];
a[end]=temp;
}
}
temp=a[lb];
a[lb]=a[end];
a[end]=temp; // swapping the pivot value with end value.
return end; }
b) Algorithm for Quick sort:
quicksort(a,lb,ub)
{
if(lb<ub)
{ // loc is location return by a partition function.
loc=partition(a,lb,ub); // function is calling for partition.
quicksort(a,lb,loc-1);
quicksort(a,loc+1,ub);
}
}
Code for Quick Sort:
#include<stdio.h>
int partition(int *,int ,int);
void quicksort(int *,int,int);
int main()
{
int a[20],i,n;
printf("How many number do u want to execute. ");
scanf("%d",&n);
printf("Enter the element one by one. ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
quicksort(a,0,n-1); // calling the quick sort.
printf("Order of Sorted elements: ");
for(i=0;i<n;i++)
printf(" %d",a[i]);
return 0;
}
int partition(int a[],int lb,int ub)
{
int temp;
int pv=a[lb];
int start=lb; // pv is a random pivot value, in our case 1st element is pivot element.
int end=ub;
while(start<end)
{
while(a[start]<=pv)
{
start++;
}
while(a[end]>pv)
{
end--;
}
if(start<end)
{
temp=a[start]; // swapping function works.
a[start]=a[end];
a[end]=temp;
}
}
temp=a[lb];
a[lb]=a[end];
a[end]=temp;
return end;
}
void quicksort(int a[],int lb,int ub)
{
int loc;
if(lb<ub) // loc is location return by the partition function.
{
loc=partition(a,lb,ub); // function is calling for partition.
quicksort(a,lb,loc-1);
quicksort(a,loc+1,ub);
}
}
Example of the Quick Sort :
Time Complexity for Quick Sort:
Worst Case [ Big-O ]: O(n2)
Best Case [Big-omega]: O(nlog n)
Average Case [Big-theta]: O(nlog n)
Space Complexity: O(nlog n)
MERGE SORT
Definiton: Merge Sort is a type of Divide and Conquer Method.
It is one of the most popular sorting algorithms which call recursive algorithms.
In this sorting, we divide the array recursively in two halves, until each sub-array contains a single element, and
then we merge the sub-array in a way that it results into a sorted array.
*** Merge sort having two functions
a)Mergesort() function which can divide the array into the sub-array,
b)Merge() function which can merge two sub-array in a way that it results into a sorted array.
Algorithm for Merge sort:
a) For Divide the Array:
void merge_sort (int A[ ] , int low , int high ):
{
if( low < high )
{
int mid = (low + high ) / 2 ; // defines the current array in 2 parts .
merge_sort (A, low , mid ) ; // sort the 1st part of array .
merge_sort (A,mid+1 , high ) ; // sort the 2nd part of array.
// merge the both parts by comparing elements of both the parts.
merge(A,low , mid , high );
}
}
b) For Merge the Sub-Array:
void merge(int A[ ] , int low, int mid, int high):
{
//stores the starting position of both parts in temporary variables.
int p = low ,q = mid+1;
int Arr[high-low+1] , k=0;
for(int i = low ;i <= high ;i++)
{
if(p > mid) //checks if first part comes to an end or not .
Arr[ k++ ] = A[ q++] ;
else if ( q > high) //checks if second part comes to an end or not
Arr[ k++ ] = A[ p++ ];
else if( A[ p ] < A[ q ]) //checks which part has smaller element.
Arr[ k++ ] = A[ p++ ];
else
Arr[ k++ ] = A[ q++];
}
for (int p=0 ; p< k ;p ++)
{
/* Now the real array has elements in sorted manner including both
parts.*/
A[ low++ ] = Arr[ p ] ;
}
}
Code for Merge Sort in C:
#include <stdio.h>
void merge(int [], int, int, int);
void mergeSort(int [],int, int);
int main()
{
int a[50],i,n;
printf("How many number do you want to execute. ");
scanf("%d", &n);
printf("Enter the elements one by one. ");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
mergeSort(a, 0, n - 1);
printf("After merge sort:\n");
for(i = 0;i < n; i++)
{
printf("%d ",a[i]);
}
return 0;
}
void mergeSort(int a[],int low,int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
mergesort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
void merge(int a[],int low,int mid,int high)
{
int i, mi, k, lo, b[50];
lo = low;
i = low;
mi = mid + 1;
while ((lo <= mid) && (mi <= high))
{
if (a[lo] <= a[mi])
{
b[i] = a[lo];
lo++;
}
else
{
b[i] = a[mi];
mi++;
}
i++;
}
if (lo > mid)
{
for (k = mi; k <= high; k++)
{
b[i] = a[k];
i++;
}
}
else
{
for (k = lo; k <= mid; k++)
{
b[i] = a[k];
i++;
}
}
for (k = low; k <= high; k++)
{
a[k] = b[k];
}
}
Example:
Time Complexity for Merge Sort:
Worst Case : O(nlog n)
Best Case : O(nlog n)
Average Case: O(nlog n)
HEAP SORT
Definition: A binary heap is a complete binary tree in which every node satisfies the property which:
If B is a child of A, then heap(A) ≥heap(B)
It means that elements at every node will be either greater than or equal to the element is placed at its right side and less than the element is placed at its left side.
Heap is of two types a) Max Heap
b) Min Heap
Max Heap: The root node has the highest key value in the heap. Such a heap is known as a max-heap.
Example:
Min Heap: The root has the lowest key value. Such a heap is called a min-heap.
Example:
Working Principle:
The heap sort begins by building heap tree(by default max-heap), then removing the largest element and placing it at the end of the sorted array. Then reconstructs the heap and removes the largest remaining element and places it in the next open position. This is repeated until there is no element left in the heap and the sorted array is full.
Algorithm for Heap Sort: It has three functions for sorting :
a) Insert the elements to the heap.
b) Delete the elements to the heap.
c) Heap Sort.
a) INSERTION:
INSHEAP(TREE, N, HEAP):
[Add new node to H and initialize PTR]
Set N: N+1 and PTR: =N
[Find location to insert VALUE]
[Find location to insert VALUE]
Set PAR:=[PTR/2] {Location of parent node}
If VALUE <=TREE[PAR],Then:
Set TREE[PTR]:=VALUE ,and return
Set TREE[PTR]:=TREE[PAR]
Set PTR:=PAR
[End of step 2 loop]
[Assign VALUE as the root of H]
Set TREE[1]:=VALUE
Return
b) DELETION:
c) DELHEAP(TREE,N,VALUE):
Set VALUE:=TREE[1]
Set LAST:=TREE[N] and N :=N-1
Set PTR:=1,LEFT:=2 and RIGHT:=3
Repeats steps 5 to 7 while RIGHT<=N:
If LAST >=TREE[LEFT] and LAST>=TREE [RIGHT], then:
Set TREE[PTR]:=LAST and return
If TREE [RIGHT]<=TREE[LEFT],then:
Set TREE[PTR]:=TREE[LEFT] and PTR:=LEFT
Else:
Set TREE[PTR]:=TREE[RIGHT] and PTR:=RIGHT
Set LEFT:=2*PTR and RIGHT:=LEFT+1
If LEFT=N and if LAST<TREE[LEFT],then:
set PTR :=LEFT
Set TREE[PTR]:=LAST
Return
c)HEAP SORT:
***Heapsort() function is also called Heapify() to build the heap.
HEAPSORT (A, N):[Build a heap A ,using INSERTION method]
Repeat for J=1 to N-1
Call INSHEAP(A, J, A[J+1])[sort A by repeatedly deleting the root of H, using DELETION method]
Repeat while N>1:
Call DELHEAP(A , N,VALUE)
Set A[n+1]:=valueExit
Coding for Heap Sort:
#include <stdio.h>
int main()
{
int heap[10], n, i, j, c, root, temp;
printf("How many number do u want to execute. ");
scanf("%d", &n);
printf("\n Enter the elements one by one. ");
for (i = 0; i < n; i++)
scanf("%d", &heap[i]);
for (i = 1; i < n; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
} while (c != 0);
}
for (j = n- 1; j >= 0; j--)
{
temp = heap[0];
heap[0] = heap[j ]; /* swap max element with rightmost leaf element */
heap[j] = temp;
root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
{
temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < n; i++)
printf("\t %d", heap[i]);
}
Example:
'
Comments
Post a Comment