Finding Second Smallest Element In an Unsorted Array

[candy man]

How should I go about finding the 2nd, or 3rd smallest element in an array?
Where the minimum is not equals to the next minimum.

Here is the psuedocode I've found

void Min(A[i..j], int&min, int &next_min)

if (i=j) then min=A[i] and next_min = infinity

else
mid = (i+j)/2

Min(A[i to mid]),a,b)
Min(A[mid+1 to j],c,d)

Let min be minimum among a,b,c,d
Let next_min be the next_min among a,b,c,d

min != next_min

Here is what I wrote but it does not seem to work. Can anyone point me to the right direction? Thanks

#include<iostream>
#include<vector>
#include <cstdlib>

using namespace std;


void minfind(vector<int> &array,int left,int right, int &min, int &next_min);

int main(){
	cout << "Enter integers one line at a time. (Enter -999 to terminate)" << endl;

    vector<int> array;  // you can also use an array to do this, e.g., int A[21];
	int input;

    //let user enter till termination condition
	while(true){
        cin >> input;
		if(input == -999) //check for termination condition
			break;
        array.push_back(input);
    }

int imin = 0;
int imax = array.size();
int q;
int r;

minfind(array, imin, imax, q, r);

   
    
    cout<<"Min number is " << r <<endl;

    cin.get();
    system("pause");
    return 0;
}


void minfind(vector<int> &array,int left,int right, int &min, int &next_min)
{
    int a;
    int b;
    int c;
    int d;
    
	if(left == right){ 
    min = array[left];
    
    next_min = 2147483647;
    
    }
    else {
        
         int mid= (right+left)/2;
                  
        minfind(array,left,mid,a,b);
        minfind(array,mid+1,right,c,d);
         
         
         if (a<b){ 
         min = a;
            if (b<c && b<d)
            next_min = b;
        }
        
        else if (b<a){
        min = b;
            if (a<c&& a<d)
            next_min = a;
        }
         
        if (c<d){ 
         min = c;
            if (d<a && d<b)
            next_min = d;
        }
        
        else if (d<c){
        min = d;
            if (c<a && c<b)
            next_min = c;
        } 
         
        
        
    }
}

[Bourgond Aries]

Maybe you're thinking too complicated. Element 2 should be smaller than element 1 yet the highest in its rank. This implies that 3 is smaller than 2, and thus you can use the same loop just with different integers. Check the 4th block of code (containing 2 for loops).

#include <vector>
#include <iostream>


int main()
{
    enum {SIZE = 16, NUMS = 100, LIM = 100};

    int highest[SIZE] {0};
    std::vector<int> v;
    for (int i = 0; i < NUMS; ++i)
        v.emplace_back(std::rand() % LIM);

    for (auto &x : v)
        if (x > highest[0])
            highest[0] = x;

    for (int i = 0; i < SIZE; ++i)
        for (auto &x : v)
            if (x > highest[i + 1] && x < highest[i])
                highest[i + 1] = x;

    for (auto &x : v)
        std::cout << x << std::endl;

    for (int i = 0; i < SIZE; ++i)
        std::cout << i << ": " << highest[i] << std::endl;

    return 0;
}

[keskiverto]

http://cplusplus.com/reference/algorithm/nth_element/
Would that help?

[topnik1]

y cant u just use SORT?
with algortihm

[Bourgond Aries]

@topnik1

Using sort means that equivalent elements come after each other. So vector[0] may contain 99, and so does vector[1] or even vector[2] because you may have the number 99, 3 times in the vector/array.

[keskiverto]

That is a case that would render nth_element useless too.

If one knows the N-1th smallest value X, then one can write the usual find min element with a twist: call all the <=X values "too big" in the test.

There is always the std::map. Filling it is an implisit sort, and it can hide the repeated values in its value_type.