Я не уверен, что случилось с моей функцией перегородки

Question

Eclipse продолжает рассказывать мне, что что-то не так с моей функцией разделения. Он находится в java и является частью класса, который предназначен для сортировки массивов.

Раздел работает следующим образом: в массиве есть два индекса i и j, а в самом начале алгоритма разбиения i указывает на первый элемент массива, а j указывает на последний. Затем алгоритм перемещает i вперед, пока не будет найден элемент со значением, большим или равным оси. Индекс j перемещается назад, пока не будет найден элемент со значением, меньшим или равным оси. Если i ≤ j, то они меняются местами, и i переходит к следующей позиции (i + 1), j - к предыдущей (j - 1). Алгоритм останавливается, когда i становится больше j.

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

public static int partition(int arr[], int left, int right) 
    { 
     int x = arr[right]; 

     int i = left-1; 
     int temp=0; 

     for (int j=left; j<right; j++) 
     { 
      if(arr[j]<=x) 
      { 
       i++; 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 

      } 
     } 

     temp = arr[i+1]; 
     arr[i+1] = arr[right]; 
     arr[right] = temp; 
     return (i+1); 

    } 

EDIT

Eclipse, говорит, что есть две проблемы, одна из которых с этой строки кода в функции раздела:

int x = arr[right]; 

И с этой линии моего тестового класса:

sort.partition(array, 100, array.length); 

Вот класс испытаний, который включает в себя функции, о которых я не упоминал.

import java.util.Random; 


public class test { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     int size = 1000; 
     int max = 5000; 
     int[] array = new int[size]; 
     int loop = 0; 

     Random generator = new Random(); 
     //Write a loop that generates 1000 integers and 
     //store them in the array using generator.nextInt(max) 

     generator.nextInt(max); //generating one 

     //I need to generate 1000 
     //So I need some kind of loop that will generate 1000 numbers. 

     for (int i =0; i<1000; i++) 
     { 
      generator.nextInt(max); 
     } 



     /** 
     * After I do this, I'll have the array, array. 
     * Then comes what's under this. 
     * THat method is for measuring the time. 
     * System.currentTimeMillis();, 
     * with this, I can collect a time for the start of the method 
     * and one for the end. 
     * Time at the end, minus the time at the start 
     * gets us the running time. 
     */ 



     long result; 

     long startTime = System.currentTimeMillis(); 
     sort.quickSort(array, 100, array.length-1); 
     long endTime = System.currentTimeMillis(); 
     result = endTime-startTime; 

     System.out.println("The quick sort runtime is " + result + " miliseconds"); 

     long result2; 

     long startTime2 = System.currentTimeMillis(); 
     sort.partition(array, 100, array.length); 
     long endTime2 = System.currentTimeMillis(); 
     result2 = endTime2 - startTime2; 
     System.out.println("The partition runtime is "+result2 + " miliseconds"); 

     long result3; 

     long startTime3 = System.currentTimeMillis(); 
     sort.bubbleSort(array, 100); 
     long endTime3 = System.currentTimeMillis(); 
     result3 = endTime3-startTime3; 
     System.out.println("The bubble sort runtime is "+result3 + " miliseconds"); 

     long result4; 

     long startTime4 = System.currentTimeMillis(); 
     sort.selectionSort(array, 100); //change the second number to change 
     //the size of an array. 
     long endTime4 = System.currentTimeMillis(); 
     result4 = endTime4-startTime4; 
     System.out.println("The selection sort runtime is "+result4 + " miliseconds"); 



    } 

} 

Answer 1

Прежде всего, вы на самом деле не храните случайные числа в массиве, так что это будут все нули.

Что касается фактической ошибки, которую вы видите, у вас есть классика от одной ошибки. У вас есть два варианта: make right указывает на конец массива или один конец конца массива. Любой из них действителен, но вы смешиваете два.

В частности, вы передаете 1000, один за концом массива, для значения right, но затем вы сразу же индексируете массив с ним, естественно бросая исключение.