Quick Sort

Algorithm

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:

1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.
2. Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
3. Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.

PDF

C++

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}




PSEUDO CODE:

Quicksort (int data[],int left,int right) {
   int mid,tmp,i,j;
   

   i = left;
   j = right;
   mid = data[(left + right)/2];
   do {
        while(data[i] < mid)
           i++;
       while(mid < data[j])
           j--;
       if (i <= j) {
           tmp = data[i];
           data[i] = data[j];
           data[j] = tmp;
           i++;
           j--;
       }
   } while (i <= j);
   if (left < j) Quicksort(data,left,j);
   if (i < right) Quicksort(data,i,right);
}

 

Find area of circle and square using Pure Virtual Function

#include <iostream.h>
#include<conio.h>

class Shape                    /* Abstract class */
{
    protected:
       float l;
    public:
       void get_data()          /* Note: this function is not virtual. */
       {
  cin>>l;
       }

       virtual float area() = 0; /* Pure virtual function */
};

class Square : public Shape
{
    public:
       float area()
       {   return l*l;  }
};

class Circle : public Shape
{
    public:
       float area()
       { return 3.14*l*l; }
};

void main()
{
    Square s;
    Circle c;
    cout<<"Enter length to calculate area of a square: ";
    s.get_data();
    cout<<"Area of square: "<<s.area();
    cout<<"\nEnter radius to calcuate area of a circle:";
    c.get_data();
    cout<<"Area of circle: "<<c.area();

    getch();
}

Virtual Function in c++

/* Program by Arun Anoop M */

#include<iostream.h>
#include<conio.h>
class B
{
protected:
int a,b;
public:
virtual void show()
{
cout<<"Arithmetic Operations";
cout<<"Div="<<a/b;
}
void get()
{
cout<<"Enter 2 nos:";
cin>>a>>b;
}
};
class D1:public B
{
/*void get()
{
cout<<"Enter 2nos:";
cin>>a>>b;
} */

void show()
{
cout<<"ADD="<<a+b;
}
};
class D2:public B
{
void show()
{
cout<<"Subst="<<a-b;
cout<<"Mul="<<a*b;
}
};

void main()
{
B *p1;
B base1;
p1=&base1;
p1->get();
p1->show();

D1 der1;
p1=&der1;
p1->get();
p1->show();

D2 der2;
p1=&der2;
p1->get();
p1->show();

getch();
}

Pure Virtual Function

concatenate two strings using operator overloading in c++

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
class string
{
char str[100];
public:
void input();
void output();
string operator+(string s);
};
void string::input()
{
cout<<"enter the string\n";
gets(str);
}s
tring string::operator+(string s)
{
string temp;
strcpy(temp.str,str);
strcat(temp.str,s.str);
return(temp);
}
void string::output()
{
cout<<"the string is\n";
cout<<str;
}
void main()
{
string s1,s2,s3;
clrscr();
s1.input();
s2.input();
s3=s1+s2;
s3.output();
getch();
} 

OUTPUT:
enter the string
MES
enter the string
college
the string is
MEScollege

Virtual Function

A Virtual function is a function which is declared in base class using the keyword virtual.

Its purpose is to tell the compiler that what function we would like to call on the basis of the object of derived class.

In c++,virtual keyword is used for OVERRIDING.

NORMAL:-

1) Declare main class
    function show()
2) Define derived class(s) with functions
3) main()

3.1)Create pointer variable of base class
ie; if base class name is B.
then,
B *p;

3.2)Create object for base_class & derived classes
Base_class named B
derived_class1 named D1
derived_class2 named D2
 ie;
B base1;
D1 der1;
D2 der2;

3.3)Assign address of base_class & derived_class(s) to pointer_variable_of_Base_class
ie;
p=&base1;

call show() function
p->show();

likewise......
p=&der1;
p->show();
p=&der2;
p->show();


Without Virtual keyword: O/p will be
B
B
B
-----------------------------------------------------------------------------------------


1) Declare Base class
    function show()
ie;
class B;
{
virtual void show()
{
cout<<"B"<<"\n";
}
};

2) Define derived class(s) with functions
ie;
class D1:public B
{
void show()
{
cout<<"D1"<<"\n";
}
};

class D2:public B
{
void show()
{
cout<<"D2"<<"\n";
}
};

3) main()

3.1)Create pointer variable of base class
ie; if base class name is B.
then,
B *p;

3.2)Create object for base_class & derived classes
Base_class named B
derived_class1 named D1
derived_class2 named D2
 ie;
B base1;
D1 der1;
D2 der2;

3.3)Assign address of base_class & derived_class(s) to pointer_variable_of_Base_class
ie;
p=&base1;

call show() function
p->show();

likewise......
p=&der1;
p->show();
p=&der2;
p->show();

getch();

With Virtual keyword: O/p will be
B
D1
D2
--------------------------------------------------------------------------------------
ABOVE PROGRAM:-  /* By ARUN ANOOP M  */
--------------------------------------------------------------------------------------
#include<iostream.h>
class B;
{
virtual void show()
{
cout<<"B"<<"\n";
}
};
class D1:public B
{
void show()
{
cout<<"D1"<<"\n";
}
};

class D2:public B
{
void show()
{
cout<<"D2"<<"\n";
}
};

main()
{
B *p;
B base1;
D1 der1;
D2 der2;

p=&base1;
p->show();

p=&der1;
p->show();

p=&der2;
p->show();

getch();
}

--------------------------------------------------------------------------------------
Another PROGRAM:-  /* By ARUN ANOOP M  */
--------------------------------------------------------------------------------------
#include<iostream.h>
class B;
{
void show()
{
cout<<"Operations"<<"\n";
}
};
class D1:public B
{
void get()
{
cout<<Enter 2 nos:";
cin>>a>>b;
}

void show()
{
cout<<"Addition"<<a+b<<"\n";
}
};

class D2:public B
{

void show()
{
cout<<"Subtraction"<<a-b<<"\n";
}
};


main()
{
B *p;
B base1;
D1 der1;
D2 der2;

p=&base1;
p->show();

p=&der1;
p->get();
p->show();

p=&der2;
p->get();
p->show();

getch();
}

O/p:-
Enter 2 nos: 4 3
7
Enter 2 nos: 2 1
3
-----------------------------------------------------------------------------------------
#include<iostream.h>
class B;
{
virtual void show()
{
cout<<"Operations"<<"\n";
}
};
class D1:public B
{
void get()
{
cout<<Enter 2 nos:";
cin>>a>>b;
}

void show()
{
cout<<"Addition"<<a+b<<"\n";
}
};

class D2:public B
{

void show()
{
cout<<"Subtraction"<<a-b<<"\n";
}
};


main()
{
B *p;
B base1;
D1 der1;
D2 der2;

p=&base1;
p->show();

p=&der1;
p->get()
p->show();

p=&der2;
p->get();
p->show();

getch();
}

O/p:-
Enter 2 nos:3 4
7
Enter 2 nos:4 3
1
--------------------------------------------------------------------------------------