[willist]

Good Evening. I am working on a homework problem and I have hit a little snag. The problem has three parts. First, fill an array with 20 random values. Second, quicksort the array using a quicksort algorithm. Third, call look_up and print the result. You may prompt the user to enter a value to look up.
Okay so I have sucesfully completed the first and second part but am clueless as to how to proceed for the third step. The code is posted below. Any help would be appreciated. Regards, Willis.

#include <stdio.h>
#define MAXIMUMARRAYSIZE 20

void quicksort(int arr[], int low, int high);

int main(void) {
int array[MAXIMUMARRAYSIZE] = {0};
int i = 0;
for(i = 0; i < MAXIMUMARRAYSIZE; i++)
array[i] = rand() % 100; 
printf("Array filled with random values: ");
 for(i = 0; i < MAXIMUMARRAYSIZE; i++) {
  printf(" %d ", array[i]); 
 }
 printf("\n--------------------");

quicksort(array, 0, (MAXIMUMARRAYSIZE - 1));
printf("Array sorted using quicksort algorithm: ");
 for(i = 0; i < MAXIMUMARRAYSIZE; i++) {
  printf(" %d ", array[i]); 
 }
 printf("\n--------------------");
 return 0;
}

void quicksort(int arr[], int low, int high) {
 int i = low;
 int j = high;
 int y = 0;
 int z = arr[(low + high) / 2];
 do {
 while(arr[i] < z) i++;
 while(arr[j] > z) j--;
 if(i <= j) {
    y = arr[i];
   arr[i] = arr[j]; 
   arr[j] = y;
   i++; 
   j--;
  }
 } while(i <= j);


 if(low < j) 
  quicksort(arr, low, j);

 if(i < high) 
  quicksort(arr, i, high); 
}

[jjl]

what do you mean clueless? you have already done the hard part, just copy and paste the method into a void function.

look

void look_up(int *arr)
{
        int i;
	printf("Array sorted using quicksort algorithm: ");
	for(i = 0; i < MAXIMUMARRAYSIZE; i++)
		printf(" %d ", arr[i]); 
	
}

