C Program to implement Quick Sort taking pivot as last element

#include <stdio.h>
void quicksort(int *a, int left, int right)
{
      int i = left, j = right-1;
      int tmp;
      int pivot = a[right];
   
      while (i <= j) {
            while (a[i] < pivot)
                  i++;
            while (j>=left && a[j] >= pivot)
                  j--;
            if (i <= j) {
                  tmp = a[i];
                  a[i] = a[j];
                  a[j] = tmp;
                  i++;
                  j--;
            }
      }
      tmp=a[i];
      a[i]=a[right];
      a[right]=tmp;
   
  if (left < i - 1)
            quicksort(a, left, i - 1);
      if ((i+1) < right)
            quicksort(a, i+1, right);  
}

main()
{
int a[100],n,i;
printf("enter n value");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d\t",a[i]);

}


Output:

Quick Sort Java Program
import java.util.Scanner;
import java.util.Arrays;
public class MyClass
{
    public static void QuickSort(int a[],int start, int end)
    {
        int i=start,j=end-1,pivot=end;
        while(i<=j)
        {
            while(a[i] < a[pivot] )
                i++;
            while(j>=start && a[j] >= a[pivot])
                j--;
            if(i<j)
            {
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        int temp=a[i];
        a[i]=a[pivot];
        a[pivot]=temp;
        if(start < i-1)
            QuickSort(a,start,i-1);
        if(i+1 < end)
             QuickSort(a,i+1,end);
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter number of elements");
        int n = sc.nextInt();
        int a[] =  new int[n];
        System.out.println("enter array elements");
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        QuickSort(a,0,n-1);
        System.out.println("Sorted array");
        System.out.println(Arrays.toString(a));
    }

}

Implementing shell sort using insertion sort (or) Single program to implement both insertion and shell sort in C

#include<stdio.h>
void Sort(int *a, int n, int gap)
{
    int i, j, temp;
        for(i = gap; i < n; i++)
        {
            for(j = i; j >= gap; j =j-gap)
            {
                 if(a[j]<a[j-gap])
                 {
                          temp = a[j];
                          a[j]=a[j-gap];
                          a[j-gap]=temp; 
}
            }
        }
}

int main()
{
    int i, n, a[10],gap,opt;
    printf("Enter the number of elements :: ");
    scanf("%d",&n);
    printf("Enter the elements :: ");
    for(i = 0; i < n; i++)
         scanf("%d",&a[i]);
    printf("\nPress 1. For Insertion Sort \t 2. Shell Sort \n");
  scanf("%d",&opt);
  switch(opt)
  {
   case 1: Sort(a,n,1);  // For insertion Sort we pass 1 for gap
      break;
  case 2:  for(gap = n/2; gap > 0; gap /= 2)
        {
             Sort(a,n,gap);
        }
}
         
    printf("\nAfter Sorting:: \n ");
    for(i = 0; i < n; i++)
        printf("%d  ",a[i]);
  return 0;
}

Here both insertion and Shell sort use the same function Sort, the only difference between two programs is highlighted in bold

Output: When shell Sort is selected

Output: When Insertion Sort is selected

(OR)
#include<stdio.h>
void Sort(int *a, int n, int increment)
{
    int i, j, tmp;
        for(i = increment; i < n; i++)
        {
            tmp = a[i];
            for(j = i; j >= increment; j -= increment)
            {
                if(tmp < a[j-increment])
                    a[j] = a[j-increment];
                else
                    break;
            }
            a[j] = tmp;
        }
}

int main()
{
    int i, n, a[10],increment,opt;
    printf("Enter the number of elements :: ");
    scanf("%d",&n);
    printf("Enter the elements :: ");
    for(i = 0; i < n; i++)
         scanf("%d",&a[i]);
    printf("\nPress 1. For Insertion Sort \t 2. Shell Sort \n");
scanf("%d",&opt);
switch(opt)
{
case 1: Sort(a,n,1);  // For insertion Sort we pass 1 for increment/gap
break;
case 2:  for(increment = n/2; increment > 0; increment /= 2)
          {
         Sort(a,n,increment);
        // printf("\nafter each increment/gap\n"); for(i = 0; i < n; i++)  printf("%d  ",a[i]);
          }
    
}
         
    printf("\nAfter Sorting:: \n ");
    for(i = 0; i < n; i++)
        printf("%d  ",a[i]);
  return 0;
}

Insertion sort hacker rank solution in C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
void insertionSort(int ar_size, int *  ar) {

   int j,tmp=ar[ar_size-1],k;
    for(j=ar_size-1; j>=1;j--)
        {
            if(tmp<ar[j-1])
                ar[j]=ar[j-1];
            else
                break;
        for(k=0; k<ar_size;k++)
        printf("%d ", ar[k]);
        printf("\n");
        }
    ar[j]=tmp;
    for(k=0; k<ar_size;k++)
        printf("%d ", ar[k]);

}
int main(void) {
    int _ar_size;
    scanf("%d", &_ar_size);
    int _ar[_ar_size], _ar_i;
    for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
        scanf("%d", &_ar[_ar_i]);
    }
   
    insertionSort(_ar_size, _ar);
    return 0;
}

Merging two sorted linked list using recursion in C hacker rank solution

Node* MergeLists(Node *headA, Node* headB)
{
  // This is a "method-only" submission.
  // You only need to complete this method \
 
if(headA == NULL)
  return headB;
if(headB == NULL)
return headA;
if(headA->data>headB->data)
 return MergeLists(headB,headA);
else
headA->next=MergeLists(headA->next,headB);
    return headA;
}

Balanced Brackets HackerRank solution in C

Algorithm

Step 1: Start

Step 2: Read the expression

Step 3: Scan every character of expression

