getting two lowest values in array by index

This is a discussion on getting two lowest values in array by index within the C++ Programming forums, part of the General Programming Boards category; Hello, This is my first post. I'm glad to meet you all. I want to write an alg that returns ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    8

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

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    1,208
    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.

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    8
    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++

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    1,208
    it would work with an array but you would have to pass the size of the array to the function. I am not sure if it would be faster since i dont know how it sorts but the sort method most certanly traverse the whole vector aswell.

    I am not sure how that would help you, unless order doesnt matter, becaus you would change the order of the elements when you sort the vector.
    Last edited by Shakti; 03-05-2005 at 12:57 PM.

  5. #5
    Registered User
    Join Date
    Mar 2005
    Posts
    8
    So are you saying that upon sorting the vector, C++ traverses the entire list anyway?

    DanielC++

  6. #6
    Registered User
    Join Date
    Aug 2003
    Posts
    1,208
    I am not 100% sure since I am not very familiar with sorting algorithms but I would guess that it does.

  7. #7
    Registered User
    Join Date
    Mar 2005
    Posts
    8
    The answer is these sorting animations.

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

    Daniel

  8. #8
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    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]

  9. #9
    Registered User
    Join Date
    Mar 2005
    Posts
    8
    Quote 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 04-12-2009, 05:49 PM
  2. 20q game problems
    By Nexus-ZERO in forum C Programming
    Replies: 24
    Last Post: 12-17-2008, 04:48 PM
  3. Eliminating duplicate values from a 20x2 array
    By desipunjabi in forum C Programming
    Replies: 2
    Last Post: 10-29-2005, 09:11 PM
  4. accessing array of structs values
    By WaterNut in forum C++ Programming
    Replies: 12
    Last Post: 07-08-2004, 08:47 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21