Я проверил, что мой алгоритм разделения работает хорошо, но когда приходит время реализации, чтобы использовать его, я получаю массив, который не отсортирован.Так как это для класса, есть определенное, что мне нужно написать сам класс, чтобы я мог вернуть ответ в виде строки.Моя проблема, скорее всего, связана с методом qkSort ().Вот код:
private static int splitterElement;
public static void main (String[] args){
System.out.println(myMethod());
}
public static String myMethod() {
String result = "";
int[] testArray = null;
testArray = populateArray(testArray, 7, 10);
result += "Before sort: \n" + printArray(testArray);
testArray = qkSort(testArray,1,testArray.length);
result += "After sort: \n" + printArray(testArray);
return result;
}
//Method to continually call the partition() method
public static int[] qkSort(int[] x, int left, int right){
if (right - left >= 1) {
//after running this method, the global variable splitterElement is assigned.
x = partition(x,left,right);
qkSort(x,left,splitterElement-1);
qkSort(x,splitterElement + 1,right);
}
//base case. if right-left = 0, then the array length is 1,
//and that is already sorted
return x;
}
/**
* Populates an integer array with random integers. Should be used only with
* non-itialized integer arrays.
*
* @param x an uninitialized array of integers and will be returned once it is populated.
* @param sizeOfArray The size that array x will be initialized to.
* @param rangeOfValues The range of values that that each element can be. This value should
* not surpass the maximum value for integers, but no error-checking is performed.
* @return
*/
public static int[] populateArray (int[] x, int sizeOfArray, int rangeOfValues){
x = new int[sizeOfArray];
for (int i = 0; i < sizeOfArray; i++){
x[i] = (int)(Math.random() * rangeOfValues); //place a random number from 0 to rangeOfValues into array.
}
return x;
}
/**
*
* @param x An integer array. It is assumed that x is initialized when the method is called.
* @param left
* @param right The length of the array can be used for the right int.
* @see #populateArray(int[], int, int)
* @return
*/
public static int[] partition (int[] x, int left, int right){
//element of the splitter
int l = (int) (Math.random() * x.length);
splitterElement = l;
x = swap (x,left,l);
//value of the splitter
int t = x[left];
int i = left;
for (int j = left + 1; j < right; j++){
if (x[j] < t){
i++;
x = swap (x,i,j);
}
}
x = swap(x,left,i);
return x;
}
/**
* Places the value at index1 in index2, and places the value at index2 in index1.
*
* @param array The array that will be worked on.
* @param index1 The first place we will switch values.
* @param index2 The second place we will switch values.
* @return
*/
public static int[] swap (int[] array, int index1, int index2){
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
return array;
}
/**
* A simple print method that prints an array.
* @param array Input.
*/
public static String printArray (int[] array){
String result = "";
for (int i = 0; i < array.length; i++){
result += array[i] + " ";
}
result += "\n";
return result;
}
}
Вывод:
До сортировки: 8 9 7 3 4 2 6
После сортировки: 8 6 39 7 2 4
Спасибо за любые идеи относительно моей проблемы!