Showing posts with label Data Structure Programs. Show all posts
Showing posts with label Data Structure Programs. Show all posts

Saturday 15 February 2014

Algorithm and Implementation Program of Quick Sort



Quick Sort is a Sorting Algorithm based on Divide And Conquer Technique. In this at every step element is placed in its proper position.It performs very well on a longer list. It works recursively, by first selecting a random "Pivot value" from the list. Then it partitions the list into elements that are less than the pivot and greater the pivot and greater than the pivot. The problem  of sorting a given list is reduced to the problem of sorting two sublists It is to be noted that the reduction step in the quick sort finds the final position of particular element; which can be accomplished by scanning that last element of list from the right to left and check with the element.

Quick sort is Developed by C.A.B. Hoare. The main purpose of quick sort is to find the element that partitions the array into tow halves and to place it at its proper location in the array.


Working Of Quick Sort


Before we start the learning how quick sort works, we make some assumptions . Set the index of first element of array to LOC and LEFT variable and index of last element of the array to RIGHT variable. Then proceeds as follows :-

1. Start with element pointed to by Right. The array is scanned from right to left , comparing each element on the way with the element pointed by LOC till either.

         ( a ) Element smaller than the element pointed to by LOC is found and elements are interchanged . Procedure continues with Step2.

         ( b ) If the value of the RIGHT becomes equal to value of LOC, the procedure terminates here. This indicates that element is placed in its final position.

2.  Start with element pointed to by LEFT. The array is scanned from left to right, comparing each element on the way with the element pointed by LOC till either.

         ( a ) Element greater than the element pointed to by LOC is found . In this case the elements are interchanged and procedure continues with step 1.
         ( b ) If the value of LEFT becomes equal to value of LOC , athea procedure terminates. This condition indicates that the element is placed in its final position

At the end of this procedure the first element ( PIVOT ) of original array is placed in its final location in the sorted array. The elements to its left will be less than this element and element to the right will be greater than this element . Now whole procedure that we applied on complete file will be applied on first subfile ( first index to LOC-1) and second (LOC + 1 to last index ) until we get the sorted array


Algorithm : QUICK SORT


Consider an Array( A ) with N elements having LB as lowerbound and UB as upperbound.

ALGORITHM : QUICK_SORT(A, LB, UB )

Step 1      If         ( LB < UB ) then
                           P = SUB_ARRAY (A, LB, UB )
                          QUICK_SORT(A, LB, P-1 )
                          QUICK_SORT(A, P+1, UB )            
               Else
                 
                   // Print sorted Array

Step 2    End

The above function is using the Divide and conquer strategy for algorithms. In above step we are dividing a large available Array named 'A' into smaller arrays and then we are passing these smaller arrays to SUB_ARRAY function that sorts the small list . And get back to Quick_Sort function and then again the divide the remaining list into another portion of a small array and then again take it to SUB_ARRAY function to sort this small array list in this way full or all elements of array are sorted


ALGORITHM : SUB_ARRAY(A, LB, UB )

Step 1      Set LEFT = LB,
               Set RIGHT = UB,
               Set LOC = LB

Step 2     Repeat step 3 and 4

Step 3      // Scanning Array from Right To Left
               Repeat while A[LOC] <= A[ Right] and LOC != Right
               Right = Right -1
                          ( a ) If LOC == Right then
                                 Return LOC
                          ( b ) Interchange A [LOC] & A [RIGHT]
                          ( c ) Set LOC == RIGHT

Explanation :- In Step 3 Array 'A' is scanned starting from Rightmost element of array and going towards the Left of array . In this step this algorithm finds the element which is greater the element at A[LOC] or pivot element and  when element which is greater than pivot is found it is replaced with A[LOC] and LOC is set the Location of element with which we have replaced the location it means A[RIGHT] and else the Right is decremented by 1 until it comes to location same as LOC

Step 4     // Scanning Array  from LEFT to Right
               Repeat while A[LOC] >= A[LEFT] and LOC != LEFT
               LEFT = LEFT +1
               ( a ) If LOC == LEFT then
                       Return LOC
               ( b ) Interchange A[LOC] and A[LEFT]
               ( c ) Set LOC = LEFT

Explanation :- In Step 4 Array 'A' is scanned starting from Leftmost element of array and going towards the Right of array . In this step this algorithm finds the element which is smaller the element at A[LOC] or pivot element and  when element which is smaller than pivot is found it is replaced with A[LOC] and LOC is set the Location of element with which we have replaced the location means A[LEFT].