          If scanned character is

          3.1: any open symbol like ( , {, [ then   push it onto the stack

          3.2: any closed symbol then

                    3.2.1 if stack is empty then invalid expression

                    3.2.2 else  pop the top most element of stack

                              if the symbol popped is not the corresponding opening

symbol, then invalid expression

Step 4: If stack is not empty then invalid expression

Step 5: Stop

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>


int main(){
    int t,top=-1,i,flag,a0;
    char stack[100],temp;
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        char* s = (char *)malloc(10240 * sizeof(char));
        scanf("%s",s);
        flag=1;
        for(i=0;s[i]!='\0';i++)
        {
            if(s[i] == '('||s[i]=='{'||s[i]=='[')
                stack[++top]=s[i];              
            if(s[i] == ')'||s[i]=='}'||s[i]==']')
            {
                  if(top == -1)
 {
  flag=0;  
  break;
 }
                   
                  else
                      {
                        temp=stack[top--];
                                             
                      if((s[i] == ')' &&temp != '(') ||(s[i] == '}' && temp!='{')||(s[i] == ']' && temp!='['))
                          flag=0;
                    }
            }
        }
        if(top>=0)
        {
        while(top >= 0)
           temp=stack[top--];
        flag=0;
        }
         
        if(flag == 0)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

C program to implement Queue using single linked list by using global variables

#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *f=NULL,*r = NULL,*c;
void enq();
void deq();
void display();
main()
{
          int opt;
while(1)
         {
printf("\n Press 1. Enq\t 2. Deq\t 3. Display \t 4. Exit\n");
               scanf("%d",&opt);
               switch(opt)
             {
                 case 1: enq();
                            break;
                 case 2: deq();
                            break;
                 case 3: display();
                            break;
case 4: exit(0);
            }
        }
}
void enq()
{
int val;
printf("enter value to be enqueued\n");
scanf("%d",&val);
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data=val;
newnode->next=NULL;
if(f == NULL && r == NULL)
f=r=newnode;
else
{
r->next=newnode;
r= newnode;
}
}

void deq()
{
if(f == NULL && r == NULL)
{
printf("queue is empty");
return;
}
if(f = = r)
       f = r = NULL;
else
{
c=f;
f=f->next;
free(c);
}
}

void display()
{
if(f == NULL && r == NULL)
{
printf("queue is empty");
return;
}
else
{
c=f;
while(c != NULL)
{
printf("%d\t",c->data);
c=c->next;
}
}
}

Little Monk and Balanced Parantheses

Little Monk and Balanced Parentheses

Given an array of positive and negative integers, denoting different types of parentheses. The positive numbers

xi denotes opening parentheses of type xi and negative number −xi denotes closing parentheses of type xi.

Open parentheses must be closed by the same type of parentheses. Open parentheses must be closed in the

correct order, i.e., never close an open pair before its inner pair is closed (if it has an inner pair). Thus,

[1,2,−2,−1]

is balanced, while [1,2,−1,−2]

is not balanced.

You have to find out the length of the longest sub array that is balanced.

Input Format:

First line contains an input N

(1≤N≤2∗105), denoting the number of parentheses. Second line contains N space separated integers. xi

(−105≤xi≤105,xi≠0) denoting the ith

parentheses of the array.

Output Format:

Print the length of the longest subarray that is balanced.

SAMPLE INPUT

5

1 -1 2 3 -2

SAMPLE OUTPUT

2

Explanation

The longest subarray that is balanced is (1,−1). (2,3,−2) is not balanced as (3) is not balanced.

#include <stdio.h>
int stack[50],top=-1;
void push(int t)
{            
       top=top+1;
stack[top]=t;
}
int pop()
{
   int te=stack[top];
   top=top-1;
   return te;
}
main()
{
   int a[50],n=4,i,temp;
   for(i=0;i<n;i++)
scanf("%d",&a[i]);
   for(i=0;i<n;i++)
   {
if(a[i] > 0)
push(a[i]);
else
{
               if(top == -1)
{
printf("invalid expression");
exit(0);
}
              temp = pop();
              else
{
if(temp !=(-a[i]))
{
printf("invalid expression");
exit(0);
}
}
}
   }
   if(top >=0 )
printf("invalid");
   else
printf("valid");
}

C program to check whether a given IP is valid or not

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
main()
{
    int num,dots=0;
char ip[50],*p,*end;
    gets(ip);
    p=strtok(ip,".");
while(p != NULL)
   {
        num=strtol(p,&end,10);
        if(!*end)
        {
         if(num >=0 && num <= 255)
              {
                           p=strtok(NULL,".");
                             if(p != NULL)
                                         dots++;
              }
              else
             {
printf("not valid ip: number not in range");
                         exit(0);
             }
      }
      else
     {
                         printf("not valid ip: not a digit");
                          exit(0);
      }
   }
   if(dots != 3)
printf("not a valid ip: not enough dots");
   else
               printf("valid ip");
getch();
}

C program to reverse each word in given line of text

#include <stdio.h>
#include <string.h>
#include <conio.h>
main()
{
int i=0,j;
char name[50];
clrscr();
gets(name);
j=strlen(name)-1;
for(;j>=0;j--)
{
if(name[j] == ' ' || j == 0)
{
i=j;
do
{
printf("%c",name[i]);
i=i+1;

}while(name[i] != '\0' && name[i] != ' ');
printf("\t");
}
}
getch();
}

Use Queue data structure to print binary numbers from 1 to n: C Program

Use Queue data structure to print binary numbers from 1 to n.

1)       Create an empty queue of strings

2)       Enqueue the first binary number “1” to queue.

3)       Now run a loop for generating and printing n  Binary Numbers.

a) Dequeue and Print the front of queue.

b) Append “0” at the end of front item and enqueue it.

