Образовательный ресурс edu.irnok.net

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Быстрая сортировка с различными опорными элементами ======

**Задание:** Реализовать быструю сортировку с выбором опорного элемента различными способами (первый элемент, последний элемент, средний элемент, медиана трех, случайный элемент). Визуализировать процесс разделения массива.

**Пример входных данных:**

<code>
Массив: [7, 2, 1, 6, 8, 5, 3, 4]
Способ выбора опорного элемента: последний элемент
Точность: 0.0001 (не используется)

</code>

**Пример выходных данных:**

<code>
Исходный массив: [7, 2, 1, 6, 8, 5, 3, 4]
Опорный элемент (последний): 4

Разделение 1:
  Индексы: i=0, j=0
  Сравнение 7 > 4? Да, пропускаем
  Индексы: i=1, j=1
  Сравнение 2 <= 4? Да, меняем с элементом [0]: [2, 7, 1, 6, 8, 5, 3, 4]
  Индексы: i=2, j=2
  Сравнение 1 <= 4? Да, меняем с элементом [1]: [2, 1, 7, 6, 8, 5, 3, 4]
  Индексы: i=3, j=3
  Сравнение 6 > 4? Да, пропускаем
  Индексы: i=4, j=4
  Сравнение 8 > 4? Да, пропускаем
  Индексы: i=5, j=5
  Сравнение 5 > 4? Да, пропускаем
  Индексы: i=6, j=6
  Сравнение 3 <= 4? Да, меняем с элементом [2]: [2, 1, 3, 6, 8, 5, 7, 4]
  Ставим опорный элемент на место: меняем [3] и [7]: [2, 1, 3, 4, 8, 5, 7, 6]
  
Левая часть: [2, 1, 3]
Правая часть: [8, 5, 7, 6]

Разделение 2 (левая часть, опорный=3):
  [2, 1, 3] -> после разделения: [1, 2, 3]

Разделение 3 (правая часть, опорный=6):
  [8, 5, 7, 6] -> после разделения: [5, 6, 7, 8] -> [5, 6, 7, 8]

Отсортированный массив: [1, 2, 3, 4, 5, 6, 7, 8]
Количество итераций разделения: 3

</code>


**Вариант 1:** Массив: [10, 7, 8, 9, 1, 5]

**Вариант 2:** Массив: [64, 34, 25, 12, 22, 11, 90]

**Вариант 3:** Массив: [3, 6, 1, 8, 4, 9, 2, 7, 5]

**Вариант 4:** Массив: [100, 90, 80, 70, 60, 50, 40, 30, 20, 10]

**Вариант 5:** Массив: [45, 23, 67, 12, 89, 34, 56, 78]

**Вариант 6:** Массив: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

**Вариант 7:** Массив: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

**Вариант 8:** Массив: [29, 10, 14, 37, 13, 25, 48, 7]

**Вариант 9:** Массив: [55, 33, 77, 11, 99, 44, 66, 22, 88]

**Вариант 10:** Массив: [15, 25, 35, 45, 55, 65, 75, 85, 95]

**Вариант 11:** Массив: [95, 85, 75, 65, 55, 45, 35, 25, 15]

**Вариант 12:** Массив: [42, 17, 89, 63, 31, 76, 24, 58]

**Вариант 13:** Массив: [8, 3, 1, 6, 9, 2, 7, 4, 5]

**Вариант 14:** Массив: [100, 50, 25, 75, 12, 37, 62, 87]

**Вариант 15:** Массив: [19, 28, 37, 46, 55, 64, 73, 82, 91]

**Вариант 16:** Массив: [91, 82, 73, 64, 55, 46, 37, 28, 19]

**Вариант 17:** Массив: [6, 2, 9, 4, 7, 1, 8, 3, 5]

**Вариант 18:** Массив: [33, 66, 99, 11, 44, 77, 22, 55, 88]

**Вариант 19:** Массив: [14, 27, 39, 52, 65, 78, 81, 93]

**Вариант 20:** Массив: [93, 81, 78, 65, 52, 39, 27, 14]

**Способы выбора опорного элемента:**
  * Варианты 1-5: Первый элемент
  * Варианты 6-10: Последний элемент
  * Варианты 11-15: Средний элемент
  * Варианты 16-20: Медиана трех (первый, средний, последний)

**Дополнительное задание (на 5):** Реализовать выбор случайного опорного элемента и сравнить количество итераций с другими способами для всех вариантов массивов.