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

  • (2 Pages)
  • +
  • 1
  • 2

20 Replies - 12506 Views - Last Post: 29 December 2012 - 08:06 PM Rate Topic: -----

#1 abdulrasheed  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 13
  • Joined: 28-November 10

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.
Is This A Good Question/Topic? 4
  • +

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

#2 prabh  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 3
  • View blog
  • Posts: 381
  • Joined: 27-December 08

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

Posted 10 August 2011 - 03:24 AM

Oho..... Homework...
Was This Post Helpful? -2
  • +
  • -

#3 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1074
  • View blog
  • Posts: 4,533
  • Joined: 09-June 09

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?
Was This Post Helpful? 2
  • +
  • -

#4 TokoYami200  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • Posts: 44
  • Joined: 18-October 10

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

Posted 10 August 2011 - 06:44 PM

View PostImaSexy, 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. :P

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

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

Was This Post Helpful? 0
  • +
  • -

#5 abdulrasheed  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 13
  • Joined: 28-November 10

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).
Was This Post Helpful? 0
  • +
  • -

#6 abdulrasheed  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 13
  • Joined: 28-November 10

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.
Was This Post Helpful? 0
  • +
  • -

#7 CreamDelight  Icon User is offline

  • D.I.C Head

Reputation: 18
  • View blog
  • Posts: 90
  • Joined: 04-July 11

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

#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..
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • Joined: 16-October 07

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


Was This Post Helpful? 1
  • +
  • -

#9 abdulrasheed  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 13
  • Joined: 28-November 10

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

Posted 21 August 2011 - 10:46 PM

View Postbaavgai, 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;
}



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.
Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • Joined: 16-October 07

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:
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.
Was This Post Helpful? 2
  • +
  • -

#11 hulla  Icon User is offline

  • Writing Lines


Reputation: 49
  • View blog
  • Posts: 732
  • Joined: 05-March 11

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

Posted 22 August 2011 - 07:15 AM

View PostCreamDelight, on 21 August 2011 - 03:47 PM, said:

void main()
{
   int array[] = {10, 5, 2, 6, 7, 1, 3, 6, 8, 1};
   printf("Largest in array is %d", findLargest(array));
}


You're main function is void. It should have a return type of int, right?
Was This Post Helpful? 2
  • +
  • -

#12 abdulrasheed  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 13
  • Joined: 28-November 10

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

Posted 23 August 2011 - 10:38 PM

View Postbaavgai, 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:
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.
Was This Post Helpful? 0
  • +
  • -

#13 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1074
  • View blog
  • Posts: 4,533
  • Joined: 09-June 09

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;


Was This Post Helpful? 1
  • +
  • -

#14 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • Joined: 16-October 07

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.
Was This Post Helpful? 1
  • +
  • -

#15 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

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".
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2