secret
Created

my median method and main

  • Download Gist
gistfile1.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
import java.util.ArrayList;
import java.util.Random;
 
 
public class quicksortagain {
public static void main(String[] args) throws Exception
{
ArrayList<Integer> rList = new ArrayList<Integer>();
Random r = new Random();
 
for (int i = 0; i < 25; i++) rList.add(r.nextInt(50));
System.out.println(qkSort(rList, rList.size()/2));
}
/**
*
* @param intList
* @param k
* @return
* @throws Exception
*/
public static int qkSort(ArrayList<Integer> intList, int k) throws Exception
{
if(intList.size() == 1) return intList.get(0);
Random r = new Random();
int size = intList.size();
//System.out.println(size);
int randInt = r.nextInt(size);//pick a random int that is within the size of the list
int otherH = intList.get(randInt);//hold it for later use
intList.remove(randInt);//take out of list
 
ArrayList<Integer> lower = new ArrayList<Integer>();//place to store ints that are lower
ArrayList<Integer> higher = new ArrayList<Integer>();//place to store ints that are higher
 
 
 
for (int i = 0; i < intList.size(); i++)//loop through list
{
int hold = intList.get(i);//hold for comparison
if(hold <= otherH ) lower.add(hold);//if it is less than the random one, add to lower list
else higher.add(hold);//if not lower... add to higher list
}
 
if (k <= lower.size())//if less than or equal to
{
return qkSort(lower, k);//go through again with lower ints
}
int difference = lower.size()-higher.size();
int otherDif = intList.size()-higher.size();
if (k > difference)
{
return qkSort(higher, k-otherDif);//go through again with higher ints
}
else
return otherH;
}
 
 
 
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.