int main()
{
	//your sorting stuff
        //then output 
	look_up(array);

This post has been edited by ImaSexy: 18 April 2010 - 08:36 PM

[willist]

ImaSexy, on 18 April 2010 - 07:30 PM, said:

what do you mean clueless? you have already done the hard part, just copy and paste the method into a void function.

look

void look_up(int *arr)
{
	printf("Array sorted using quicksort algorithm: ");
	for(i = 0; i < MAXIMUMARRAYSIZE; i++)
		printf(" %d ", arr[i]); 
	
}

int main()
{
	//your sorting stuff
        //then output 
	look_up(array);

The only part that I don't get is how do i get it to search for a user-input value?

[Oler1s]

If in real life, I gave you a page containing a list of numbers. Then I told you to find if the number 2 was in the list. What would you do?

[jjl]

like for a specific index?

void look_up(int *arr, int index)
{
		printf(" %d ", arr[index]); 
}

but off topic, your code is missing headers. Also the rand() functions depends on something called a "seed" (number for random algorithm). A computer cannot just spit out a random number, it needs a seed that is always changing so the random numbers are different everytime your run the program. User srand(time(0)); to set the "seed" to the computer clock so it is always changing

#include <stdio.h>
//neeed these
#include <stdlib.h>
#include "time.h"

#define MAXIMUMARRAYSIZE 20

void quicksort(int arr[], int low, int high);
void look_up(int *arr);

int main(void) 
{
	srand(time(0)); //set the seed for the rand() algorithm to the clock so it really is RANDOM
	int array[MAXIMUMARRAYSIZE] = {0};
	int i;
	for(i = 0; i < MAXIMUMARRAYSIZE; i++)
		array[i] = rand() % 100; 
	printf("Array filled with random values: ");
	for(i = 0; i < MAXIMUMARRAYSIZE; i++) {
		printf(" %d ", array[i]); 
	}
	printf("\n--------------------");

	quicksort(array, 0, (MAXIMUMARRAYSIZE - 1));
	look_up(array);
	
	printf("\n--------------------");
	getchar();
	return 0;
}

void look_up(int *arr, int index)
{
		printf(" %d ", arr[index]); 
}
void quicksort(int arr[], int low, int high)
{
	int i = low;
	int j = high;
	int y = 0;
	int z = arr[(low + high) / 2];
	do {
		while(arr[i] < z) i++;
		while(arr[j] > z) j--;
		if(i <= j) {
			y = arr[i];
			arr[i] = arr[j]; 
			arr[j] = y;
			i++; 
			j--;
		}
	} while(i <= j);


	if(low < j) 
		quicksort(arr, low, j);

	if(i < high) 
		quicksort(arr, i, high); 
}

[willist]

Oler1s, on 18 April 2010 - 07:38 PM, said:

If in real life, I gave you a page containing a list of numbers. Then I told you to find if the number 2 was in the list. What would you do?

I would scan the page and take note every time I found a 2?

[Oler1s]

Quote

I would scan the page

Define scan the page. Cast voodoo magic that makes every number that is 2 glow? Or what?

[willist]

I think maybe I posed the question wrong. This is the third step as written on the instruction...

5. (here, you may want to ask the user to enter the value for v to
look up in a),
6. call look_up(), and
7. print the result of lookup.

Oler1s, on 18 April 2010 - 07:59 PM, said:

Quote

I would scan the page

Define scan the page. Cast voodoo magic that makes every number that is 2 glow? Or what?

I wish that would make my life alot easier. Okay I would start as the beggining and scan the page line by line. Every time I saw a two I would note it's location in the array and then reference that location later if I wanted to find the number again?

This post has been edited by willist: 18 April 2010 - 09:03 PM

[Oler1s]

When I look at those steps, I think of two perfectly valid ways to interpret them.

1. You are looking up the data at a certain position (i.e. you know position, want to know data). So if I have a list of numbers, I'm asking for things like, what's the 5th number, what's the 12th number? etc.

2. You want to find the position of certain data (i.e. you know data, want to know position). So if I have a list of numbers, I'm asking for things like, where is the number 2? where is the number 56? etc.

Question 2 is more complex of course. What's more complex is that a) the data may not exist, and you need to handle this properly and there may be more than one instance of that data.

In the case of b, you need to find out how it should be handled. Sane defaults are: list of positions, first position, last position.

EDIT: "Every time I saw a two I would note it's location in the array and then reference that location later if I wanted to find the number again? "

Yes, precisely. And in trying to break this problem down, you have to determine what "note it's location" and "reference that location" mean.

Everything in the end collapses down to understanding data structures and algorithms. When you have a complex problem, you cannot solve it until you understand how data is being stored, and how it being manipulated.

This post has been edited by Oler1s: 18 April 2010 - 09:06 PM

[willist]

Oler1s, on 18 April 2010 - 08:04 PM, said:

When I look at those steps, I think of two perfectly valid ways to interpret them.

1. You are looking up the data at a certain position (i.e. you know position, want to know data). So if I have a list of numbers, I'm asking for things like, what's the 5th number, what's the 12th number? etc.

2. You want to find the position of certain data (i.e. you know data, want to know position). So if I have a list of numbers, I'm asking for things like, where is the number 2? where is the number 56? etc.

Question 2 is more complex of course. What's more complex is that a) the data may not exist, and you need to handle this properly and there may be more than one instance of that data.

In the case of b, you need to find out how it should be handled. Sane defaults are: list of positions, first position, last position.

Okay this is what I was thinking. I want to search the array for a value and then print the location of that value in the array if that value exists in the array. Otherwise, if the value is not found, maybe use a printf statement to inform the user. An if-else statement might work for this.

[Oler1s]

Quote

Otherwise, if the value is not found, maybe use a printf statement to inform the user.

Really? You sure about this?

Let me give you an absurd example, but one that illustrates my point. Let's assume the following code:

// ... necessary junk
    std::cout << "Hello, World\n";
    //... remaining part
    

Now imagine that the << operator, in addition to spitting out Hello, World on the screen, also flushes your bathroom toilet. Err. what? But it does this.

You might be really, really unhappy. You see, the job of << should be output. But it's doing something that isn't it's job. Furthermore, you can't do anything about it! Output and flushing the toilet are (very) stupidly coupled together.

Coupling is an important concept is software development. It's a really bad thing to do. Going to back to your original question. You have a function lookUp that needs to find the position of something. If it fails, your function prints to screen the failure. It is coupling printing to screen to failure. What if you needed to print to file, later on? Print to database. Print to website. Make red bulb glow. Make a beep sound. Who knows?

You want to communicate that the function failed. How can you do this, without printing anything to screen? (Hint: everyone is going to look at what you return, right?)

[willist]

Oler1s, on 18 April 2010 - 08:16 PM, said:

Quote

Otherwise, if the value is not found, maybe use a printf statement to inform the user.

Really? You sure about this?

Let me give you an absurd example, but one that illustrates my point. Let's assume the following code:

// ... necessary junk
    std::cout << "Hello, World\n";
    //... remaining part
    

Now imagine that the << operator, in addition to spitting out Hello, World on the screen, also flushes your bathroom toilet. Err. what? But it does this.

You might be really, really unhappy. You see, the job of << should be output. But it's doing something that isn't it's job. Furthermore, you can't do anything about it! Output and flushing the toilet are (very) stupidly coupled together.

Coupling is an important concept is software development. It's a really bad thing to do. Going to back to your original question. You have a function lookUp that needs to find the position of something. If it fails, your function prints to screen the failure. It is coupling printing to screen to failure. What if you needed to print to file, later on? Print to database. Print to website. Make red bulb glow. Make a beep sound. Who knows?

You want to communicate that the function failed. How can you do this, without printing anything to screen? (Hint: everyone is going to look at what you return, right?)

Return a -1?

[Oler1s]

Quote

Return a -1?

That sounds like an excellent idea, doesn't it?

[willist]

Oler1s, on 18 April 2010 - 08:34 PM, said:

Quote

Return a -1?

That sounds like an excellent idea, doesn't it?

Your logic is impeccable. So how would I go about searching for this value in the array?

[jjl]

well your gonna need a loop right?

void look_up(int *arr, int value)
{
	for(i = 0; i<MAXIMUMARRAYSIZE; i++)
	{
		//if the value inputted equals any value in the array
		// return that position (i)
		//else return a error value
	}


}