Thread: getting two lowest values in array by index

Hello, This is my first post. I'm glad to meet you all.

I want to write an alg that returns the index numbers of the two lowest values in an array. The array will contain thousands of elements.

I hope to use this as a way to learn more about STL containers.
Does anyone have any suggestions?

DanielC++

Since you mention STL I take that as you meant vectors.

Write a function taking a vector and 2 pointers to integers as arguments.
Loop through the vector and keep track of the lowest and the second lowest values and their indeces.

Thank you for your response. You are correct. I meant vectors.

Your suggestion would work just as well with arrays, correct? Would the STL's sorting capabilities provide a faster way of getting the 2 lowest values and their indeces without having to traverse the entire list? It is a HUGE array.

DanielC++

So are you saying that upon sorting the vector, C++ traverses the entire list anyway?

DanielC++

I am not 100% sure since I am not very familiar with sorting algorithms but I would guess that it does.

The answer is these sorting animations.

http://www.cs.ubc.ca/spider/harrison...ting-demo.html

Daniel

If you look through the STL index you will often find something you can use. In this case you could use partial_sort_copy, although I suspect it may be slower than the manual method.

Code:

#include <iostream>
#include <algorithm>
using namespace std;

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))

int main(void)
{
	int numbers[] = { 27, 1, 100, 53, 12 };
	int smallest[2];

	partial_sort_copy(numbers, numbers + ARRAY_SIZE(numbers),     // Source range.
                          smallest, smallest + ARRAY_SIZE(smallest)); // Destination range.

	copy(smallest, smallest + ARRAY_SIZE(smallest), ostream_iterator<int>(cout, " "));

	cin.get();
}

[edit]I reread your post and it seems you are looking for index positions rather than values so this won't do. It looks like it's back to doing this trivial task manually, possibly with the help of for_each.[/edit]

Originally Posted by anonytmouse

[edit]I reread your post and it seems you are looking for index positions rather than values so this won't do. It looks like it's back to doing this trivial task manually, possibly with the help of for_each.[/edit]

Thank you, anonytmouse.
for_each will do nicely in my manual method.

Daniel