Quicksort С Компаратором

Question

I'am работает над проектом для сортировки массива объектов Student со следующим critiria:

1.Sort сорта

сорта 2.Ели равны, сортировать по StudentNumber.

Теперь я получил эту работу, используя метод Arrays.Sort (T [] a, Comparator <> c). , так как я думаю, что этот метод сортировки должен замедляться, я хочу использовать Quicksort.

я получил следующий фрагмент кода:

public static void quickSort(Student[] arr, int low, int high) { 
    if (arr == null || arr.length == 0) { 
     return; 
    } 
    if (low >= high) { 
     return; 
    } 
    // pick the pivot 
    int middle = low + (high - low)/2; 
    Student pivot = arr[middle]; 
    // make left < pivot and right > pivot 
    int i = low, j = high; 
    while (i <= j) { 
     while (arr[i].getCijfer() < pivot.getCijfer()) { 
      i++; 
     } 
     while (arr[j].getCijfer() > pivot.getCijfer()) { 
      j--; 
     } 
     if (i <= j) { 
      Student temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
      i++; 
      j--; 
     } 
    } 
    // recursively sort two sub parts 
    if (low < j) { 
     quickSort(arr, low, j); 
    } 
    if (high > i) { 
     quickSort(arr, i, high); 
    } 
} 

UPDATE Компаратор Код:

private static Comparator<Student> gradeComparator = new Comparator<Student>() { 
    @Override 
    public int compare(Student o1, Student o2) { 
     int compareTo = 0; 
     if (o1.cijfer > o2.cijfer) { 
      compareTo = -1; 
     } else { 
      if (o1.cijfer < o2.cijfer) { 
       compareTo = 1; 
      } else { 
       // als Studenten Grade gelijk, vergelijk op studenten Ldap 
       if (o1.cijfer == o2.cijfer) { 
        if (o1.studentnummer > o2.studentnummer) { 
         compareTo = -1; 
        } else { 
         compareTo = 1; 
        } 
       } 
      } 
     } 
     return compareTo; 
    } 
}; 

это сортирует массив на Сорта (cijfer), но i'am застрял на том, где поставить свою 2-й критерий сортировки. пожалуйста помогите!

Сердечные приветы

Answer 1

Вы должны были бы поставить второй критерий в любом месте вы сравнить два Student экземпляры, например,

if (arr[i].getCijfer() < pivot.getCijfer() 
    || (arr[i].getCijfer() == pivot.getCijfer() 
     && arr[i].getStudentNumber() < pivot.getStudentNumber())) 

Однако, это неудобно, чтобы добавить несколько критериев здесь, так что вы бы лучше введения метода, в котором делается сравнение:

if (compare(arr[i], pivot) < 0) 

, а затем толкая логику сравнения в этом методе, так что он возвращает некоторое число в зависимости от того, меньше или равно arr[i], чем pivot.

Обратите внимание, что это в основном то, что Comparator обеспечивает:

class MyComparator implements Comparator<Student> { 
    @Override int compare(Student a, Student b) { 
    if (a.getCijfer() != b.getCijfer()) { 
     return // Some comparison of a.getCijfer() and b.getCijfer() 
    } 
    // Somehow compare student number. 
    } 
} 

Answer 2

Это выражение: arr[i].getCijfer() < pivot.getCijfer() и это: arr[j].getCijfer() > pivot.getCijfer() являются источником вашей проблемы. Вам нужно извлечь их в одну функцию, которая возвращает целое число, реализованное следующим образом: return Integer.compare(a.getCijfer(), b..getCijfer());.

Но тогда вы заметите, что это всего лишь функция компаратора, поэтому вы можете продолжать и модифицировать ее для работы точно так же, как она работала, когда вы использовали Arrays.sort() с компаратором.

Это касается вашего вопроса.

Однако, имейте в виду следующее:

1. Ваше подозрение, что Arrays.sort() будет медленнее, чем какой-то сортировки совершенно необоснованны, и, скорее всего, неверно.

2. Ваша вера в то, что вы можете сделать быструю сортировку на дому, которая будет работать лучше, чем Arrays.sort(), скорее всего, будет ложной.

3. Если вы не знаете, как получить свою быструю сортировку на дому, чтобы отсортировать ее по своему усмотрению, и вы должны спросить о стеке, нет ничего плохого в этом, но тогда, очевидно, сортировка - это тема который намного более продвинут, чем то, что ваш профессор ожидает от вас.