Я пытаюсь реализовать свою собственную версию на быстрой сортировке. Я был очень счастлив, когда увидел, что он отсортирован по небольшим массивам, но как только я попробовал использовать более крупные входы массива, такие как 1k, 50k, 100k, 1000k. Я увидел, что время выполнения оказалось выше, чем ожидалось, и когда я попытался с массивом ввода 1000k, это вызвало переполнение стека.
Я хотел бы получить обратную связь по моему коду, что я должен изменить в коде, чтобы алгоритм работали прокомментируйте, почему он в настоящее время не работает с моим кодом.
Я добавил run_partition = false, как только я обнаружил, что левый указатель и правый указатель указывают на один и тот же индекс. Это позволило сортировать для входного массива 100 тыс.
// 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;
}
}
Я ожидаю, что код будет работать для ввода массива большего размера.