Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Help!! (http://www.go4expert.com/forums/help-t171/)

Levi 15Sep2004 07:09

Help!!
 
Hey everyone,
I am having big problems with three problems. The programs are quicksort.c, fill.c, and removedup.c. Can you give me any help. Thanks so much. Here are the instructions.
Levi


Quicksort.c

Write a program that implements the quicksort algorithm. Quicksort is a popular sorting
algorithm, developed by the British Computer Scientist Tony Haore.
Your input consists of a list of words and the output should display the same list but sorted.
For example, if the input is:
Russian English Italian Spanish Hebrew French German
the output will be:
English French German Hebrew Italian Russian Spanish
The method of quicksort works in the following way; For the input array,
25 50 48 37 10 92 87 33
we will need to follow these steps:
1. We first choose one element from the input numbers which serves as the boundary between
the small and large elements. This element is called the pivot. You can choose any element
for this purpose, and the simplest way is to select the first element in the array, namely 25 in
this example will be the current pivot.
2. At the next stage, we rearrange the elements of the array so that large elements are moved to
the end of the array and small elements toward the beginning. By the end of this stage we’ll
get the following array,
10 25 50 48 37 92 87 33
elements pivot elements larger than 25
less than 25
Note that 25 is now positioned in its right location.
By the end of this stage we got two sub arrays,
[10] and [5048 37 92 87 33] that need to be treated at the same way.
3. At the next stage we sort the elements of each of the sub arrays. Because all elements to the
left of the pivot boundary are strictly less than all those to the right, sorting each of the sub
arrays must leave the entire array in sorted order. These sub arrays can be sorted using a
recursive application of quicksort.
For the sub array [10] we do not need to do anything since it contains only one element. So
we need to repeat this process only for the sub array [50 48 37 92 87 33].
4. The current pivot now is 50 (since this is the first element of the current sub array.)
Once again we rearrange the elements of this sub array so that the large elements are moved
toward the end of the sub array and small elements towrd the beginning as follows,
10 25 [48 37 33] 50 [92 87]
This process will be repeated for the two new sub arrays that were created, and so forth until all
the array is sorted.
c11b - Programming Exercises - 37 -
As a whole, the passes for this input can be described in the following way,
input: 25 50 48 37 10 92 87 33
stage 1: [10] 25 [50 48 37 92 87 33]
pivot
stage 2: 10 25 [50 48 37 92 87 33]
stage 3: 10 25 [48 37 33] 50 [92 87]
pivot
stage 4: 10 25 [37 33] 48 50 [92 87]
pivot
stage 5: 10 25 [33] 37 48 50 [92 87]
pivot
stage 6: 10 25 33 37 48 50 [92 87]
stage 7: 10 25 33 37 48 50 [87] 92
pivot
stage 8: 10 25 33 37 48 50 87 92
Try to implement this algorithm in a recursive way. Run your program on any input you wish of
size >= 20.


Fill.c

Write a program that gets as an input:
• A perimeter (boundary) of a “closed” shape, such as an ellipse, circle, etc,.
• Coordinates of an interior point.
The program should fill in a recursive way the area (enclosed by) this shape from the given
interior point without exceeding the boundary of this shape. For example if the input:
***** *****
* * *****
* �� * then the output will be: *****
* * *****
***** *****
Instructions
The input will include:
• m lines, each including n characters. If the character read is not a space, the character belongs
to the boundary of the shape.
• Two numbers that specify the coordinates, namely the row and column indices of the point
from which the program is supposed to start filling the shape.
You can assume that this input point is inside the shape and that the shape is really closed. The
interior point is such that to any direction you “go” from this point, you will eventually reach the
boundary.
Note that the perimeter is represented as a sequence of characters (asterisks).
The program should display both the shapes before filling the shape and after filling the shape.
For example, for the following shape and point,
***** *****
* * * * point in location [3,6]
* *** *
* �� *
* *
*************
the input will consist of:
1. Six lines as follows,
***** *****
* * * *
* *** *
* *
* *
*************
2. The pair (3 , 6)
c11b - Programming Exercises - 39 -
Run your program on the following shapes,
Rectangle:
**********
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
**********
Ellipse:
******
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* * ******
The letter “H”:
*** ***
* * * *
* * * *
* * * *
* ****** *
* *
* ****** *
* * * *
* * * *
* * * *
* * * *
*** ***
Hints
1.The recursive procedure, fill, should be very short..
The procedure, fill, takes three arguments: Row and column of the current point checked and the
multidimensional array that represents the shape.
2. Think of a simple end condition, and of the neighbouring cells.

Removedup.c

Write a program that removes all duplicate values from a sorted array of integers, leaving only a
single copy of each value. For example if the input array is inpArray with the following values,
InpArray
50 60 70 70 72 80 85 85 90 100
then the output array will be,
OutArray
50 60 70 72 80 85 90 100
Your program should include a function named removedup that returns the new size of the array
(without the duplicates). For this input array,
removedup (inpArray, inpArraySize, outArray) �� 8
In addition, your program should display both the input array and the output array.
File name should be, removeD.c

shabbir 15Sep2004 07:25

Re: Help!!
 
Code:

void quicksort(int *a,int left,int right)
{
 int temp,l,r,pivot;
 int i;
 l=left;
 r=right;
 pivot=a[(left+right)/2];
 do
 {
  while(a[l]<pivot)
  l++;
  while(a[r]>pivot)
  r--;
  if(l<=r)
  {
    temp=a[l];
    a[l++]=a[r];
    a[r--]=temp;
  }
 }while(l<=r);
 if(left<r)
  quicksort(a,left,r);
 if(l<right)
  quicksort(a,l,right);
}

code to implement Quick Sort in a recursive way

shabbir 15Sep2004 07:54

Re: Help!!
 
Quote:

We first choose one element from the input numbers which serves as the boundary between
the small and large elements. This element is called the pivot. You can choose any element
for this purpose, and the simplest way is to select the first element in the array, namely 25 in
this example will be the current pivot.
I have choosen the middle one
Code:

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

shabbir 15Sep2004 07:54

Re: Help!!
 
Code:

int RemoveDup(int inpArr[],int size, int outArr[])
{
        int i,j;
        for(i=0,j=0;i<size;i++)
        {
                if(i==0)
                {
                        outArr[j++] = inpArr[i];
                        continue;
                }
                if(inpArr[i]!=inpArr[i+1])
                        outArr[j++] = inpArr[i];
        }
        return j;
}


shabbir 15Sep2004 08:05

Re: Help!!
 
Regarding your Fill I could not get what you meant and the input and output stuffs. Try to be more clear if possible.

Also please make your titles and other stuffs more clear and try reading this thread.

Levi 15Sep2004 08:24

Re: Help!!
 
Hey,
Thanks for all your help. I'll try it and tell you how it goes.
Levi

shabbir 15Sep2004 09:49

Re: Help!!
 
Quote:

Thanks for all your help.
My Pleasure
Quote:

I'll try it and tell you how it goes.
I will wait for that.

Thanks
Shabbir Bhimani

BlazeB 1Jan2005 02:18

Re: Help!!
 
hey...I'm a new user and i can see that u are also doing the programming course through EPGY? or no...i have similar prgms and also need help with the fill.c prgm. The prgm takes a square of astersiks and a midpoint that lays inside the square and u need the fill function to print the same square but where the inside is filled with astersiks as well as the boundary.
-Blaze

BlazeB 1Jan2005 02:26

Re: Help!!
 
to view his pictures copy his asterisk pictures then paste them in a reply box or when u are making a message like the one i am making right now... and to add to my last message...u also have to b able to run the prgm on cirlces, squares, the letter H and many other funky shapes. Thank you
-Blaze

BlazeB 1Jan2005 02:32

Re: Help!!
 
nvm bout the copy past thing... dont work.. here ya go:
input = ***** *****
* mid* then output: *****
***** *****

must b able to work on Rectangle:
********
* *
* *
* *
********

Ellipse:
*****
** **
* *
* *
* *
* *
* *
** **
*****


The letter H:
*** ***
* * * *
* * * *
* **** *
* *
* **** *
* * * *
* * * *
*** ***

I EDITED THIS MESSAGE...IT DOESNT WORK...A CORRECTED VERSION IS ON THE NEXT PAGE PLZ VISIT
Thanks
-Blaze


All times are GMT +5.5. The time now is 22:06.