[jjl]

Quote

And this teaches the programmer what? That there is a canned function for damn near everything?

yes

[Wuzseen]

I really liked this problem, so I set to work to a find a bit "easier" solution. Here's the code--I'll explain it below.

	const int x = 10;
	int arr[x] = {5, 22, 4, 63, 112, 49, 27, 32, 9, 87};
	// 4th lowest is 22
	int nth = 4;
	int curLow = 0;
	int z = 0;
	for(int i = 0; i < x; i++)
	{
		curLow = 0;
		for(z = 0; z < x; z++)
		{
			if(arr[z] < arr[i])
			{
				curLow++;
			}
		}
		if(curLow == nth-1)
		{
			cout << arr[i] << endl; //This is your solution
                        //break;
		}
	}

I'm sure there's a more elegant solution, but this worked pretty darn well. The way I saw it was take each element of the array and compare it against every other element in the way. If you're looking for the X smallest number in the array, then there are X-1 numbers smaller than it. I made a variable, curLow, that increments for just that purpose. For each position in the array it checks the entire array and increments curLow if the check number is less than the current position.

To save time break is in that last conditional, however I've commented it out. Through sheer coincidence I could have found the answer if break was there. For example, what if there was something later in the array that confounds the app? If you try this code, break simply saves time and resources--but it doesn't really check the "whole" problem.

Also, that array in there was one of my test ones, you can swap it and its size value out with anything you want. Just don't try and find the nth+1 smallest variable in an array of size n.

This post has been edited by Wuzseen: 07 October 2011 - 07:31 AM

[erdilelif]

baavgai, on 21 August 2011 - 01:03 PM, said:

In the absence of proper sorting or even a scratch array, you're basically forced to do it the most inefficient way possible. However, it's also a very simple way, so perhaps that's the point.

Here's a complete solution, consider the age of this thread.

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int findNSmallest(const int *a, const int size, const int n) {
	// find the first smallest
	int smallest = a[0];
	for(int i=1; i<size; i++) { if (a[i]<smallest) { smallest = a[i]; } }
	
	for(int i=0; i<n-1; i++) {
		// find the next smallest
		int found = -1;
		for(int i=0; i<size; i++) {
			if (a[i]>smallest && (found==-1 || a[i]<a[found])) { found = i; }
		}
		if (found==-1) { cout << endl << "invalid request" << endl; break; }
		smallest = a[found];
	}
	return smallest;
}



// because I'm lazy
void test(const int size, const int min, const int max, const int n) {
	cout << "size=" << size << " n=" << n << " range=" << "(" << min <<"-"<<max<<")"<<endl;
	
	int range = (max - min) + 1;
	int *data = new int[size];
	
	for(int i=0; i<size; i++) { data[i] = (rand() % range) + min; }
	for(int i=0; i<size; i++) { cout << data[i] << ' '; }
	cout << endl << n << "th smallest = " << findNSmallest(data, size, n) << endl << endl;
	
	delete [] data;
}

int main() {
	srand ( time(NULL) );
	test(20, 1, 100, 3);
	test(20, 1, 100, 7);
	// this will often fail because of lack of result domain
	test(10, 1, 10, 6);
	test(10, 1, 10, 6);
	return 0;
}

Can you explain what is "found" and why is its value "-1"? I couldnt understand because i am not good at writing program for now.

[blackcompe]

Kth-order statistic is the most efficient algorithm (linear) for finding the Nth smallest number in a list. It's a spin-off of quicksort and fairly simple to implement.

[mojo666]

The topic is kind of necroed, but to answer erdilelif's question, found represents the location of the ith smallest element of the array. -1 is being used to represent that such a value has not been found. Since i loops n times, by the time the algorithm finishes found will contain the location of the nth smallest number. Thus, a[found] will be the nth smallest number.

[jjl]

If you are not worried about sustaining the integrity of the data, then you can simply just loop over the data n times, with each time doing a "find minimum" search. After every "find minimum" search, save the smallest value and then set the value at that index to the maximum possible value.

i.e.

#include <iostream>
#include <algorithm>
#include <limits>

int findNthSmallest(int *arr, int size, int nth) { 
   int index = 0;
   
   while(nth--) {
      index = std::distance(arr, std::min_element(arr, arr + size));
      if (nth) arr[index] = std::numeric_limits<int>::max();
   }
   return arr[index];
}