Finding second largest number in an array

c programming

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 12847 Views - Last Post: 04 October 2009 - 01:01 AM Rate Topic: -----

#1 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Finding second largest number in an array

Posted 02 October 2009 - 05:21 PM

#include <stdio.h>
#include <stdlib.h>

void partially_fill(int *arr, int max_elements, int *p_n_elements);
/*
 *  Partially fill an array with user-supplied values.
 *
 *  REQUIRES
 *	 User is ready to respond to prompts for input.
 *	 max_elements > 0.
 *	 Array elements arr[0] ... arr[max_elements - 1] exist.
 *	 p_n_elements points to an int variable.
 *
 *  PROMISES
 *	 If user enters bad input, exit is called with an arg of 1.
 *	 Otherwise:
 *		*p_n_element contains a user-supplied value with
 *		   0 < *p_n_element and *p_n_element <= max_elements;
 *		arr[0] ... arr[*p_n_element - 1] contain user-supplied values;
 *		the other array elements are untouched.
 */
 
int read_int_only(void);
/*
 *  Read an int, then skip to the end of a line of input.
 *
 *  REQUIRES
 *	 User has been prompted to enter an int.
 *  PROMISES
 *	 If user enters bad input, exit is called with an arg of 1.
 *	 (Bad input includes constants of type double.)
 *	 Otherwise:
 *		Characters following the int are discarded up to
 *		end-of-line or end-of-file, whichever is first.
 *		Return value is the int that was read.
 */

void echo_array(const int *arr, int n_elements);
/*
 *  REQUIRES
 *	 n_elements > 0.
 *	 Array elements arr[0] ... arr[n_elements - 1] exist.
 *  PROMISES
 *	 Values of arr[0] ... arr[n_elements - 1] are printed on
 *	 a single line of output.
 */

int non_decreasing(const int *arr, int n_elements);
/*
 *  REQUIRES
 *	 n_elements > 0.
 *	 Array elements arr[0] ... arr[n_elements - 1] exist.
 *  PROMISES
 *	 If n_elements == 1, the return value is 1.
 *	 If n_elements > 1, return value is:
 *	   1 if arr[0] <= arr[1], ... , arr[n_elements-2] <= arr[n_elements-1]; 
 *	   0 otherwise.
 */

int index_of_smallest(const int *arr, int n_elements);
/*
 * REQUIRES
 *  n_elements > 0.
 *  Array elements arr[0] ... arr[n_elements - 1] exist.
 * PROMISES
 *   Finds and returns the index of the smallest element. 
 *   We assume the first element is the smallest, then we compare it to the other elements.
 */   
int second_largest(const int *arr, int n_elements);
int main(void)
{
  int arr[10];			/* test data from user goes here */
  int n_arr;			/* number of valid elements in arr */
  
  printf("This program tests array functions.\n");
  printf("Please enter some array element values.\n");
  partially_fill(arr, 10, &n_arr);
  printf("\nYou entered %d elements, which are:\n", n_arr);
  echo_array(arr, n_arr);

  if ( non_decreasing(arr, n_arr) )
	printf("The elements are in nondecreasing order.\n");
  else
	printf("The elements are NOT in nondecreasing order.\n");

  /* STUDENTS: You will add code here to test average,
   * index_of_smallest, and second-largest.				 */
printf("The index of the smallest element in an array is: %d \n", index_of_smallest(arr, n_arr));

printf("The second largest element in an array of ints is: %d \n", second_largest(arr, n_arr));


  printf("\nThe test of array functions is over.\n");
  return 0;
}


void partially_fill(int *arr, int max_elements, int *p_n_elements)
{
  int k;
  
  printf("How many elements do you wish to enter [1 to %d]? ",
	 max_elements);
  *p_n_elements = read_int_only();
  if (*p_n_elements < 1 || *p_n_elements > max_elements) {
	printf("Illegal input.  Program terminated.\n");
	exit(1);
  }

  for (k = 0; k < *p_n_elements; k++) {
	printf("Enter an int value for element %d: ", k);
	arr[k] = read_int_only();
  }
}


