computer graphics Line Drawing Algorithm

Line Drawing is done by calculating Intermediate positions along the line path Between specified paths. DDA LINE Algorithm is a simplest algorithm of drawing a line . In DDA Algorithm line is simply Draws by adding the increment to initial pixel values with respect to x and y direction . After drawing initial pixel whose x and y direction are entered by user or inputted by user Then the Next pixel is drawn by adding Change in x and y direction of new pixel to the initial pixel 

We will add the value of change in x and y axis to initial or previous x and y axis values to get New pixel plotted on screen and This process continues upto and end point that is also inputted by user at start of execution of This Algorithm

The Screen Locations are refrenced by integer values and if these values are in fraction like 10.25 and 21.4 :- (10.25,21.4)  where 10.25 is x coordinate in x-Axis and 21.4 is Y Coordinate in Y-Axis Then These Fractional Values will be converted into Integer values on Screen and interpreted as (10,21). This rounding of two integers cause lines to be displayed with stare steps appearance in Zagged line

To Display a pixel on Screen we use 

                                                          putpixel ( 10 , 11 )

How Line Drawn in DDA Line Algorithm

1. First user input the four values 

* Initial pixel value in x-direction            { let x1 }
* Initial pixel value in y-direction            { let y1 }
* End Point pixel value in x-direction     { let x2 }
* End Point pixel value in y-direction     { let y2 }

2. Now all inputs are  given , Now first input the initial pixels point

putpixel ( x1, y1 )

3. Now we will add the an increment value to initial x and y coordinates and this increment value is added upto End Point


4. The Increment value is calculated by 

dx = x2 - x1   // In x-Direction
dy = y2 - y1   // In y-Direction

Here dx is the how much total distance to cover in x-direction to reach the End coordinate in x-direction
Here dy is the how much distance to cover in y-direction to reach the End coordinate in y-direction

5. Now find the how must distance to cover at one time or at one loop run 

6. This is calculated by dividing the dx and dy by a step 

7. value of step will be value among dx or dy 

If dx > dy then
{
step = dx
}
else
{
step = dy
}

8. After calculating step change in x-direction let be cx will be 

cx =  dx/step 
This will give how much distance to cover in each loop run or at one time how much increment will takes place

Similarly in y-direction 
cy =  dy/step 
This will give how much distance to cover in each loop run or at one time how much increment will takes place

9. Now Start a loop and it will continue upto value in Step variable 

increment x and y as :- 

x= cx + x

y= cy + y

setpixel ( x , y )  // Put or set the New pixel 

 

10. Now at execution of Loop the line will be printed

For Any query feel free and post the question you will get feedback within 2 hours

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

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.

Explain HeapSort With Example

Heap Sort is a Sorting Mechanism Developed by J. W. J. Williams 

We have looked at various Sorting Algorithms but the faster sorting algorithms  in the average and best case time and Algorithm that did not require any space over and above what was needed to store the input is a Heap Sort Algorithm