0

Я не понимаю почему мой код сортировки не работает, но вроде бы все правильно сделано по теории. Например, для входных данных 2, 3, 1, 5, 4, вывод бывает 1, 2, 5, 3, 4.

public class Main {
  
  public static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2; i >= 0; i--) {
      heapify(a, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
      swap(a, i, 0);
      heapify(a, i, 0);
    }
  }
  
  public static void heapify(int[] heap, int n, int i) {
    int l = left(i);
    int r = right(i);
    int largest = i;
    if (l < n && heap[l] > heap[i]) {
      largest = l;
    }
    if (r < n && heap[r] > heap[i]) {
      largest = r;
    }
    if (i != largest) {
      swap(heap, i, largest);
      heapify(heap, n, largest);
    }
  }
  
  public static int right(int i) {
    return 2 * i + 2;
  }
  
  public static int left(int i) {
    return 2 * i + 1;
  }
  
  public static void swap(int[] heap, int i1, int i2) {
    int temp = heap[i1];
    heap[i1] = heap[i2];
    heap[i2] = temp;
  }
  
  public static void main(String[] args) {
    int[] A = new int[] {2, 3, 1, 5, 4};
    heapSort(A);
    for (int i = 0; i < A.length; i++)
      System.out.println(A[i]);
  }
}

1 ответ 1

1

У вас ошибка в методе heapify, в условиях.
Так выглядит правильный метод:

  public static void heapify(int[] heap, int n, int i) {
    int l = left(i);
    int r = right(i);
    int largest = i;
    if (l < n && heap[l] > heap[largest]) {
      largest = l;
    }
    if (r < n && heap[r] > heap[largest]) {
      largest = r;
    }
    if (i != largest) {
      swap(heap, i, largest);
      heapify(heap, n, largest);
    }
  }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.