Solved

Algorithm right?

Posted on 2003-12-06
18
461 Views
Last Modified: 2010-04-02
I need to write for the program that computes A th smallest number in a set of K distinct integer.  But there's an restriction that the running time has to be
O(K+Alog(K)).  This is my way of thinking.  I think I will need to sort the data first.  And I'm think to use basket sorting. Then find the number I want.  I just want to know if it is right?  Or I should use heap sort?  I'll appreciate any idea.  I'm not asking for the actual code, I just need the algorithm so that I can start coding.
Thanks,
0
Comment
Question by:templeavenue
  • 7
  • 3
  • 2
  • +2
18 Comments
 
LVL 11

Expert Comment

by:bcladd
ID: 9888574
Problem with sorting first:

Sorting is O(K log(K))

so you have blown your constraints out of the gate.

The important insight here is that you don't care about the elements in positions [0,A-2] and [A,(K-1)]. If you could "simulate" sorting just position A-1 you would be happy. Think about the sorting algorithms you know and try to imagine running one of them WITHOUT finishing the sort that could put just the Ath element in the right place (or rather some number of elements in the right place, the number dependent on A).

Note: It does NOT have to be the elements [0, A-2].

-bcl
0
 
LVL 15

Expert Comment

by:efn
ID: 9888575
To find the smallest number in a set of integers, you have to look at each integer, and you don't have to look at each integer more than once.  So the cost should be O(K).  If A is the value of the smallest number, it shouldn't enter into the complexity calculation as in Alog(K).  The value of the number doesn't affect how long the search takes.

Are you sure you have stated the problem correctly?  Did I misunderstand something?

--efn
0
 
LVL 15

Expert Comment

by:efn
ID: 9888584
Oh, from bcladd's comment, I see that you probably meant the Ath smallest number.  I read it as a typo for "A the smallest number."  Sorry!

--efn
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9888587
efn-

I think the problem is to find the A'th smallest or the number that would be in position A-1 if the set were sorted and put into a C++ vector.

0
 

Expert Comment

by:ks5d
ID: 9888643
Hi.

     There are many, many pages of information about sorting algorithms on the web.  I am studying for a C++ exam, and have been looking at a lot of these sites for answers to questions like the one you are asking here.  I really liked the explanations by the author of these pages here:

http://linux.wku.edu/~lamonml/algor/sort/heap.html

   You are correct that heap sort is O(k + log(K)) for a data set of size K.  Once the data is sorted, you can just grab the Ath item, assuming you are using a container that supports random access, like an array or a vector.

    I think, but I'm not sure, the basket sort you are mentioning is more commonly called 'bucket sort', and it takes O(N + K) time where N is the number of buckets and K is the number of items.  If the number of buckets is chosen wisely, then the running time can be almost linear O(K).  A short article on Bucket sort can be found here:

http://www.ics.uci.edu/~eppstein/161/960123.html

    In summary, both bucket sort and heap sort will accomplish your goals in your bounds of O(K + Alog(K)) or better.

I hope this helps,

      - Ken
0
 

Expert Comment

by:ks5d
ID: 9888733
OOPS!

    Heapsort runs in O(K log(K)), NOT O(K + log(K))!  That plus makes a big difference.  That difference will constrain you to using basket sort.  Sorry for the typo.

      - Ken
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9889020
It is possible to sort the integers using a radix sort BUT that only works for this limited set of input. The problem is acually solvable for any sortable type within the given constraints using only key comparisons. Think about all of the sorting algorithms and see what you can come up with.

-bcl
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 49

Expert Comment

by:DanRollins
ID: 9891408
I don't think you need to sort the whole list.
Just make an array of length A and cycle through the length-K list once, inserting into the A array whenever you find a new item that is less than the highest item that is in the A array.

I haven't a clue how to typify that as
     Whatzat log W00t,
but that's how I'd do it.

-- Dan
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9892173
DanRollins-

Ordered insert into the A array: O(A) (might have to move the entire content) and it might happen on each item in the K list (reverse sorted order) so O(KA) which blows the assigned execution budget. Your solution is also O(A) in space complexity which is non-optimal (it can be done in the required time with constant (O(1)) additional space).

-bcl
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 9895244
Again, I don't know how to express in those terms, but at most, you would need to insert A items and they would not need to be in any particular order.  Once you have A items in the list, you can compare the next item from K to the current max and min in A.  If it is less than the min, replace the max with that min and find the new max.

I feel stupoid.  Where can I learn what Alog(K) means in this context?

-- Dan
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9895926
And finding the new max requires scanning the whole list if it is unordered. Still O(A) to insert a new item. When I reread my post I KNEW someone would suggest an unordered array and a single comparison. For a minute I was sure that fixed the problem...but then I remembered that finding the largest remaining element in that array is still a linear scan (if the list is unordered).

It is quite possible that your constants are better than if the A array were kept sorted with an insertion sort but I am not even sure that is the case.

Wonder if templeavenue is even reading this anymore.

The trick is to ALMOST sort original array. One well known sort algorithm starts with an ALMOST sort and then recurs to finish the job. For this problem you can use the same start (almost sort the array) but THEN you only need to work on part of the almost sorted space (where in the sort you have to work on all of the space).

-bcl
0
 

Author Comment

by:templeavenue
ID: 9898654
Sorry for coming back lately. I don't have an access to internet on Sunday.  
To "bcl" - Should I sort the array completely first? If so, using what method?  or should I look for the Kth element as while I sort the array?  I'm not quite sure what are you trying to say.  Pls explain me more if you can.

Thanks everyone!
0
 
LVL 11

Accepted Solution

by:
bcladd earned 125 total points
ID: 9898917
No, no, no: Remember that the lower bound on any sorting method that uses only key-to-key comparison is O(K lg K). You do NOT want to sort.  You want to do something like sort.

If you were to sort it you would probably use quicksort, right? It is a fast sort and if you have unique values and use a median of 5 (or median of 3) to select your pivot you will get optimal performance. The question is, in your problem, why do you have to sort both to the left of the pivot _and_ to the right of the pivot? You know the A'th element is only in one of those two subsets.

That is as far as I can go in spelling it out; any further and I am writing the algorithm for you. Look at quicksort and think about what you DON'T have to do for your solution.

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9920130
templeavenue-

How goes the programming? Any questions?

-bcl
0
 
LVL 15

Expert Comment

by:efn
ID: 11138410
Answered by bcladd.
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now