Рандомизированный алгоритм выбора

Question

Я пытаюсь реализовать рандомизированный алгоритм выбора, где массив заполняется случайными числами, и пользователь выбирает местоположение, и программа возвращает значение, совпадающее с местоположением в отсортированной версии массива, без фактической сортировки массив.

Проблема в том, что программа задает значение элемента в данном месте, но в несортированном массиве.

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 < 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 < 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 <= end-1; j++) { 
      if (array[j] <= 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; 
    }  
} 

Выход этой программы, если пользователь выбирает выбор расположения 4: Массив был: [195, 24, 111, 50, 37, 128, 196, 117, 167, 195]

отсортированный массив должен быть: [24, 37, 50, 111, 117, 128, 167, 195, 195, 196]
который должен сделать выбор расположения 4 равно 111, а не 50.

Answer 1

Попробуйте помещать отсортированный массив или, как минимум, массив, в конце каждого вызова которого находится randomizedPartition. Вы обнаружите, что массив не изменился с момента его создания.

Теперь попробуйте посмотреть на свой массив после каждого вызова до swap, снова вы заметите, что массив не изменяется с помощью метода swap. Итак, теперь мы знаем, что метод swap работает не так, как вам хотелось бы.

Почему это может быть?

Вы читали о пропущенных ссылках и пропусках по значению?

для примитивов Java использует раззё по значению не ссылаются поэтому параметры метода swapi & j являются копиями значений, хранящихся в массиве, изменяя значение i или j не будет влиять на массив вообще.

Попробуйте изменить подпись свопа на

private static void swap(int[] array, int indexI, int indexJ) {...} 

Измените тело метода swap для перемещения элементов в массиве, и посмотреть, как это происходит.

Кстати, ваш код будет намного лучше с лучшими именами переменных. Также неверный диапазон для генератора случайных чисел для инициализации массива.