Find the nth largest int in an array

How do you find the top few elements without sorting the entire array?

Page 1 of 1

4 Replies - 18109 Views - Last Post: 28 July 2009 - 01:17 PM Rate Topic: -----

#1 skorned  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • Posts: 41
  • Joined: 30-August 08

Find the nth largest int in an array

Posted 22 July 2009 - 12:16 PM

I am learning C++ and have taken up random problems from the internet as test cases. This program is basically meant to operate as a ballot system, taking in the number of candidates and voters, registering each voter's vote, and then outputting the winner. Only problem is, I don't have to output the top highest candidate, but the candidate with the third highest number of votes.

So basically, I have an array of ints, and I need to find the index of the third highest int. How do I do it efficiently and quickly, without sorting the ENTIRE array, or going through the tedious loops of finding the highest number everytime, then setting that to 0, and repeating, till I find the third highest number. Or I could have a loop which iterates through each element, checks if it is higher than a variable for the 1st, 2nd or 3rd highest ints, and if it is, replacing the respective variable with the new int.

However, these are all messed up methods where I could easily make a small mistake in the algorithm. I was searching around and saw some references that indicated that there might be a built-in function in C++, to find the nth highest element, something like std::nth_element. However, it's not showing up on Visual C++'s (I know, I know, its made by MS, but then the autosuggestions and auto-indenting and stuff are really helpful for a beginner) autosuggest, and I'm not sure what syntax to use. Can someone tell me if theres some function in the standard header files that can do this job for me? And also, a little pointer about the syntax for that function would be real nice...

and um...the array i need to sort is in dynamic memory, whose size is set while the program is running, based on user input.

I don't think the rest of my code would really help, but here it is anyways...:

// bccs.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;


void main(){
	int cand, voters;
	int * candvots = NULL;
	
	//input number of candidates, voters. Create an array of size cand-1, initialize all values to 0

	cin >> cand >> voters;
	candvots = new int[cand];

	for(int i=0; i<cand; i++){
		candvots[i]=0;
	}

	//loop through number of voters, for each vote, increase candvots[select] by 1

	int select; //which candidate each voter votes for

	for(; voters>0; voters--){
		cin >> select;
		candvots[select]++;
	}


	//loop thrice. Find highest value, delete, repeat. store third higest value to 'select'
	std::n
	//output select



	
	while(vot > 0){
		int candvotedfor;
		cin >> candvotedfor;
		candvots[candvotedfor - 1] ++;
		vot--;
	}
	int third = 0;
	int sortit = 0;
	int maxvotes = 0;
	int maxcand = 0;
	while(third < 3){
		while(sortit < cand){
			if (candvots[sortit] > maxvotes){
				maxvotes = candvots[sortit];
				maxcand = sortit;
				sortit--;
			}
		}
		candvots[maxcand]= 0;
		third++;
	}
	cout << maxvotes;


	/*while(cand > 0){
		cout << "\n Candidate No: " << cand << " votes = " << candvots[cand - 1];
		cand --;
	}*/
	system("pause");


}



of course this code still has relics of my old sorting code which I realise has some flaws in it...

Is This A Good Question/Topic? 0
  • +

Replies To: Find the nth largest int in an array

#2 Guest_Neumann*


Reputation:

Re: Find the nth largest int in an array

Posted 22 July 2009 - 01:04 PM

There is a fast way of finding Kth largest element. It is based on the technique used in a QuickSort in which you take an array and one of its elements (call it pivot), then you reorder the array in such a way as to make all the elements that are less than the pivot to be to the left of it, and the elements that are bigger to be to the right. The value that is returned from that function is the new index position of a pivot.

To find Kth largest element you recursively use the above function until it returns the number K. It's has average case of O(n) and worst case of O(n^2).

Edit: I am very busy at the moment, but if I have time I'll write the function.

This post has been edited by Neumann: 22 July 2009 - 01:05 PM

Was This Post Helpful? 1

#4 Guest_Neumann*


Reputation:

Re: Find the nth largest int in an array

Posted 22 July 2009 - 05:11 PM

I'll post this in the code snippet section as well. Here it is:

#include <stdio.h>

//Input:  array with index range [first, last)
//Output: new index of the pivot. An element in the middle is chosen to be a pivot. Then the array's elements are
//placed in such way that all elements <= pivot are to the left and all elements >= pivot are to the right.
int positionPivot(int* array, int first, int last);

//Input:  array with index range [first, last) and integer K (first <= K < last)
//Output: array whose Kth element (i.e. array[K]) has the "correct" position. More precisely,
//array[first ... K - 1] <= array[K] <= array[K + 1 ... last - 1]
void positionKthElement(int* array, int first, int last, int k);

