# Help!!

Discussion in 'C' started by Levi, Sep 15, 2004.

1. ### LeviNew Member

Joined:
Aug 21, 2004
Messages:
30
0
Trophy Points:
0
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,
 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  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:  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  37 48 50 [92 87]
pivot
stage 6: 10 25 33 37 48 50 [92 87]
stage 7: 10 25 33 37 48 50  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

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
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

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
I have choosen the middle one
Code:
`pivot=a[(left+right)/2];`

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
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;
}```

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
Regarding your Fill I could not get what you meant and the input and output stuffs. Try to be more clear if possible.

6. ### LeviNew Member

Joined:
Aug 21, 2004
Messages:
30
0
Trophy Points:
0
Hey,
Thanks for all your help. I'll try it and tell you how it goes.
Levi

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
My Pleasure
I will wait for that.

Thanks
Shabbir Bhimani

8. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
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

9. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
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

10. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
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

Last edited: Dec 31, 2004
11. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
ok...this is really buggin me...the website automatically takes out the spaces
im gonna put 0's where the spaces shud b
HERE YA GO (better work)
input =
*****
*000*
*000*
*000*
*****
then output:
*****
*****
*****
*****
*****

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

Ellipse:
000*****
0**00000**
*000000000*
*000000000*
*000000000*
*000000000*
*000000000*
0**00000**
000*****

The letter H:
***0000***
*0*0000*0*
*0*0000*0*
*0******0*
*000000000*
*0******0*
*0*00000*0*
*0*00000*0*
***00000***

BETTER WORK OR I GIVE UP
Thanks
-Blaze

12. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
to make it look better just take out the 0's and put spaces in... Remember only the asterisks are the boundaries
Thanks
-Blaze

13. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
-blaze

14. ### alokNew Member

Joined:
Jul 24, 2004
Messages:
127
2
Trophy Points:
0
Occupation:
S/W Engg
http://www.thatsalok.com
Have tried your self yet Mr Blaze.
just try and then post your Source COde here,then we can help.
NO body going to write full source Code for you HERE!!

15. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
heres what i have so far...i think this is the right logic but sum numbers are screwy or sumthing

/* fill.c is a program that takes an input of a boundary and
* the coordinates of an interior point. The program then takes
* those and dispays the boundary but as a closed shape. It
* fills the shape.
*/

#include "stdafx.h"
#include "simpio.h"
#include "strlib.h"

void fill(int Row, int Column, char Shape);
void GO(int Row, int Column, char Shape);

main(int count, int Count , int Sentinel, char Temp, int Row, int Column, string check)
{
char Shape;
for(count = 0; count < 21; count++) {
for(Count = 0; Count < 21; Count++) {
Shape[count][Count] = ' ';
}
}
Sentinel = 0;
printf("Start Entering Your Shape One Character At A Time And Enter  when done \n");
printf("Only 20 Rows & Columns Max \n");
for(Count = 0; Sentinel != 1; count++) {
for(count = 0; Sentinel != 1; count++) {
Temp = getchar();
if(Temp == '0') {
Sentinel = 1;
}
Shape[Count][count] = Temp;
}
}
check = GetLine();
printf("\nNow Enter The Row of the inner coordinate \n");
Row = (GetInteger() - 1);
printf("Now Enter The Column of the inner coordinate \n");
Column = (GetInteger() - 1);
fill(0, 0, Shape);
printf("\n");
}

void fill(int Row, int Column, char Shape)
{
if(Shape[Row][Column] != ' ' && Shape[Row][Column] != '0') {
printf("*");
} else {
GO(Row, Column, Shape);
}
if(Column == 20 && Row < 20) {
printf("\n");
fill(Row + 1, 0, Shape);
}
else if(Row < 20 && Column < 20) {
fill(Row, Column + 1, Shape);
}
}

void GO(int Row, int Column, char Shape)
{
int check = 0;
for(int count = Row; count >= 0; count = count - 1) {
if(Shape[count][Column] != ' ' && Shape[count][Column] != '0') {
check = check + 1;
count = 0;
}
}
for(int count = Row; count <= 20; count++) {
if(Shape[count][Column] != ' ' && Shape[count][Column] != '0') {
check = check + 1;
count = 20;
}
}
for(int count = Column; count >= 0; count = count - 1) {
if(Shape[Row][count] != ' ' && Shape[Row][count] != '0') {
check = check + 1;
count = 0;
}
}
for(int count = Column; count <= 20; count++) {
if(Shape[Row][count] != ' ' && Shape[Row][count] != '0') {
check = check + 1;
count = 20;
}
}
if(check == 4) {
printf("*");
} else {
printf(" ");
}
}

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
Instead of posting the complete code if you can lay us the problem are we can help or you can use http://www.globaldevelopers.net/ and some software developer will do it for you also.

Last edited: Jan 3, 2005
17. ### BlazeBNew Member

Joined:
Dec 31, 2004
Messages:
8
0
Trophy Points:
0
the problem is, I can't get the program to function correctly but i dont know where the prob is...btw alok, the user that posted b4 u told me to post my source code. If you want to know what the prgm is supposed to do then read the first descriptions and look at my pictures (it's the fill.c prgm)
-Blaze

Joined:
Jul 12, 2004
Messages:
15,346
382
Trophy Points:
83
Yes I have read that and also if you have read this thread I have helped the guy who has started. Seeing the program and running is a difficult task but if you can recognize the problem are you can use this forums or you can use our partner sites for the work also.

19. ### LeviNew Member

Joined:
Aug 21, 2004
Messages:
30
0
Trophy Points:
0
Hey,
I am taking a course through epgy. Write what you have of the program
so far, and I'll see how I can help. Sorry for not responding sooner.
Levi

20. ### LeviNew Member

Joined:
Aug 21, 2004
Messages:
30
0
Trophy Points:
0
Hey,
I'm going to post the code for the fill.c program. I'm assuming that you have not completed it right? Use the code as a helper, don't just copy and paste. See if you can understand what is going on in there, and if you don't write back and ask your questions.
Of course, the fill function is the heart of the program. The Square, Circle and H, functions just make it easier to use the program. I found it near impossible to make it easy to imput a shape, so I wrote those. It's nice to know that there is someone else out there taking a programming course with EPGY. Levi

/*
* This program fills in a recursive way the area enclosed
* by a shape from a given interior point without exeeding
* the boundary of the shape.
*/

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"
#include "conio.h"
#define height 15
#define width 12

string shape[height][width];
void getinput(string shape[height][width]);
void printshape(string shape[height][width]);
void fill(string shape[height][width],int x, int y);
void square(string shape[height][width]);
void circle(string shape[height][width]);
void H(string shape[height][width]);
void prntsquare(string shape[height][width]);
main()
{
int x, y,ans;
printf("This program fills in a recursive way the area enclosed\nby a shape from a given interior point without exeeding\nthe boundary of the shape.\n");
printf("\n\nDo you want to see a \n1)square\n2)circle\n3)the letter H\n4)input yourself?\n");
printf("Type the number to make your selection....for example,\nfor square,enter number 1\n");
ans=GetInteger();
switch(ans)
{
case 1: square(shape);break;
case 2: circle(shape);break;
case 3: H(shape);break;
case 4: getinput(shape);break;
}
printf("Enter a x start position that is not an astrick.");
x=GetInteger();
printf("Enter a y start position that is not an astrick.");
y=GetInteger();
printshape(shape);
fill(shape,x,y);
printshape(shape);
}
void H(string shape[height][width])
{
int u,i;
clrscr();
for(u=0;u<height;u++)
{
for(i=0;i<width;i++)
{
shape=" ";
}
}
for(u=0;u<=11;u++)
{
shape="*";
shape="*";
}
for(i=0;i<=9;i++)
{
if((((((i==0||i==1||i==2||i==7||i==8||i==9))))))
{
shape="*";
shape="*";
}
else
{
shape="*";
shape="*";
}
}
shape="*";
shape="*";
shape="*";
shape="*";
for(u=1;u<4;u++)
{
shape="*";
shape="*";
}
for(u=7;u<11;u++)
{
shape="*";
shape="*";
}
}
void circle(string shape[height][width])
{
int n, n1;
for(n=0;n<height;n++)
{
for(n1=0;n1<width;n1++)
{
shape[n][n1]=" ";
}
}
for(n=3;n<(width-3);n++)
{
shape[n]="*";
shape[n]="*";
}
for(n1=3;n1<12;n1++)
{
shape[n1]="*";
shape[n1]="*";
}
shape="*";
shape="*";
shape="*";
shape="*";
shape="*";
shape="*";
shape="*";
shape="*";
}

void square(string shape[height][width])
{
clrscr();
prntsquare(shape);
printf("\n\nEnter a co-ordinate inside the square");
}

void prntsquare(string shape[height][width])
{
int a,b;
for(a=0;a<height;a++)
{
for(b=0;b<width;b++)
{
shape[a]=" ";
}
}

for(a=0;a<9;a++)
{
shape[a]="*";
shape[a]="*";
}
for(b=0;b<12;b++)
{
shape="*";
shape="*";
}

for (a=0;a<height;a++)
{
for(b=0;b<width;b++)
{
printf("%s",shape[a]);
}
printf("\n");
}
}

void getinput(string shape[height][width])
{
int col, row,var;
var=0;
clrscr();

for(row=0;row<height;row++)
{
for(col=0;col<width;col++)
{
shape[row][col]=" ";
}
}
printf("The maximum limits for the shape is %d from top to bottom,\nand %d from left to right.\n",height,width);
printf("Enter your shape from left to right, top to bottom.\n");
printf("Each time you enter a astrick, the shape will print,\nshowing you what you have inputed sofar.");
printf("Enter \"-1\", to signal that you are done inputing.");
for(row=0;row<height;row++)
{
for(col=0;col<width;col++)
{
shape[row][col]=GetLine();
printf("\n");
if(StringEqual(shape[row][col],""))shape[row][col]=" ";
if(StringEqual(shape[row][col],"-1"))
{
shape[row][col]=" ";
printshape(shape);
var=-1;
break;
}
printshape(shape);
}
if(var==-1)
{
break;
}
printf("New line.");
}
}

void printshape(string shape[height][width])
{
int r,c;
for (r=0;r<height;r++)
{
for(c=0;c<width;c++)
{
printf("%s",shape[r][c]);
}
printf("\n");
}
printf("\n");
}

void fill(string shape[height][width],int x,int y)
{
if(StringEqual(shape[x][y],"*")==FALSE)
{
shape[x][y]="*";
fill(shape,x+1,y);
fill(shape,x-1,y);
fill(shape,x,y+1);
fill(shape,x,y-1);
}
}