Step 5      End


Implementation of Quick Sort Algorithm in Cplusplus ( c++ ) Program



#include< iostream.h >
#include< conio.h >
int a[20], n, lb, loc, ub, left, right, temp, temp1;

void quicksort(int[10],int,int);

int pivot(int[],int,int);

void main()
{
cout<<"Enter size of array";
cin>>n;
cout<<"Enter Array Elements ";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
quicksort(a,0,n-1);
for(int z=0;z<n;z++)
{
cout<<" "<<a[z];
}
getch();
}
void quicksort(int a[], int lb, int ub)
{
int p;
if(lb<ub)
{
p=pivot(a,lb,ub);
quicksort(a,lb,p-1);
quicksort(a,p+1,ub);
}
}
int pivot( int a[],int lb,int ub )
{
for(int z=0;z<n;z++)
{
cout<<" "<<a[z];
}
cout<<endl;
left =lb;
right = ub;
loc  =lb;
cout<<"right is :- "<<right;
cout<<"\tloc is :-"<<loc;
cout<<"left is :- "<<left;
 cout<<"Now right \n";
while((a[loc]<=a[right]) && (loc!=right))
{
right=right-1;
}
if(loc==right)
{
return loc;
}
temp=a[loc];
a[loc]=a[right];
a[right]=temp;
loc=right;
cout<<"Now left \n";
while((a[left]<=a[loc]) && (loc!=left))
{
left=left+1;
}
if(loc==left)
{
return loc;
}
temp1=a[loc];
a[loc]=a[left];
a[left]=temp1;
loc=left;





}



OUTPUT QUICK SORT PROGRAM
quick sorting technique with quick sort algorithm programming
Output of Quick Sort Program

For any type of more explanation to this program and for any suggest to this post you can freely comment . your comment are very crucial to us.

Tuesday 28 January 2014

selection sorting

 SELECTION SORT IN C++


Searching and sorting are popular in elementry data structures. Although now a days many advanced sorting techniques are used to sort a set of data, the basic sorting methods are still popular and are the used frequently.

The algorithm works is selection sort works by finding the smallest element in the list and by assuming that we are doing sorting in ascending order we replace that smallest found element with first element of list in this way we put the smallest element of list at first  position . Then we go on repeating this task for rest of elements. We then find the second smallest element in the list and then replace it with second element of list and thus we have our first two elements of list in sorted order of ascending order .


 I have given  C++ code for selection sort . The algorithm for selection sort is quite simple. In the first iteration, 1st element is compared against all the other elements (from array index 1 to array index n). In the second iteration 2nd element is compared with the elements from array index 2 to n. This process is repeated n-1 times.

 Disadvantages of Selection Sort
  • It is slow as the sorting process is too long and time consuming so it is mainly used for sorting when N (number of elements is less)


 Advantages of Selection Sort


  • Selection sort is easy to implement and does not require additional storage
  • It implements better on small lists




Code For Selection Sort
//It is for 10 elements and to change number of elements change 10 arguement in smallest function call


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

int small , a1=0 , loc;
int a[ 10 ];
int main( )
{
int n, temp, temp1, count, compare;
int smallest( int , int ) ;
clrscr( );
cout<<"enter number of elements you want to sort";
cin>>n;
count=n-1;
for(int i=0; i<=n-1; i++)
{
cout<<"ARRAY ["<<i<<"] :- ";
cin>>a[ i ];
}
for(int j1=0;j1<=n-1;j1++)
{
compare = smallest(10,a1);            // call smallest() function to calculate smallest element
temp1 = a[ j1 ];
a[ j1 ] = a[ loc ];
a[ loc ] = temp1;
a1 = a1 + 1;
}
cout<<endl;
cout<<" sorted array is ";cout<<endl;

for(i=0;i<=n-1;i++)                                      // Print sorted Array 
{
cout<<"ARRAY ["<<i<<"] :- ";
cout<<a[i];cout<<endl;
}
 getch();
}
int smallest(int n,int a1)      // function to calculate smaller number
{
for(int k=a1;k<=a1;k++)
{
small=a[k];                       // smaller is assigned first element
for(int j=k+1;j<=n-1;j++)
{
if(small>a[j])                       // if value smaller than small variable found
                                             then small = a[j] 

{                                                      
small = a[j];
loc = j;                                 // and location of smallest loc = j
}
}
}
return(loc);                              //return location of smallest element
     }