我正在尝试在quicksort上实现我自己的版本当我看到它为小数组排序时,我非常高兴,但是当我尝试1k、50k、100k、1000k等更大的数组输入时,我发现运行时间比预期的要长,而且当我尝试1000k数组输入时,它会导致stackoverflow。
我很想得到关于我的代码的反馈,我应该在代码中做些什么来使算法工作,并评论为什么它目前不使用我的代码。
当我发现左指针和右指针指向同一索引时,我添加了run_partition = false
。它使得对100k的输入数组进行排序成为可能。
// O(nlogn) worst case running time
// O(n) space complexity
import java.util.*;
public class Quicksort {
public int partition_array(int [] array, int start, int end) {
// The pivot pointer starts at the first element initially, array index = 0
// The left pointer points to first element initially
int left_pointer = start;
int right_pointer = end;
int pivot_pointer = left_pointer;
boolean run_partition = true;
// keep running partition until we return a pivot index, once we return a partition index we can do quicksort on the values left to partition and values to right of partition
while(run_partition) {
if( pivot_pointer == left_pointer) {
// If pivot points towards the left pointer then we have to make sure that all values to the right of pivot, make sure ew can sort duplicate keys too
while(array[pivot_pointer] <= (array[right_pointer]) && right_pointer != pivot_pointer ) {
right_pointer--;
}
if(left_pointer == right_pointer) {
// System.out.println(left_pointer + ": is same as " + right_pointer);
run_partition=false;
return pivot_pointer;
}
// if pivot points towards left pointer and we find out that there exists a right value that is smaller, we have to swap them.
else if(array[pivot_pointer] > (array[right_pointer]) ) {
// System.out.println("Right: " + array[right_pointer] + " is less than pivot_left: " + array[pivot_pointer]);
swap(array, pivot_pointer, right_pointer);
pivot_pointer = right_pointer;
}
else if( right_pointer < left_pointer){
break;
}
else {
right_pointer--;
}
}
if(pivot_pointer == right_pointer) {
// if pivot_pointer points towards right pointer then we have to make sure that all values to the left is smaller
while(array[pivot_pointer] > ( array[left_pointer]) && left_pointer != pivot_pointer) {
// increment left_pointer until this while condition is no longer true
left_pointer++;
}
if(pivot_pointer == left_pointer) {
run_partition=false;
// System.out.println(left_pointer + "is same as " + right_pointer);
return pivot_pointer;
}
else if(array[pivot_pointer] < (array[left_pointer])) {
// System.out.println("Left: " + array[left_pointer] + " er storre enn pivot: " + array[pivot_pointer]);
swap(array, pivot_pointer, left_pointer);
pivot_pointer= left_pointer;
}
else if( left_pointer < 0){
break;
}
else {
left_pointer++;
}
}
}
return -1;
}
public void quicksort(int [] array, int start, int end) {
// The pivot pointer starts at the first element initially, array index = 0
// The left pointer points to first element initially
// The right pointer points to last element initially
// All elements to the right of pivot must be greater than pivot
// All elements to the left of pivot must be smalelr than pivot
// The pivot pointer starts at the first element initially, array index = 0
// The left pointer points to first element initially
if(end<=start || start>=end){
return;
}
if(start <= end) {
int partition_index = partition_array(array,start,end);
quicksort(array,start,partition_index-1);
quicksort(array,partition_index+1,end);
}
// System.out.println(Arrays.toString(array));
}
public void swap(int[] array, int index_left, int index_right) {
int temp = array[index_left];
array[index_left] = array[index_right];
array[index_right] = temp;
}
}
我希望代码可以用于更大的数组输入。
最佳答案
算法实现使用递归,给定调用堆栈增长的大输入,这很可能是导致程序堆栈溢出的原因。您必须实现一个迭代版本来处理大型数组。