algorithm - Adapting quickselect for smallest k elements in an array -


i know can kth order statistic (i.e. kth smallest number in array) using quickselect in linear time, if needed k smallest elements of array?

the wikipedia link has pseudocode single-element lookup, not k smallest elements lookup.

how should quickselect modified attain in linear time (if possible) ?

actually modifying quickselect not needed. if had array (called arraytosearch in example) , wanted k smallest items i'd this:

int i; int k = 10;  // if wanted 10 smallest elements  int smallestitems = new array(k); (i = 0; < k; i++) {     smallestitems[i] = quickselect(i, arraytosearch); }

edit: under assumption k relatively small number make effective big-o o(n). if not assuming k small have speed of o(k*n), not linear time. answer easier comprehend, , applicable practical purposes. recursion.ninja's answer may more technically correct, , therefore better academic purposes.


Comments

Post a Comment

Popular posts from this blog

android - Pass an Serializable object in AIDL -

i have defined aidl file interface imyfeature { void dotask(class clazz); } but need pass class object process. possible in android? if so, how? i tried: interface imyfeature { serializable class; void dotask(class clazz); } but doesn’t work. aidl in android supports custom class implement parcelable interface. in case want send class object not possible. can send class canonical name , retrieve in service. for example have aidl file interface imyfeature { void dotask(string classname); } then call : binder.dotask(myclass.class.getcanonicalname()); and in service binder stub implementation : private final imyfeature mbinder = new imyfeature.stub() { public void dotask(string classname) { try { class<?> clazz = class.forname(classname); constructor<?> ctor = clazz.getconstructor((class[]) null); object object = ctor.newinstance(); ...
Read more

php - Improving script execution time -

i want improve execution time of insert query, because webhost not change max_execution_time. script below contains test wallclock execution time. results in 22 seconds execution time way long because webhost keeps default @ 30 seconds. after code below, more code needs executed. reference, there 1000 players in tblplayers. $time_start = microtime(true); $sqltotalpoints = array(); $sqlcompetingplayers = "select id tblplayers game='" . $gamenumber. "' , joined='1'"; $resultcompetingplayers = mysql_query($sqlcompetingplayers); while($row= mysql_fetch_array($resultcompetingplayers)) { $playerid = $row['id']; $sqlalreadyhaspoints = "select playerid tblplayerpoints playerid='" . $playerid . "'"; $resultalreadyhaspoints = mysql_query($sqlalreadyhaspoints); $pointsrowfound = mysql_num_rows($resultalreadyhaspoints); if($pointsrowfound < 1 ) { $sqltotalpoints[] = '("' . $ga...
Read more

How to provide Authorization & Authentication using Asp.net, C#? -

Image
i have asp.net application in c#. i have provide page authorization specific user/usergroup. i have created 2 tables in database: 1) pagename 2)permissions[insert, update, view, delete] but i'm unable match tables , permissions assigning... can 1 please me, how created tables in database , how coding. please me. you can below explanation. configure access specific file , folder, set forms-based authentication. request page in application redirected logon.aspx automatically. in web.config file, type or paste following code. this code grants users access default1.aspx page , subdir1 folder . <configuration> <system.web> <authentication mode="forms" > <forms loginurl="login.aspx" name=".aspnetauth" protection="none" path="/" timeout="20" > </forms> </authentication> <!-- section denies access files in...
Read more