(1) Heap sort:
A heap is a complete binary tree. A complete binary tree means a tree which has all the nodes present before it enters the next layer. A heap is used in sorting process, by means of recursive rebuilding of the heap again and again and thus sorting the numbers.
A heap is called max heap if in any node, the child nodes are less than or equal to the node. Similarly a min heap is also defined.
As a heap is complete, we use array to store the heap rather than any dynamic or complex data structure. In this case, we store the child node values of a node stored at i, at 2*i+1, 2*i+2.
In this case, we first build the heap once. Then we heapify it again and again replacing the root element each time, therefore, as the root is the highest element, so, we get smaller and smaller heaps and finish the sorting in finite many steps.
Below I have written a program for heap sort which works for integer values and assumes the user will provide correct inputs only.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
void heapify(int A[],int n, int k)
{
int largest;
int le=2*k+1;
int ri=2*k+2;
if(le<n && A[le]>A[k])
{
largest=le;
}
if(ri<n && A[ri]>A[largest])
{
largest=ri;
}
if(largest!=k)
{
int temp;
temp=A[k];
A[k]=A[largest];
A[largest]=temp;
heapify(A,n,largest);
}
}
void buildheap(int A[],int n)
{
for(int i=n/2-1;i>=0;i--)
{
heapify(A,n,i);
}
}
void heapsort(int A[],int n)
{
int length=n;
int i;
buildheap(A,n);
printf("%d\n",length);
for(i=length-1;i>=0;i--)
{
int temp;
temp=A[0]; A[0]=A[i]; A[i]=temp;
heapify(A,i,0);
}
}
int main(void) {
int M; int A[100]; int i;
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d",&A[i]);
}
heapsort(A,M);
for(i=0;i<M;i++)
{
printf("%d ",A[i]);
}
/* int i;
int A[]={5,2,8,4};
heapsort(A,4);
for(i=0;i<4;i++)
{
printf("%d ",A[i]);
}
*/
return 0;
}
(2) Quick sort:
//lemoto process
#include <stdio.h>
void QuickSort(int A[],int low,int high)
{
if(low<high)
{
int p=partition(A,low,high);
QuickSort(A,low,p-1);
QuickSort(A,p+1,high);
}
}
int partition(int A[],int low,int high)
{
int j;
int pivot=A[high];
int i=low-1;
for(j=low; j<high; j++)
{
if(A[j]<=pivot)
{
i++;
int temp=A[j];
A[j]=A[i];
A[i]=temp;
}
}
int tempo=A[i+1];
A[i+1]=A[j];
A[j]=tempo;
return (i+1);
}
int main(void) {
int M; int A[100]; int i;
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d",&A[i]);
}
QuickSort(A,0,M-1);
for(i=0;i<M;i++)
{
printf("%d ",A[i]);
}
return 0;
}
(3) Counting sort:
This is a bit different from the above two also. This is a non-comparative sort; it does not use comparison to perform the sorting.
Here is the code for it:
#include <stdio.h>
#include <stdlib.h>
void counting_sort(int A[], int length)
{
int i; int frequency[10]; int *SortedArray;
for(i=0;i<10;i++)
{frequency[i]=0;}
SortedArray=(int *)calloc(length,sizeof(int));
for(i=0;i<length;i++)
{SortedArray[i]=-3;}
for(i=0;i<length;i++)
{frequency[A[i]]+=1;}
for(i=1;i<10;i++)
{frequency[i]+=frequency[i-1];}
// for(i=0;i<10;i++)
// {printf("%d\n",frequency[i]);}
int count=0;
while(count<length)
{
for(i=0;i<10;i++)
{
if(frequency[i]!=0 && SortedArray[frequency[i]-1]==-3)
{
SortedArray[frequency[i]-1]=i;
frequency[i]-=1;
count+=1;
}
}
}
for(i=0;i<length;i++)
{
A[i]=SortedArray[i];
}
}
int main(void) {
// data is in between 0 to 9
int array[200];
int response[200];
int length; int i;
scanf("%d",&length);
for(i=0;i<length;i++)
{scanf("%d",&array[i]);}
counting_sort(array,length);
// *response=counting_sort(array,length);
for(i=0;i<length;i++)
{printf("%d ",array[i]);}
return 0;
}
Input:
8
2 4 2 3 9 7 7 1
output:
Success #stdin #stdout 0s 9424KB
A heap is a complete binary tree. A complete binary tree means a tree which has all the nodes present before it enters the next layer. A heap is used in sorting process, by means of recursive rebuilding of the heap again and again and thus sorting the numbers.
A heap is called max heap if in any node, the child nodes are less than or equal to the node. Similarly a min heap is also defined.
As a heap is complete, we use array to store the heap rather than any dynamic or complex data structure. In this case, we store the child node values of a node stored at i, at 2*i+1, 2*i+2.
In this case, we first build the heap once. Then we heapify it again and again replacing the root element each time, therefore, as the root is the highest element, so, we get smaller and smaller heaps and finish the sorting in finite many steps.
Below I have written a program for heap sort which works for integer values and assumes the user will provide correct inputs only.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
void heapify(int A[],int n, int k)
{
int largest;
int le=2*k+1;
int ri=2*k+2;
if(le<n && A[le]>A[k])
{
largest=le;
}
if(ri<n && A[ri]>A[largest])
{
largest=ri;
}
if(largest!=k)
{
int temp;
temp=A[k];
A[k]=A[largest];
A[largest]=temp;
heapify(A,n,largest);
}
}
void buildheap(int A[],int n)
{
for(int i=n/2-1;i>=0;i--)
{
heapify(A,n,i);
}
}
void heapsort(int A[],int n)
{
int length=n;
int i;
buildheap(A,n);
printf("%d\n",length);
for(i=length-1;i>=0;i--)
{
int temp;
temp=A[0]; A[0]=A[i]; A[i]=temp;
heapify(A,i,0);
}
}
int main(void) {
int M; int A[100]; int i;
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d",&A[i]);
}
heapsort(A,M);
for(i=0;i<M;i++)
{
printf("%d ",A[i]);
}
/* int i;
int A[]={5,2,8,4};
heapsort(A,4);
for(i=0;i<4;i++)
{
printf("%d ",A[i]);
}
*/
return 0;
}
(2) Quick sort:
//lemoto process
#include <stdio.h>
void QuickSort(int A[],int low,int high)
{
if(low<high)
{
int p=partition(A,low,high);
QuickSort(A,low,p-1);
QuickSort(A,p+1,high);
}
}
int partition(int A[],int low,int high)
{
int j;
int pivot=A[high];
int i=low-1;
for(j=low; j<high; j++)
{
if(A[j]<=pivot)
{
i++;
int temp=A[j];
A[j]=A[i];
A[i]=temp;
}
}
int tempo=A[i+1];
A[i+1]=A[j];
A[j]=tempo;
return (i+1);
}
int main(void) {
int M; int A[100]; int i;
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d",&A[i]);
}
QuickSort(A,0,M-1);
for(i=0;i<M;i++)
{
printf("%d ",A[i]);
}
return 0;
}
(3) Counting sort:
This is a bit different from the above two also. This is a non-comparative sort; it does not use comparison to perform the sorting.
Here is the code for it:
#include <stdio.h>
#include <stdlib.h>
void counting_sort(int A[], int length)
{
int i; int frequency[10]; int *SortedArray;
for(i=0;i<10;i++)
{frequency[i]=0;}
SortedArray=(int *)calloc(length,sizeof(int));
for(i=0;i<length;i++)
{SortedArray[i]=-3;}
for(i=0;i<length;i++)
{frequency[A[i]]+=1;}
for(i=1;i<10;i++)
{frequency[i]+=frequency[i-1];}
// for(i=0;i<10;i++)
// {printf("%d\n",frequency[i]);}
int count=0;
while(count<length)
{
for(i=0;i<10;i++)
{
if(frequency[i]!=0 && SortedArray[frequency[i]-1]==-3)
{
SortedArray[frequency[i]-1]=i;
frequency[i]-=1;
count+=1;
}
}
}
for(i=0;i<length;i++)
{
A[i]=SortedArray[i];
}
}
int main(void) {
// data is in between 0 to 9
int array[200];
int response[200];
int length; int i;
scanf("%d",&length);
for(i=0;i<length;i++)
{scanf("%d",&array[i]);}
counting_sort(array,length);
// *response=counting_sort(array,length);
for(i=0;i<length;i++)
{printf("%d ",array[i]);}
return 0;
}
Input:
8
2 4 2 3 9 7 7 1
output:
Success #stdin #stdout 0s 9424KB
1 2 2 3 4 7 7 9
Comments
Post a Comment