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

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