Skip to main content

non-linear sorting

(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
1  2  2  3  4  7  7  9 

Comments

Popular posts from this blog

Mastering SQL for Data Science: Top SQL Interview Questions by Experience Level

Introduction: SQL (Structured Query Language) is a cornerstone of data manipulation and querying in data science. SQL technical rounds are designed to assess a candidate’s ability to work with databases, retrieve, and manipulate data efficiently. This guide provides a comprehensive list of SQL interview questions segmented by experience level—beginner, intermediate, and experienced. For each level, you'll find key questions designed to evaluate the candidate’s proficiency in SQL and their ability to solve data-related problems. The difficulty increases as the experience level rises, and the final section will guide you on how to prepare effectively for these rounds. Beginner (0-2 Years of Experience) At this stage, candidates are expected to know the basics of SQL, common commands, and elementary data manipulation. What is SQL? Explain its importance in data science. Hint: Think about querying, relational databases, and data manipulation. What is the difference between WHERE

What is Bort?

 Introduction: Bort, is the new and more optimized version of BERT; which came out this october from amazon science. I came to know about it today while parsing amazon science's news on facebook about bort. So Bort is the newest addition to the long list of great LM models with extra-ordinary achievements.  Why is Bort important? Bort, is a model of 5.5% effective and 16% total size of the original BERT model; and is 20x faster than BERT, while being able to surpass the BERT model in 20 out of 23 tasks; to quote the abstract of the paper,  ' it obtains performance improvements of between 0 . 3% and 31%, absolute, with respect to BERT-large, on multiple public natural language understanding (NLU) benchmarks. ' So what made this achievement possible? The main idea behind creation of Bort is to go beyond the shallow depth of weight pruning, connection deletion or merely factoring the NN into different matrix factorizations and thus distilling it. While methods like knowle

Spacy errors and their solutions

 Introduction: There are a bunch of errors in spacy, which never makes sense until you get to the depth of it. In this post, we will analyze the attribute error E046 and why it occurs. (1) AttributeError: [E046] Can't retrieve unregistered extension attribute 'tag_name'. Did you forget to call the set_extension method? Let's first understand what the error means on superficial level. There is a tag_name extension in your code. i.e. from a doc object, probably you are calling doc._.tag_name. But spacy suggests to you that probably you forgot to call the set_extension method. So what to do from here? The problem in hand is that your extension is not created where it should have been created. Now in general this means that your pipeline is incorrect at some level.  So how should you solve it? Look into the pipeline of your spacy language object. Chances are that the pipeline component which creates the extension is not included in the pipeline. To check the pipe eleme