Слияния сортировки сортировки?

Question

Я не думаю, что количество сравнений с использованием сортировки слияния является правильным в моем методе сортировки 2-го класса/method, который возвращает количество сравнений. Слияние sort 2 похоже на сортировку слияния, но просто возвращает количество сравнений. Ниже мое демо, у меня есть массив из 4 целых чисел {2,55,1,45}, и когда я запускаю программу, он возвращает 8 сравнений. Может ли кто-нибудь проверить, правильно ли это или что я делаю неправильно?

Мой демо:

ArrayInts[] myInts2 = new ArrayInts[4]; 

    myInts2[0] = new ArrayInts(2); 
    myInts2[1] = new ArrayInts(55); 
    myInts2[2] = new ArrayInts(1); 
    myInts2[3] = new ArrayInts(45); 

    MergeSort.mergeSort(myInts2, 0, 3); 

    System.out.println("Sorted using Merge Sort: "); 


    for (int index = 0; index < myInts2.length; index++) { 
     System.out.println(myInts2[index]); 
    } 

    System.out.println("Number of comps using Merge Sort: " + MergeSort2.mergeSort2(myInts2, 0, 3)); 
    System.out.println(" "); 

Моя сортировка слиянием 2 класс/метод:

public class MergeSort2 { 
private static long comp=0; 

public static <T extends Comparable<? super T>> long mergeSort2(T[] data, int min, int max) { 
    T[] temp; 
    int index1, left, right; 


    //return on list of length one 

    if (min == max) { 
     return comp; 
    } 

    //find the length and the midpoint of the list 

    int size = max - min + 1; 
    int pivot = (min + max)/2; 
    temp = (T[]) (new Comparable[size]); 

    mergeSort2(data, min, pivot); //sort left half of list 
    mergeSort2(data, pivot + 1, max); //sort right half of list 

    //copy sorted data into workspace 

    for (index1 = 0; index1 < size; index1++) { 
     temp[index1] = data[min + index1]; 
    } 

    //merge the two sorted lists 

    left = 0; 
    right = pivot - min + 1; 
    for (index1 = 0; index1 < size; index1++) { 
     comp++; 
     if (right <= max - min) { 

      if (left <= pivot - min) { 

       if (temp[left].compareTo(temp[right]) > 0) { 

        data[index1 + min] = temp[right++]; 
       } else { 
        data[index1 + min] = temp[left++]; 
       } 
      } else { 
       data[index1 + min] = temp[right++]; 
      } 
     } else { 
      data[index1 + min] = temp[left++]; 
     } 
    } 


    return comp; 

    } 

    } 

Answer 1

вы получаете 8, потому что вы приращением каждый раз, когда цикл слияния выполняет ли это сравнение или нет ,

если изменить

for (index1 = 0; index1 < size; index1++) { 
    comp++; 
    if (right <= max - min) { 

     if (left <= pivot - min) { 

в

for (index1 = 0; index1 < size; index1++) { 
    if (right <= max - min) { 

     if (left <= pivot - min) { 
      comp++; 

вы получите число сравнений, сделанные, а не количество итераций цикла.

[0,1,2,3] должно дать 4 сравнения
[3,2,1,0] должно дать 4 сравнения
[0,2,1,3] должно дать 5 сравнений
[ 0,4,1,5,2,6,3,7] должно давать 16 сравнений

merge sort - это алгоритм наихудшего случая O (nlog2n).

вы также должны изменить этот бит

MergeSort.mergeSort(myInts2, 0, 3); 

System.out.println("Sorted using Merge Sort: "); 


for (int index = 0; index < myInts2.length; index++) { 
    System.out.println(myInts2[index]); 
} 

System.out.println("Number of comps using Merge Sort: " + MergeSort2.mergeSort2(myInts2, 0, 3)); 
System.out.println(" "); 

в

int result = MergeSort.mergeSort(myInts2, 0, 3); 

System.out.println("Sorted using Merge Sort: "); 


for (int index = 0; index < myInts2.length; index++) { 
    System.out.println(myInts2[index]); 
} 

System.out.println("Number of comps using Merge Sort: " + result); 
System.out.println(" "); 

в myInts будут отсортированы при выводе количества, так что вы получите отсортированный сложности.

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

public static void main(String[] args) { 
    Integer[] myInts2 = new Integer[4]; 

    myInts2[0] = new Integer(0); 
    myInts2[1] = new Integer(2); 
    myInts2[2] = new Integer(1); 
    myInts2[3] = new Integer(3); 

    System.out.println(new MergeSort2().mergeSort2(myInts2, 0, 3)); // will output 5 
    System.out.println(new MergeSort2().mergeSort2(myInts2, 0, 3)); // will output 4 
} 

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

Answer 2

Количество отображаемых вами результатов отображается правильно по методу, предоставленному нами. Когда массив длины 4 передан в метод, который вы нам предоставили, строка comp++; называется 8 раз. Позволь мне объяснить.

Во-первых, pivot=1. Эти линии делают две рекурсивные вызовы:

mergeSort2(data, min, pivot); //sort left half of list 
mergeSort2(data, pivot + 1, max); //sort right half of list 

После каждого из этих вызовов завершить свои два дополнительных вложенных рекурсивных вызовов, они идут на приращение comp на 2, так как цикл проходит несколько итераций, равное size.В обоих этих вызовах size=2, поэтому после звонка один, comp=2, и после звонка два, comp=4. Каждый из этих рекурсивных вызовов, в свою очередь, делает еще два рекурсивных вызова, потому что в каждом из этих вызовов min==max метод возвращается на return comp;, никогда не дойдя до строки, чтобы увеличить comp.

Наконец, после возвращения двух исходных рекурсивных вызовов метода приращение для цикла 2 вызывается еще четыре раза, поскольку при начальном вызове size=4. Таким образом, comp = 4 + 4, что равно 8!

Если это сбивает с толку, я проиллюстрирую свой ответ с помощью (min, max) каждого звонка на номер mergesort2().

/* 1. */ (min=0, max=3) -> size=4, comp = comp + 4; 
/* 2. */  (min=0, max=1) -> size=2, comp = comp + 2; 
/* 3. */   (min=0, max=0) -> size=0, comp = comp + 0; 
/* 4. */   (min=1, max=1) -> size=0, comp = comp + 0; 
/* 5. */  (min=2, max=3) -> size=2, comp = comp + 2; 
/* 6. */   (min=2, max=2) -> size=0, comp = comp + 0; 
/* 7. */   (min=3, max=3) -> size=0; comp = comp + 0; 

/* TOTAL. */ comp = 0 + 0 + 2 + 0 + 0 + 2 + 4; comp = 8 

Надеюсь, я разъяснил здесь!

edit1: Ответ BevynQ верен. Мой ответ больше посвящен , почему ваш код возвращается 8, в то время как его ответ фокусируется на , почему ваш метод сортировки неверно подсчитывает сравнения.

edit2: Я скопировал и вставил ваш код непосредственно в свой редактор и сделал однострочное изменение BevynQ. Мой код работает по назначению, и я не вижу таких же результатов. Возможно, что-то еще случайно было изменено?