1 Replies - 1828 Views - Last Post: 10 December 2012 - 06:08 PM Rate Topic: -----

#1 iamminn  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 10-December 12

Selection sort find "kth" smallest element

Posted 10 December 2012 - 05:08 PM

I have been asked to create a function based on selection sort to find the kth smallest element in an arbitrary array of integers.

I used the standard selection sort which sorts the array and then uses input to output what integer they are requesting to find.

It works correctly, I just feel as though it is a very "lame" inefficient program. I know there is a way to cut a few corners and find the answer prior to the sort, but i cannot figure it out.

I was also asked to state why selection sort is a better method then insertion sort for this task?


Here is my code:
 int main()
{
const int nSize = 5;
int A[nSize] = { 30, 5, 200, 151, 40 };


for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
{
   
    int nSmallestIndex = nStartIndex;
 
    for (int nCurrentIndex = nStartIndex + 1; nCurrentIndex < nSize; nCurrentIndex++)
    {
  
        if (A[nCurrentIndex] < A[nSmallestIndex])
      
            nSmallestIndex = nCurrentIndex;
    }
 
  
    swap(A[nStartIndex], A[nSmallestIndex]);
	

}
int j;
cout<<"Enter the kth smallest number you want:"<<endl;
cin>>j;
cout<<endl<<A[j-1]<<" is the "<<j<<" smallest element ";
}


Is This A Good Question/Topic? 0
  • +

Replies To: Selection sort find "kth" smallest element

#2 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: Selection sort find "kth" smallest element

Posted 10 December 2012 - 06:08 PM

Selection sort has been given a boost from the newer hardware on PC's. Used to be just a DOG of a sorter, but I just tested it last week (only because I was challenged to do it), and it did comparable with insertion sort - beating it handily on some inputs even - except for data that is either already sorted, or almost already sorted - or needs a stable sort (where the index of equal values remains in the same relative order).

Anyway, Selection sort is great for this, because you always scan the array to find the next value to put into it's proper place, and you're right, you don't have to sort the entire array to do this. There are some "slick" ways to do this faster, but they're complicated, and not in the spirit of Selection sort, so I'll stick with this way:

(Whew! Got out of that one!) ;)

You could do a Selection sort UP TO the kth value being found and put into it's place. Then stop - you're finished.
Then you could optimize it - say the SIZE of the array is 100. You're asked to find the 90th to the smallest value. Instead of starting at the minimum value and working upward to it, you could start at the maximum value and work down to it.

Using this logic, you have to start at the "ends", either max or min, and work toward the kth value. You can't start with the 50th value, because you don't know what that value would be.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1