int read_int_only(void)
{
  int value_read;
  int char_code;

  if (scanf("%d", &value_read) != 1) {
	printf("Error trying to read in an integer.  Program terminated.\n");
	exit(1);
  }

  /* OK, an int has been read.  But what is the next character? */
  char_code = getchar();
  if (char_code == '.' || char_code == 'e') {
	printf("Apparent attempt to enter a double constant.  ");
	printf("Program terminated.\n");
	exit(1);
  }

  /* Throw away characters up to and including the end of the line. */
  while (char_code != '\n' && char_code != EOF)
	char_code = getchar();

  return value_read;
}


void echo_array(const int *arr, int n_elements)
															{
  int k;
  
  for (k = 0; k < n_elements; k++)
	printf("  %d", arr[k]);
  printf("\n");
}
	

int non_decreasing(const int *arr, int n_elements)
{
  int k;
 
  /* The algorithm below is DEFECTIVE.  It must be corrected. */
  for (k = 0; k <n_elements - 1; k++)
	if(arr[k]> arr[k+1])
  return 0;
	return 1;
}

int index_of_smallest(const int *arr, int n_elements)
{
int index;
int smallest_index = 0;

for(index = 1; index < n_elements; index++)
 if(arr[smallest_index] >= arr[index])
	 smallest_index = index;

return smallest_index;
}

int second_largest(const int *arr, int n_elements)
{
int index;
int largest = 0;
int sec_largest;
for(index = 1; index < n_elements; index++)
if(arr[largest] < arr[index])
largest = index;

..........................................
}

 


Hi!!
Ok I am trying to find the second largest element in an array.
I thought for that second_largest function I would find the largest and then somehow say sec_largest cannot be largest.

Also if the user enters two equal large numbers then the sec_largest=largest

so if the user enters 22 44 44 11

it should say the seocnd largest is 44

How can I find the second largest?
Am I on the right track?

thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Finding second largest number in an array

#2 OliveOyl3471  Icon User is offline

  • Everybody's crazy but me!
  • member icon

Reputation: 134
  • View blog
  • Posts: 6,581
  • Joined: 11-July 07

Re: Finding second largest number in an array

Posted 02 October 2009 - 06:53 PM

The way I would do it is to sort the array and access the second to last element (if you know how many elements are in the array). If you don't know how many numbers are input you can sort the array backward (highest to lowest) and access the second element.

Others probably have a better solution though. :)
Was This Post Helpful? 0
  • +
  • -

#3 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 02 October 2009 - 07:33 PM

Ooo ok!!
I think I could work a code from that.
It seems like it could be easier then what I was thinking of :P

Thank you for your help!

This post has been edited by brac589: 02 October 2009 - 07:34 PM

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5642
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Finding second largest number in an array

Posted 03 October 2009 - 05:55 AM

You're close. It's essentially a one liner so I'll give it to you.
int second_largest(const int *arr, int n_elements) {
	int index, largest_idx, sec_largest_idx;

	// everyone has got to start somewhere
	largest_idx = sec_largest_idx = 0;
	
	for(index = 1; index < n_elements; index++) {
		if(arr[largest_idx] < arr[index]) {
			// before you assign the largest
			// move the current largest down
			sec_largest_idx = largest_idx;
			
			largest_idx = index;
		}
	}
	return sec_largest_idx;
}


Was This Post Helpful? 0
  • +
  • -

#5 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 09:07 AM

Ok this reassuring.
I did get the same thing as you late last night without using sorting.

However If a user enters 44 44 22 11
Then the second largest should be 44...I am getting 22


I have been trying to fix this for a while and not sure how
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5642
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Finding second largest number in an array

Posted 03 October 2009 - 12:00 PM

View Postbrac589, on 3 Oct, 2009 - 10:07 AM, said:

However If a user enters 44 44 22 11
Then the second largest should be 44...I am getting 22


