Quote

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

yes

Posted 07 October 2011 - 07:26 AM

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.

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.

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

Posted 28 December 2012 - 12:42 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; }

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.

Posted 28 December 2012 - 01:30 PM

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.

Posted 28 December 2012 - 01:34 PM

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.

Posted 29 December 2012 - 08:06 PM

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.

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

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- ASP.NET
- .NET Framework
- VB6
- PHP
- Ruby
- Python
- ColdFusion
- Databases
- Other Languages
- Game Development
- Mobile Development
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- Network programming under UNIX
- Implementation Inheritance
- Change Theme in Code::Blocks
- A New Webcam Api Tutorial in C++ for Windows
- External Sorting with C
- C++ Windows Charting Library Part 6
- Bezier Curves Part 1 [Linear Algebra Series]
- STL Algorithms ~ Tutorial 1: Using sort()
- C++ Windows Charting Library Part 5
- C++ Windows Charting Library Part 4
**342 More C++ Tutorials...**

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2015 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3