Динамический массив в порядке печати

Question

Мне нужно напечатать массив в порядке от наибольшего к наименьшему.Для простоты скажем, что это массив целых чисел.

Единственный способ, которым я могу думать, это сделать цикл по массиву, найти самый большой элемент, напечатать его и установить соответствующий логический флаг, чтобы он не печатался дважды.Есть ли лучший способ сделать это?

int *array;

// Fill array, malloc, all that good stuff

int i, j, max = 0, max_index = 0;
int isPrinted[ARRAY_SIZE] = {0};

for (i = 0; i < ARRAY_SIZE; i++) {
  for (j = 0; j < ARRAY_SIZE; j++) {
    if (isPrinted[j] == 0 && array[j] > max) {
      max = array[j];
      max_index = j;
    }  
  }
  isPrinted[max_index] = 1;
  printf("%d", max);
  max = 0;
}

Answer 1

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

Answer 2

Сортируйте, затем распечатайте.Для целых чисел это можно сделать за линейное время.Со стандартным qsort это O(n*log(n)).

// stdlib.h
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); 

Answer 3

Не можете ли вы отсортировать массив, а затем распечатать его? Или скопировать массив, отсортировать копию и распечатать ее? Сложность будет значительно лучше (O (n log (n)) вместо O (n ** 2) с вашим алгоритмом).

Answer 4

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

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

Answer 5

Если вы можете изменить порядок элементов, вы можете использовать алгоритм сортировки в вашем массиве перед печатью.

Answer 6

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