[skorned]

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...

[skorned]

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...

Neumann, 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.

[baavgai]

skorned, 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.