title: Randomized Selection Algorithm
body: <p>I am trying to implement a randomized selection algorithm where an array is filled with random numbers and the user selects a location and the program returns the value coinciding with the location in the sorted version of the array without actually sorting the array.</p>
  
  <p>The problem is that the program is giving the value of the element at the given location but in the unsorted array.</p>
  
  <pre><code>import java.util.*;
  
  public class RandomizedSelection {
  
      public static void main(String[] args) {
          int maxSize = 10; // max size of the array
          int[] arr = new int[maxSize];
  
          // fill array with random numbers between the range of 0-200
          for (int i = 0; i &lt; maxSize; i++) {
              int n = (int)(java.lang.Math.random()*199); 
              arr[i] = n;
          }
  
          System.out.println("There is an array of 100 elements in the range" +
                              " of 0 - 200. Select a location to view" +
                              " the value.");
  
          Scanner in = new Scanner(System.in);
          int userChoice = in.nextInt(); // get user's choice of i
  
          int loc = randomizedSelect(arr, 0, arr.length-1, userChoice);
  
          System.out.println(loc);
  
          System.out.println("The array was:\n" + Arrays.toString(arr));
      }
  
      public static int randomizedSelect(int[] array, int p, int r, int i) {
          if (p == r)
              return array[p];
  
          if (i == 0)
              return -1;
  
              int mid = randomizedPartition(array, p, r);
              int k = mid - p + 1;
  
              if (k == i) 
                  return array[mid];
              else if (i &lt; k)
                  return randomizedSelect(array, p, mid-1, i);
              else
                  return randomizedSelect(array, mid+1, r, i-k);
  
      }
  
      public static int randomizedPartition(int[] array, int start, int end) {
          Random rand = new Random();
          int pivotIdx = rand.nextInt((end - start) + 1) + start;
          int pivot = array[pivotIdx];
  
          swap(array[pivotIdx], array[end]);
          pivotIdx = end;
  
          int i = start - 1;
  
          for (int j = start; j &lt;= end-1; j++) {
              if (array[j] &lt;= pivot) {
                  i++;
                  swap(array[i], array[j]);
              }
          }
          swap(array[i+1], array[pivotIdx]);
          return i+1;
      }
  
      public static void swap(int i, int j) {
          int temp = i;
          i = j;
          j = temp;
      }       
  }
  </code></pre>
  
  <p>The output of this program if the user selects a location choice 4 is:
  50 
  The array was: [195, 24, 111, 50, 37, 128, 196, 117, 167, 195]</p>
  
  <p>The sorted array should be:
  [24, 37, 50, 111, 117, 128, 167, 195, 195, 196] <br>
  which should make location choice 4 equal to 111, not 50.</p>