Блог

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

Проект должен был реализовать сортировку слиянием и оценить ее. Проблемной областью является подсчет критических операций и определение отклонения от подсчета путем случайного заполнения массива 10 различными размерами, и каждый размер выполнялся 50 раз (с разными случайными данными). Мои выводы заключались в том, что для каждого размера количество критических операций всегда заканчивалось одинаково (например, массив размером 10 достиг 68 критических операций независимо от данных), оставляя отклонение критических операций равным 0.

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

Ниже приведен мой код, который я написал, что, опять же, независимо от данных, он по-прежнему производит одинаковое количество критических операций. Может ли кто-нибудь указать на мою проблему? Независимо от того, что я делаю с подсчетом, он всегда выдает одно и то же значение.

 public class MergeSortSingle {
public static int count = 0;

private MergeSortSingle() { }

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k  ) {
        count  ;
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid 1;
    for (int k = lo; k <= hi; k  ) {
        if      (i > mid) {
            count  ;
            a[k] = aux[j  ];
        }
        else if (j > hi) {
            count  ;
            a[k] = aux[i  ];
        }
        else if (less(aux[j], aux[i])) {
            count  ;
            a[k] = aux[j  ];
        }
        else      {
            count  ;
            a[k] = aux[i  ];
        }
    }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo   (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid   1, hi);
    merge(a, aux, lo, mid, hi);
}

public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length-1);
}

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

private static void show(Comparable[] a) {
    System.out.println("nAfter Sorting completed:");
   System.out.print(Arrays.toString(a));
   System.out.println();
}

public static void main(String[] args) {
    int length = 10;
    Comparable[] a = new Comparable[length];
    for (int w = 0; w < length; w  ) {
            a[w] = (int) (Math.random() * 10000   1);
        }
    System.out.println("Before Sorting:");
    System.out.print(Arrays.toString(a));
    System.out.println();
    MergeSortSingle.sort(a);
    show(a);
    System.out.println("nCounter = "   count);
}
}
 

Пример вывода 1:

Перед сортировкой: [9661, 4831, 4865, 3383, 1451, 3029, 5258, 4788, 9463, 8971]

После завершения сортировки: [1451, 3029, 3383, 4788, 4831, 4865, 5258, 8971, 9463, 9661]

Счетчик = 68

Пример вывода 2:

Перед сортировкой: [9446, 230, 9089, 7865, 5829, 2589, 4068, 5608, 6138, 372]

После завершения сортировки: [230, 372, 2589, 4068, 5608, 5829, 6138, 7865, 9089, 9446]

Счетчик = 68

Код сортировки слиянием был использован из: http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

Вы считаете только при объединении подмассивов — вы используете счетчик для копирования массива tro aux — это всегда будет одинаковое количество операций, а затем вы снова используете его в for цикле — у вас есть 4 пути, и каждый из них увеличивает счетчик — опять же, фиксированное количество операцийраз.
вы также должны учитывать сопутствующие операции в sort — if (hi <= lo) — его операциях. Если это не удается — это другая операция.