Одномерный массив содержит 10000 неотрицательных целых чи- сел, ** хранение каждого из...

Question

Одномерный массив содержит 10000 неотрицательных целых чи-
сел, на хранение каждого из которых отводится один байт. Со-
ставьте наиболее эффективную программу вывода на экран упо-
рядоченных по возрастанию элементов такого массива.
ПОМОГИТЕ ПОЖАЛУЙСТА!

Comments

Эффективную по каким критериям?

---

Кроме как "необходимо привести законченную программу на выбранном языке программирования", больше ничего нет

---

Бывает эффективность по расходу памяти, по времени выполнения...

---

Обычно и то, и другое редко совместимы )))

---

Значит пусть будет по расходу памяти)

---

Смущает слово "эффективное". Например, любая обменная сортировка массива производится на месте, используя для этого одну дополнительную ячейку пямяти. Есть также три алгоритма обмена, которые вообще не используют дополнительную память. Т.е. по умолчанию эффективность по памяти уже наличествует...

---

Но для 10 000 элементов обменная сортировка неэффективна по времени.

---

Тут нужно что-то типа "быстрой сортировки" для эффективности по времени.

---

В общем, думать надо над условием...

---

Эта задача из вступительного теста в универ и времени на решение осталось ОЧЕНЬ мало, сойдет уже любоеее решение)

Answer 1

// PascalABC.NET 3.1, сборка 1204 от 24.03.2016
const
  n=100; // заменить на 10000
var
  a:array[1..n] of byte;
  i:byte;
  j:integer;
begin
  // инициализация, для
  for j:=1 to n do a[j]:=Random(256);
  // собственно программа
  for i:=0 to 255 do
    for j:=1 to n do
      if a[j]=i then Write(i,' ');
end.

Тестовое решение:
5 8 9 11 11 14 14 17 18 19 21 22 24 24 29 30 33 36 40 45 46 47 55 55 56 58 61 62 64 66 68 73 74 75 85 88 91 94 96 96 96 98 102 103 108 109 111 111 116 119 122 123 129 129 130 135 137 139 143 144 149 149 155 155 160 169 170 173 177 178 181 182 190 193 196 198 199 199 200 206 206 207 209 222 224 225 226 229 230 235 237 240 243 246 249 250 251 252 254 255

Comments

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

---

Например, можно сделать предпросмотр, найдя минимальный и следующий за ним элементы. И внешний цикл вести не по всем 256 возмоным комбинациям, а начиная с первого минимума. Потом второй переопределить, как первый и выводить по нему, помутна отыскивая следующего кандидата.

---

*помутна - опечатка. ПОПУТНО