int main() {
  int array[] = {7,1,8,3,1,9,4,8};
  int i;
  for (i = 0; i < 8; i++) {
	positionKthElement(array, 0, sizeof(array) / sizeof(array[0]),i);
	printf("%d is at position %d\n", array[i], i);
  }
  return 0;
}


int positionPivot(int* array, int first, int last) {
  if (first == last)
	return -1;
  else if (first + 1 == last)
	return first;

  int tmp = (first + last) / 2;
  int pivot = array[tmp];
  int movingUp = first + 1;
  int movingDown = last - 1;
  
  array[tmp] = array[first];
  array[first] = pivot;
  
  while (movingUp <= movingDown) {
	while (movingUp <= movingDown && array[movingUp] < pivot)
	  ++movingUp;
	while (pivot < array[movingDown])
	  --movingDown;
	if (movingUp <= movingDown) {
	  tmp = array[movingUp];
	  array[movingUp] = array[movingDown];
	  array[movingDown] = tmp;
	  ++movingUp;
	  --movingDown;
	}
  }
  array[first] = array[movingDown];
  array[movingDown] = pivot;
  return movingDown;
}

void positionKthElement(int* array, int first, int last, int k) {
  int index;
  while ((index = positionPivot(array, first, last)) != k) {
	if (k < index)
	  last = index;
	else
	  first = index + 1;
  }
}



Edit: in the main() I've ran the function inside a loop to see every i-th largest element. If the function is written correctly it should output a sorted array.

This post has been edited by Neumann: 22 July 2009 - 05:54 PM

Was This Post Helpful? 1

#5 skorned  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • Posts: 41
  • Joined: 30-August 08

Re: Find the nth largest int in an array

Posted 28 July 2009 - 11:27 AM

are you sure you got that code right? should the third argument to positionKthElement really be sizeof(array) / sizeof(array[0] ? How does dividing the total length by the length of the first element help? I changed that to read simply sizeof(array), and it worked pretty well...now I've got to change the code to show tags of the numbers instead of the number itself...as in like...the the largest number is the third entry, then the first one...so on...

View PostNeumann, on 22 Jul, 2009 - 04:11 PM, said:

I'll post this in the code snippet section as well. Here it is:

#include <stdio.h>

//Input:  array with index range [first, last)
//Output: new index of the pivot. An element in the middle is chosen to be a pivot. Then the array's elements are
//placed in such way that all elements <= pivot are to the left and all elements >= pivot are to the right.
int positionPivot(int* array, int first, int last);

//Input:  array with index range [first, last) and integer K (first <= K < last)
//Output: array whose Kth element (i.e. array[K]) has the "correct" position. More precisely,
//array[first ... K - 1] <= array[K] <= array[K + 1 ... last - 1]
void positionKthElement(int* array, int first, int last, int k);

int main() {
  int array[] = {7,1,8,3,1,9,4,8};
  int i;
  for (i = 0; i < 8; i++) {
	positionKthElement(array, 0, sizeof(array) / sizeof(array[0]),i);
	printf("%d is at position %d\n", array[i], i);
  }
  return 0;
}


int positionPivot(int* array, int first, int last) {
  if (first == last)
	return -1;
  else if (first + 1 == last)
	return first;

  int tmp = (first + last) / 2;
  int pivot = array[tmp];
  int movingUp = first + 1;
  int movingDown = last - 1;
  
  array[tmp] = array[first];
  array[first] = pivot;
  
  while (movingUp <= movingDown) {
	while (movingUp <= movingDown && array[movingUp] < pivot)
	  ++movingUp;
	while (pivot < array[movingDown])
	  --movingDown;
	if (movingUp <= movingDown) {
	  tmp = array[movingUp];
	  array[movingUp] = array[movingDown];
	  array[movingDown] = tmp;
	  ++movingUp;
	  --movingDown;
	}
  }
  array[first] = array[movingDown];
  array[movingDown] = pivot;
  return movingDown;
}

void positionKthElement(int* array, int first, int last, int k) {
  int index;
  while ((index = positionPivot(array, first, last)) != k) {
	if (k < index)
	  last = index;
	else
	  first = index + 1;
  }
}



Edit: in the main() I've ran the function inside a loop to see every i-th largest element. If the function is written correctly it should output a sorted array.

Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5907
  • View blog
  • Posts: 12,811
  • Joined: 16-October 07

Re: Find the nth largest int in an array

Posted 28 July 2009 - 01:17 PM

View Postskorned, on 28 Jul, 2009 - 12:27 PM, said:

now I've got to change the code to show tags of the numbers instead of the number itself...as in like...the the largest number is the third entry, then the first one...so on...


Doesn't sound like you're actually looking for just the nth largest, then. Also, if more than one value is the same, e.g. "9,8,8,7,6" Is the third largest 8 or 7? 8 is actually the second largest, appearing twice.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1