Ouch, that's a bit of a worst case there. Sorry I didn't spot it.

If the first number is the largest, nothing ever swaps. We need to make sure the second number is not equal the first no matter what. Happily, you can fix this with two lines.

int second_largest(const int *arr, int n_elements) {
	int index, largest_idx, sec_largest_idx;

	largest_idx = sec_largest_idx = 0;
	
	for(index = 1; index < n_elements; index++) {
		if(arr[largest_idx] < arr[index]) {
			sec_largest_idx = largest_idx;
			largest_idx = index;
		} else if(arr[largest_idx]==arr[sec_largest_idx]) {
			sec_largest_idx = index;
		}
	}
	return sec_largest_idx;
}



This may see off, but it's not. The first will only equal the second if it starts off and hasn't found a good different lower value. Once the second is different from the first, everything proceeds properly.
Was This Post Helpful? 1
  • +
  • -

#7 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 12:29 PM

Thank you i got it :P
One more question though...
When I executed the code like yours, with the brackets like what you showed...My output would say sec_largest is 22.

int second_largest(const int *arr, int n_elements) 
{		
int index, largest_idx, sec_largest_idx;		
largest_idx = sec_largest_idx = 0;				
for(index = 1; index < n_elements; index++) 
{				
if(arr[largest_idx] < arr[index]) 
{						
sec_largest_idx = largest_idx;						
largest_idx = index;				
}
 else if(arr[largest_idx]==arr[sec_largest_idx]) 
{						
sec_largest_idx = index;				
}		
}		
return sec_largest_idx;
}



When i only used brackets for the for-loop, my output for sec_largest was 44.
Can anybody explain why?


int second_largest(const int *arr, int n_elements)
{
int index;
int largest, sec_largest;
largest = sec_largest = 0;
for(index = 1; index < n_elements; index++)
{
if(arr[largest] < arr[index])
sec_largest = largest;
largest = index;

if(arr[largest] == arr[sec_largest])
sec_largest = index;
}
return arr[sec_largest];

}



C programming is much different to C++

This post has been edited by brac589: 03 October 2009 - 12:31 PM

Was This Post Helpful? 0
  • +
  • -

#8 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 12:40 PM

ok so it doesnt work

I said 2 4 6 8
and it said sec_largest is 6

Thats correct

i said 44 44 22 11
it said sec_largest is 44

Thats correct

Then i said 20 33 25 10
and it said sec_largest is 20

That is Incorrect


I am not sure what is happening aha.
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5642
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Finding second largest number in an array

Posted 03 October 2009 - 12:55 PM

View Postbrac589, on 3 Oct, 2009 - 01:29 PM, said:

C programming is much different to C++


Quite. They are really very different animals. However, the brace thing is universal.

If you are confused by braces, then always use them. Always. It's simply too easy to screw up if you don't.

// I did this:
if(arr[largest_idx] < arr[index]) {
	sec_largest_idx = largest_idx;
	largest_idx = index;
}

// you did this
if(arr[largest] < arr[index])
sec_largest = largest;
largest = index;

// let's add a little formatting
if(arr[largest] < arr[index])
	sec_largest = largest;
largest = index;

// or some braces
if(arr[largest] < arr[index]) {
	sec_largest = largest;
}
largest = index;



See the difference? I said "if this is true, execute these two lines." You said "If this is true, execute this single line. Then always execute the next line."

// this line
if(n==1) return;

// and this line
if(n==1) { return; }

// are identical



If you never leave the braces of your blocks, even though you can on single statements, you might have less of a problem.

Also, pick an indent style and stick with it. Be consistent so you can highlight what's going on.
int second_largest(const int *arr, int n_elements)
{
	int index;
	int largest, sec_largest;
	
	largest = sec_largest = 0;
	for(index = 1; index < n_elements; index++)
	{
		if(arr[largest] < arr[index])
			sec_largest = largest;
		largest = index;

		if(arr[largest] == arr[sec_largest])
			sec_largest = index;
	}
	
	return arr[sec_largest];
}



