@Dave: simple, you have to find the first k elements , if you can find the* kth last element *also then we are done
eg : let you have array [1,6,3,8,9,23,15] in this you have to find the first k=3 elements if we can find 3rd element then from that we can know what the rest 1st & 2nd can be from selection algorithm we can get 3rd element is *6 *we can traverse again in array & find all the element less than 6 which are 1 & 3 so first k element are 6 , 1 & 3 *note *: selection algorithm does not load whole array at a time it divide into parts & loads so whether our array is million or billion we don't have to worry about memory here , it break it into parts & checks hope my explanation easy please let me know if you have any question.. On Sat, Mar 26, 2011 at 7:42 PM, Dave <dave_and_da...@juno.com> wrote: > @Patidarachat: Please explain how to use the selection algorithm in > the presence of the restriction that you can't hold all of the data in > memory at once. > > Dave > > On Mar 22, 3:55 am, "patidarc...@gmail.com" <patidarc...@gmail.com> > wrote: > > please check this also > > Selection_algorithm <http://en.wikipedia.org/wiki/Selection_algorithm> > > > > On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar <rajeevprasa...@gmail.com > >wrote: > > > > > > > > > > > > > > > > >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of. > .. > > > > > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma < > natansh.ve...@gmail.com>wrote: > > > > >> @dave -was this a constraint since the beginning? In case it was, I am > > >> sorry I didn't notice. > > > > >> In that case, the heap method ought to work better. I dont think the > > >> quicksort method will work. > > > > >> Sent from my iPhone > > > > >> On 20-Mar-2011, at 23:00, Dave <dave_and_da...@juno.com> wrote: > > > > >> > @Natansh: How do you do this with the constraint that your RAM is so > > >> > small that you cannot accomodate all of the numbers at once? > > > > >> > Dave > > > > >> > On Mar 20, 9:04 am, Natansh Verma <natansh.ve...@gmail.com> wrote: > > >> >> There's another way... use the partitioning method for quicksort to > > >> find the > > >> >> k smallest elements. Then it should take expected time as O(n + > klogk). > > >> >> Plus, it is in-place. > > > > >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit <lipu...@gmail.com> wrote: > > >> >>> I agree with munna > > > > >> >>> -- > > >> >>> You received this message because you are subscribed to the Google > > >> Groups > > >> >>> "Algorithm Geeks" group. > > >> >>> To post to this group, send email to algogeeks@googlegroups.com. > > >> >>> To unsubscribe from this group, send email to > > >> >>> algogeeks+unsubscr...@googlegroups.com. > > >> >>> For more options, visit this group at > > >> >>>http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > >> >> - Show quoted text - > > > > >> > -- > > >> > You received this message because you are subscribed to the Google > > >> Groups "Algorithm Geeks" group. > > >> > To post to this group, send email to algogeeks@googlegroups.com. > > >> > To unsubscribe from this group, send email to > > >> algogeeks+unsubscr...@googlegroups.com. > > >> > For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to algogeeks@googlegroups.com. > > >> To unsubscribe from this group, send email to > > >> algogeeks+unsubscr...@googlegroups.com. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > Thank You > > > Rajeev Kumar > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > Thanks > > Rajesh Patidar~- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- --Thanks-- **<Bl**@©k D!@Mond>** -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
