20 Replies  13913 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
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
#3
Re: Finding nth Smallest Number in an Array without using ....
Posted 10 August 2011  08:11 AM
#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:
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
#6
Re: Finding nth Smallest Number in an Array without using ....
Posted 21 August 2011  12:44 AM
However, I could slove it with the idea that the number of elements in an array lower than nth lowest will be n1.
#7
Re: Finding nth Smallest Number in an Array without using ....
Posted 21 August 2011  12:47 AM
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
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<n1; 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:
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<n1; 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
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:
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
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
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