Consistency will help you spot errors.
Was This Post Helpful? 0
  • +
  • -

#10 aks29921  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 84
  • View blog
  • Posts: 230
  • Joined: 24-August 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 01:05 PM

View Postbrac589, on 3 Oct, 2009 - 11:29 AM, said:

int second_largest(const int *arr, int n_elements)
{
int index;
int largest, sec_largest;
largest = sec_largest = 0;
for(index = 1; index < n_elements; index++)
{
if(arr[largest] < arr[index])
sec_largest = largest;
largest = index;
if(arr[largest] == arr[sec_largest])
sec_largest = index;
}
return arr[sec_largest];
}


of course this code has a basic flaw, once you get a value in sec_largest, it is only updated depending on the change in value of largest....
in 20,33,25:
first, sec_largest is 0 and largest is 20,
next time sec_largest is 20 and largest is 33
& finally 25 is compared to 33 and since it is less, no change in the value of sec_largest and you get 20..

my suggestion:
use nested for loops, first loop i=1 to n where largest is updated and the second loop j=1 to i where sec_largest is updated (so that you can keep track of the entire array instead of only the last value)....

hope this helps
Was This Post Helpful? 1
  • +
  • -

#11 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 03:56 PM

int second_largest(const int *arr, int n_elements)
{
	int index, j;
	int largest, sec_largest;
	largest = sec_largest = 0;

	for(index = 1; index < n_elements; index++)
	{
		for(j = 1; j < index; j++)
		{
			if(arr[largest] < arr[index])
				largest = index;
			 if (arr[sec_largest] < arr[index])
			sec_largest = largest;.  /* I really messed this part up any suggestions? */
		}
	}

	return arr[sec_largest];

}
 


Like this???
Could I maybe cll the function index_of_smallest?
I dont think it will help much...

This post has been edited by brac589: 03 October 2009 - 04:10 PM

Was This Post Helpful? 0
  • +
  • -

#12 IngeniousHax  Icon User is offline

  • |>|20-514<|{3|2

Reputation: 78
  • View blog
  • Posts: 1,358
  • Joined: 28-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 04:23 PM

Are you attempting a bubble sort to solve this?
Was This Post Helpful? 0
  • +
  • -

#13 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 04:29 PM

I tried, but it didnt work well...
I am trying to find the second largest.
So i find my largest and then somehow find the second


int second_largest(const int *arr, int n_elements)
{
	int index, j;
	int largest, sec_largest;
	largest = sec_largest = 0;

		for(index = 1; index < n_elements; index++)
	{
		for(j = 1; j < index; j++)
		{
			if(arr[largest] < arr[index])
				largest = index;


			 if (arr[sec_largest] < arr[j])
				sec_largest = j;
		}
	}

	return arr[sec_largest];

}



It doesnt work

This post has been edited by brac589: 03 October 2009 - 04:35 PM

Was This Post Helpful? 0
  • +
  • -

#14 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 04:43 PM

ok I have noticed that If i enter my smallest value after my largest. Then my second largest is my largest.

if I enter 50 60 80 3

My sec_largest is 80

if i enter 50 60 3 80

My sec_largest is 60

Why??
Was This Post Helpful? 0
  • +
  • -

#15 IngeniousHax  Icon User is offline

  • |>|20-514<|{3|2

Reputation: 78
  • View blog
  • Posts: 1,358
  • Joined: 28-March 09

Re: Finding second largest number in an array

Posted 03 October 2009 - 04:43 PM

Well, to start off, I think you're making the bubble sort far too difficult. It should basically use a variable to run through an array, and than compare each value of the array...

//this is a quick show
for(int x = 0; x < ARRAY_SIZE; x++) {
	  if(array[x] < array[x + 1]) {
		  index = array[x];
		  array[x] = array[x + 1];
		  array[x] = index;
	  }
	 else // Im sure you could figure this out from here.


This post has been edited by IngeniousHax: 03 October 2009 - 04:44 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2