## 20 Replies - 22235 Views - Last Post: 29 December 2012 - 08:06 PM

### #1

# Finding nth Smallest Number in an Array without using ....

Posted 09 August 2011 - 11:15 PM

I have come across this question below for which I can't get any clue.

Write a program in c++ to find nth smallest number in an array without using another array or sorting. Positions of elements shouldn't be altered.

I am told that the problem prohibits use of pointers and the data structures. So, an answer taking this also into consideration will be useful.

Write a program in c++ to find nth smallest number in an array without using another array or sorting. Positions of elements shouldn't be altered.

I am told that the problem prohibits use of pointers and the data structures. So, an answer taking this also into consideration will be useful.

##
**Replies To:** Finding nth Smallest Number in an Array without using ....

### #2

## Re: Finding nth Smallest Number in an Array without using ....

Posted 10 August 2011 - 03:24 AM

Oho..... Homework...

### #3

## Re: Finding nth Smallest Number in an Array without using ....

Posted 10 August 2011 - 08:11 AM

Why are peope + repping someone that is explicitly asking for a homework solution?

### #4

## Re: Finding nth Smallest Number in an Array without using ....

Posted 10 August 2011 - 06:44 PM

ImaSexy, on 10 August 2011 - 11:11 AM, said:

Why are peope + repping someone that is explicitly asking for a homework solution?

Sorry, I'm new to programming and thought it was an interesting question.

I wrote a terrible solution, so I'm hijacking this thread because I'm curious as to how the more experienced programmers would solve it.

int FindNext(const int *Array, const size_t &Size, const int &StopAt) { for (register size_t x = 0; x<Size; ++x) { if (Array[x] > StopAt) { return Array[x]; } } return StopAt; } int StupidSolution(const int *Array, const size_t &Size, const size_t &NthSmallest) { int Smallest = Array[0]; int Buffer; for (register size_t x = 0; x<NthSmallest; ++x) { Buffer = Smallest; Smallest = FindNext(Array, Size, Buffer); for (register size_t y = 0; y<Size;++y) { if (Array[y] > Buffer && Array[y] < Smallest) { Smallest = Array[y]; } } } return Smallest; }

Terrible! I know! But I tested it and it seemed to work pretty well. So how would you solve it? I took an approach that's sort of like bubble sort except without actually sorting it. I actually struggled during the beginning, but after using a nested for loop it made more sense.

Anyway, to reiterate, I'm

**not**the original poster, just a curious programmer.

Edit; also my variables are named terribly. I was editing the original code a lot while trying to fix it, so some of the names are holdovers. I'll name them something better if you wish.

This post has been edited by **TokoYami200**: 10 August 2011 - 06:46 PM

### #5

## Re: Finding nth Smallest Number in an Array without using ....

Posted 21 August 2011 - 12:29 AM

Thanks to Prabh for reminding that homeworks are not to be raised here. (though, it was not my homework).

### #6

## Re: Finding nth Smallest Number in an Array without using ....

Posted 21 August 2011 - 12:44 AM

Thanks to Toko Yami 200 for the reply. Sorry for the delay to respond. The given code doesn't return nth smallest.

However, I could slove it with the idea that the number of elements in an array lower than nth lowest will be n-1.

However, I could slove it with the idea that the number of elements in an array lower than nth lowest will be n-1.

### #7

## Re: Finding nth Smallest Number in an Array without using ....

Posted 21 August 2011 - 12:47 AM

If i didn't misunderstand the question, the answer is quite simple..

1.) Assumption must be that the first element in the array is the largest element.

2.) Iterate the loop starting in the second element, if the current element is bigger than the (current)largest element, then the largest element must be set to be the largest element..

========================================

oh, i've understand youre problem now..

so you mean that find the nth largest number..

i guess i should edit my example..

1.) Assumption must be that the first element in the array is the largest element.

2.) Iterate the loop starting in the second element, if the current element is bigger than the (current)largest element, then the largest element must be set to be the largest element..

#define SIZE 10 int findLargest(int *array) { int largest = array[0]; for(int x = 1; x < SIZE; x++) { if(largest < array[x]) largest = array[x]; } return largest; } void main() { int array[] = {10, 5, 2, 6, 7, 1, 3, 6, 8, 1}; printf("Largest in array is %d", findLargest(array)); }

========================================

oh, i've understand youre problem now..

so you mean that find the nth largest number..

i guess i should edit my example..

### #8

## Re: Finding nth Smallest Number in an Array without using ....

Posted 21 August 2011 - 01:03 PM

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.

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; }

### #9

## Re: Finding nth Smallest Number in an Array without using ....

Posted 21 August 2011 - 10:46 PM

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.

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; }

Great!!! The solution given by baavgai works well. Thanks. (efficiency is not important in this case).

It is interesting that the numbers are chosen randomly.

### #10

## Re: Finding nth Smallest Number in an Array without using ....

Posted 22 August 2011 - 04:31 AM

Numbers aren't chosen randomly... rather, tests are generated randomly. If you write your own test, e.g. {1,2,3,4,5,6,7}, you mightn't really hit all possible issues. Random is just a lazy way to check the validity of the function.

The function findNSmallest is the only code needed. The rest of the code is testing to make sure it's right. I wouldn't have offered a complete solution if I thought this homework was still in play. However, I also thought the number of misleading answers might confuse future readers.

Please make sure you understand the function. It's really very simple. Basically, you choose the smallest first. This is easy, you loop through the entire array and keep comparing, keeping the smallest value. For the Nth smallest, you go through the exact same logic, but with the extra criteria that the value must be greater than the current smallest, while still being smaller than all the values that meet the criteria.