c) Append “1” at the end of front item and enqueue it.

Input: n=5

Output: 1,10,11,100,101

Program:

#include <stdio.h>

#include <string.h>

#define MAX 20

char queue[MAX][MAX], temp[MAX];

int front=-1, rear=-1;

void enq(char *s)

{

if(rear == MAX-1)

{

printf("Queye full");

return;

}

if(front == -1 && rear == -1)

front=rear=0;

else

rear=rear+1;

strcpy(queue[rear],s);

}

char* deq()

{

if(front == -1)

printf("stack is empty");

else

{

strcpy(temp,queue[front]);

if(front == rear)

front = rear = -1;

else

front=front+1;

return temp;

}

}

void bin()

{

char temp2[MAX];

strcpy(temp,deq());

printf("Binary numbers = %s\n",temp);

strcpy(temp2,temp);

strcat(temp,"0");

enq(temp);

strcat(temp2,"1");

enq(temp2);

}

main()

{

int i;

char temp[2]="1";

enq(temp);

for(i=1;i<=5;i++)

bin();

}

Symbol Balancing using Stacks : Java program and C program

Algorithm

Step 1: Start

Step 2: Read the expression

Step 3: Scan every character of expression

          If scanned character is

          3.1: any open symbol like ( , {, [ then   push it onto the stack

          3.2: any closed symbol then

                    3.2.1 if stack is empty then invalid expression

                    3.2.2 else  pop the top most element of stack

                              if the symbol popped is not the corresponding opening

symbol, then invalid expression

Step 4: If stack is not empty then invalid expression

Step 5: Stop

Java program
package p1;

import java.util.Scanner;
class SNode
{
char data;
SNode next;
}
class Stack
{
SNode top=null;
public void push(char val)
{
SNode newnode=new SNode() ;
newnode.data=val;
newnode.next=null;
if(top==null)
top=newnode;
else
{
newnode.next=top;
top=newnode;
}
}
public char pop()
{
char temp=top.data;
top=top.next;
return temp;
}
}
public class SymbolBalancingDemo 
{
public static void main(String[] args)
{
Stack ob=  new Stack();
Scanner sc = new Scanner(System.in);
System.out.println("enter infix expression");
String infix=sc.next();
int flag=0;
for(int i=0;i<infix.length();i++)
{
char ch=infix.charAt(i);
if(ch == '(' || ch== '{' || ch =='[')
ob.push(ch);
else if (ch == ')' || ch== '}' || ch ==']')
{
if(ob.top == null)
flag=1;
else 
{
char temp=ob.pop();
if(ch ==')' && (temp == '{' || temp == '['))
flag=1;
else if(ch ==']' && (temp == '{' || temp == '('))
flag=1;
else if(ch =='}' && (temp == '(' || temp == '['))
flag=1;

}
}
if(flag ==1)
break;
}
if(ob.top != null)
flag=1;
if(flag == 1)
System.out.println("invalid expression");
else
System.out.println("valid expression");
}

}

========C program=================

#include<stdio.h>
#include <process.h>
#include <string.h>
#define MAX 50
char stack[MAX];
int top=-1;
void push(char);
char pop();
void main()
{
 char exp[MAX],temp;
 int i, flag=1;
printf("Enter an expression : ");
gets(exp);
for(i=0;i<strlen(exp);i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
       push(exp[i]);
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top == -1)
{
       flag=0; break;
}
else
{
temp=pop();
if(exp[i]==')' && (temp=='{' || temp=='['))
flag=0;
if(exp[i]=='}' && (temp=='(' || temp=='['))
flag=0;
if(exp[i]==']' && (temp=='(' || temp=='{'))
flag=0;
}
}
if(top>=0)
         flag=0;
if(flag==1)
printf("\n Valid expression");
else
printf("\n Invalid expression");
}
void push(char item)
{
 if(top == MAX-1)
 {
  printf("stack is full");
  return;
 }
 top=top+1;
 stack[top]=item;
}

char pop()
{
 if(top == -1)
 {
  printf("stack empty");
  return;
 }
 char temp;
 temp=stack[top];
 top=top-1;
 return temp;
}

Evaluating Postfix Expression Using Stack : Java Program and C Program

Algorithm

Step 1: Start

Step 2: Read the postfix expression

Step 3: Scan every character of postfix expression

          3.1 If scanned character is operand then push it onto the stack

          3.2 If scanned character is operator, then

                    a. pop the top two elements from the stack as A and B

                    b. Perform the operation on B and A

                    c. Push the result back into stack

Step 4: Print the top most element of the stack

Step 5: Stop

import java.util.Scanner;
class SNodei
{
int data;
SNodei next;
}
class Stacki
{
SNodei top=null;
public void push(int val)
{
SNodei newnode=new SNodei() ;
newnode.data=val;
newnode.next=null;
if(top==null)
top=newnode;
else
{
newnode.next=top;
top=newnode;
}
}
public int pop()
{
int temp=top.data;
top=top.next;
return temp;
}
}

public class PostfixEvaluation
{
public static void main(String[] args)
{
Stacki ob = new Stacki();
Scanner sc = new Scanner(System.in);
System.out.println("enter postfix expression");
String postfix;
postfix=sc.next();
for(int i=0;i<postfix.length();i++)
{
char ch=postfix.charAt(i);
if(ch == '*' ||ch == '/' ||ch == '+' ||ch == '-'|| ch == '%' )
{
int v1,v2,v3=0;
v1=ob.pop();
v2=ob.pop();
switch(ch)
{
   case '+': v3=v2+v1;
      break;
   case '-': v3=v2-v1;
      break;
   case '*': v3=v2*v1;
      break;
   case '/': v3=v2/v1;
      break; 
}
ob.push(v3);
}
else if(ch>='a' && ch<='z')
{
  int val;
  System.out.println("enter the value of "+ch);
  val=sc.nextInt();
  ob.push(val);
}
}
System.out.println("Result ="+ob.pop());
}
}

============================================================

#include<stdio.h>
#include <process.h>
#include <string.h>
#define MAX 50
char stack[MAX];
int top=-1;
void push(float);
float pop();
void main()
{
char exp[MAX],temp,ch;
int i;
float op1,op2,value;
printf("Enter an expression : ");
gets(exp);
for(i=0;i<strlen(exp);i++)
{
ch=exp[i];
if(isdigit(ch))
push((float)ch-'0');
else
{
op2=pop();
op1=pop();
switch(ch)
{
case '+':
value=op1+op2;
break;
case '-':
value=op1-op2;
break;
case '*':
value=op1*op2;
break;
case '/':
value=op1/op2;
break;
case '%':
value=(int)op1%(int)op2;
break;
}
push(value);
}
}
printf("\n Result=%f",pop());
}

void push(float item)
{
if(top == MAX-1)
{
printf("stack is full");
return;
}
top=top+1;
stack[top]=item;
}

float pop()
{
if(top == -1)
{
printf("stack empty");
return;
}
float temp;
temp=stack[top];
top=top-1;
return temp;
}

Infix to Postfix conversion without incorrect expression checking

#include<stdio.h>
#include <process.h>
#define MAX 50
char stack[MAX];
int top=-1;
int getpriority(char);
void push(char);
char pop();

main()
{
    char infix[50],temp,ch,postfix[50];
    int i,j=0;
    printf("enter the infix expression\n");
    scanf("%s",&infix);
    for(i=0; infix[i] != '\0'; i++)
    {
          ch=infix[i];
          if(ch == '(')
                   push(ch);
          else if(ch == ')')
          {
                 while(stack[top]!='(')
                            postfix[j++]=pop();
                  temp=pop();                  // popping the (
           }
           else if(isalnum(ch))
                  postfix[j++]=ch;
           else
           {
                 while(getpriority(stack[top])>=getpriority(ch))
                        postfix[j++]=pop();
                 push(ch);
          }
    }
    while(top != -1)
              postfix[j++]=pop();
     postfix[j]='\0';
     printf("%s",postfix);
}

int getpriority(char ch)
{
if( ch == '*'|| ch == '/'|| ch == '%')
return 2;
else if(ch == '+' || ch == '-')
return 1;
else
return 0;
}
void push(char item)
{
if(top == MAX-1)
{
printf("stack is full");
return;
}
top=top+1;
stack[top]=item;
}

char pop()
{
if(top == -1)
{
printf("stack empty");
return;
}
char temp;
temp=stack[top];
top=top-1;
return temp;
}