Пытаясь реализовать быструю сортировку и использовать сортировку вставкой, когда размер списков <= 10. получение неправильных результатов

Question

import java.util.Comparator;


public class SortedList implements Container{
private int size;
private int front = 0;
private int rear = 0;
private WorkOrder[] buffer;
Comparator comparator;

public SortedList(){
    buffer = new WorkOrder[10];
}
/**
 * The comparator that the container will use to arrange the container
 * 
 * @param comp
 */
public void setComparator(Comparator comp){
    if (comp == null){
        throw new IllegalArgumentException();
    }
    comparator = comp;
}

/**
 * Add a workorder to the container
 */
public void add(WorkOrder wo){
    if(wo == null){
        throw new IllegalArgumentException();
    }
    if (size == capacity()){
        WorkOrder[] regrowArray = new WorkOrder[2*capacity()];
        for (int i = 0; i<size;i++){
            regrowArray[i] = buffer[i];
        }
        buffer = regrowArray;
        rear = size;
    }

    buffer[rear] = wo;
    rear++;
    size++;
}

/**
 * Gets a workorder (removes it also) from the container
 */
public WorkOrder getNext(){
    if (isEmpty()){
        return null;
    }
    WorkOrder itemRemoved = buffer[front];
    buffer[front] = null;
    front++;
    size--;

    return itemRemoved;
}

/**
 * Arranges the workorders in the required order
 * Uses the comparator if necessary
 * Some data structures may not need this method (like Queue)
 * Just make it a no-op for those structures.
 */
public void arrange(){
    if (buffer == null || size == 0){
        return;
    }
    partition(0,size-1);
    //sort(0,size-1);
}

private void partition(int left, int right){
    int pivotIndex = (right + left) / 2;
    int i = left;
    int j = right;

    if ((right-left) <= 10){
        insertionSort(left,right);
        return;
    }
    while (i <= j){
        while (comparator.compare(buffer[i],buffer[pivotIndex]) < 0){
            i++;
        }
        while (comparator.compare(buffer[j],buffer[pivotIndex]) > 0){
            j--;
        }
        if (i <= j){
            swap(i,j);
            i++;
            j--;
        }
    }
    if (left < j){
        partition(left,j);
    }
    if (i<right){
        partition(i, right);
    }
}

private void insertionSort(int left, int right){
    for (int i = 1; i < right; i++){
        WorkOrder val = buffer[i];
        int j = i - 1;
        while (j>=0 && comparator.compare(buffer[j], val) > 0){
            buffer[j+1] = buffer[j];
            j = j - 1;
        }
        buffer[j+1] = val;
    }
}

private void swap(int x, int y){
    WorkOrder temp = buffer[x];
    buffer[x] = buffer[y];
    buffer[y] = temp;
}
}

вывод, который я вижу: 0123567894

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

Answer 1

Проблема, кажется, ее insertion sort часть:

for (int i = 1; i < right; i++){ //going from 1 to one previous to the last (right - 1)
    WorkOrder val = buffer[i];
    int j = i - 1;
    while (j>=0 && comparator.compare(buffer[j], val) > 0){
        buffer[j+1] = buffer[j];
        j = j - 1;
    }
    buffer[j+1] = val;
}

Вы должны принять во внимание, что он должен зацикливаться до последнего, так как вы знаете, что right Переменная является последним индексом этого раздела.

for (int i = 1; i <= right; i++) //replace < for <=

так как право является последним индексом (и это нужно учитывать) массива при его 10 или менее элементах.

edit:

Единственное, что я еще вижу (в quick sort код) это часть:

if (left < j){ 
    partition(left,j); //trying to partition from left to j (since 'j' and 'i' may overlap)
}

так должно быть

if (left < (i - 1)){ 
    partition(left,i - 1); //so the partition doesnt overlap with the 'i' to 'right' partition by an element (since i and j may overlap at the end).
}

Таким образом вы гарантируете, что вы всегда делите раздел на половину.