Consider the third smallest of this list: 4,3,2,1,2,3,4,1

First pass:

Second pass:

Third pass:

Hope this helps.

The function findNSmallest is the only code needed. The rest of the code is testing to make sure it's right. I wouldn't have offered a complete solution if I thought this homework was still in play. However, I also thought the number of misleading answers might confuse future readers.

Please make sure you understand the function. It's really very simple. Basically, you choose the smallest first. This is easy, you loop through the entire array and keep comparing, keeping the smallest value. For the Nth smallest, you go through the exact same logic, but with the extra criteria that the value must be greater than the current smallest, while still being smaller than all the values that meet the criteria.

Consider the third smallest of this list: 4,3,2,1,2,3,4,1

First pass:

4 smallest = 4 3 is < 4, smallest = 3 2 is < 3, smallest = 2 1 is < 2, smallest = 1 2 is not < 1, skip 3 is not < 1, skip 4 is not < 1, skip 1 is not < 1, skip smallest = 1

Second pass:

smallest = 1 4 is > 1, next smallest = 4 3 is > 1, is < 4, next smallest = 3 2 is > 1, is < 3, next smallest = 2 1 is not > 1, skip 2 is > 1, not < 2, skip 3 is > 1, not < 2, skip 4 is > 1, not < 2, skip 1 is not > 1, skip next smallest = 2

Third pass:

smallest = 2 4 is > 2, next smallest = 4 3 is > 2, is < 4, next smallest = 3 2 is not > 2, skip 1 is not > 2, skip 2 is not > 2, skip 3 is > 2, not < 3, skip 4 is > 2, not < 3, skip 1 is not > 2, skip next smallest = 3

Hope this helps.

### #11

## Re: Finding nth Smallest Number in an Array without using ....

Posted 22 August 2011 - 07:15 AM

### #12

## Re: Finding nth Smallest Number in an Array without using ....

Posted 23 August 2011 - 10:38 PM

baavgai, on 22 August 2011 - 04:31 AM, said:

Numbers aren't chosen randomly... rather, tests are generated randomly. If you write your own test, e.g. {1,2,3,4,5,6,7}, you mightn't really hit all possible issues. Random is just a lazy way to check the validity of the function.

The function findNSmallest is the only code needed. The rest of the code is testing to make sure it's right. I wouldn't have offered a complete solution if I thought this homework was still in play. However, I also thought the number of misleading answers might confuse future readers.

Please make sure you understand the function. It's really very simple. Basically, you choose the smallest first. This is easy, you loop through the entire array and keep comparing, keeping the smallest value. For the Nth smallest, you go through the exact same logic, but with the extra criteria that the value must be greater than the current smallest, while still being smaller than all the values that meet the criteria.

Consider the third smallest of this list: 4,3,2,1,2,3,4,1

First pass:

Second pass:

Third pass:

Hope this helps.

The function findNSmallest is the only code needed. The rest of the code is testing to make sure it's right. I wouldn't have offered a complete solution if I thought this homework was still in play. However, I also thought the number of misleading answers might confuse future readers.

Please make sure you understand the function. It's really very simple. Basically, you choose the smallest first. This is easy, you loop through the entire array and keep comparing, keeping the smallest value. For the Nth smallest, you go through the exact same logic, but with the extra criteria that the value must be greater than the current smallest, while still being smaller than all the values that meet the criteria.

Consider the third smallest of this list: 4,3,2,1,2,3,4,1

First pass:

4 smallest = 4 3 is < 4, smallest = 3 2 is < 3, smallest = 2 1 is < 2, smallest = 1 2 is not < 1, skip 3 is not < 1, skip 4 is not < 1, skip 1 is not < 1, skip smallest = 1

Second pass:

smallest = 1 4 is > 1, next smallest = 4 3 is > 1, is < 4, next smallest = 3 2 is > 1, is < 3, next smallest = 2 1 is not > 1, skip 2 is > 1, not < 2, skip 3 is > 1, not < 2, skip 4 is > 1, not < 2, skip 1 is not > 1, skip next smallest = 2

Third pass:

smallest = 2 4 is > 2, next smallest = 4 3 is > 2, is < 4, next smallest = 3 2 is not > 2, skip 1 is not > 2, skip 2 is not > 2, skip 3 is > 2, not < 3, skip 4 is > 2, not < 3, skip 1 is not > 2, skip next smallest = 3

Hope this helps.

Thanks to baavgai, very well explained.

### #13

## Re: Finding nth Smallest Number in an Array without using ....

Posted 30 August 2011 - 11:48 PM

You can use <algorithm> which is apart of the standard C++ library

int main () { int myints[] = {3,7,2,5,6,4,9}; // using default comparison: cout << "The smallest element is " << *min_element(myints,myints+7) << endl; cout << "The largest element is " << *max_element(myints,myints+7) << endl;

### #14

## Re: Finding nth Smallest Number in an Array without using ....

Posted 31 August 2011 - 04:19 AM

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

No, you should not use algorithm to solve this. That you've even been asked to solve this means you're being challenged to think, no use black boxes.

It should also be noted that the functions given do not solve any element of the problem.

No, you should not use algorithm to solve this. That you've even been asked to solve this means you're being challenged to think, no use black boxes.

It should also be noted that the functions given do not solve any element of the problem.

### #15

## Re: Finding nth Smallest Number in an Array without using ....

Posted 31 August 2011 - 08:07 AM

Well the real problem is that we are looking for the Nth smallest not "the smallest".