Quick Sort

In Quick Sort, which of the following is a common strategy for selecting the pivot element?

• Choosing the first element

• Choosing a random element

• Choosing the median of the first, middle, and last elements

• all of the above

What is Quick Sort?

• A sorting algorithm that divides the array into smaller parts and sorts them independently.
  (Алгоритм сортировки, который делит массив на меньшие части и сортирует их независимо.)

• A divide-and-conquer algorithm that sorts items by partitioning an array into sub-arrays.
  (Алгоритм «разделяй и властвуй», который сортирует элементы путем разделения массива на подмассивы.)

• A linear search algorithm that finds the correct order of elements.
  (Алгоритм линейного поиска, который находит правильный порядок элементов.)

• An algorithm that sorts the array by repeatedly swapping adjacent elements.
  (Алгоритм, который сортирует массив, постоянно меняя местами соседние элементы.)

What is the time complexity of Quick Sort in the best case

• O(n)

• O(log n)

• O(n²)

• O(n log n)
  

What is the time complexity of Quick Sort in the worst case?

• O(n log n)

• O(n)

• O(n²)

• O(log n)

In which situation does the worst case time complexity of Quick Sort occur?

• When the pivot divides the array into two nearly equal halves.
  (Когда опорный элемент делит массив на две почти равные части.)

• When the array is already sorted or reverse sorted.
  (Когда массив уже отсортирован или отсортирован в обратном порядке.)

• When a random pivot is chosen.
  (Когда выбирается случайный опорный элемент.)

• When the array contains only identical elements.
  (Когда массив содержит только одинаковые элементы.)

What is the space complexity of Quick Sort?

• O(log n)

• O(n)

• O(n log n)

• O(1)

Stability yes or no

• NO

• YES

How does Quick Sort's cache performance compare to Merge Sort?
(Как производительность кеша у Quick Sort по сравнению с Merge Sort?)

• Quick Sort has better cache locality, which leads to faster execution.
  (У Quick Sort лучшая локальность кеша, что приводит к более быстрому выполнению.)

• Merge Sort has better cache locality.
  (У Merge Sort лучшая локальность кеша.)

• Both Quick Sort and Merge Sort have the same cache performance.
  (У Quick Sort и Merge Sort одинаковая производительность кеша.)

• Cache performance doesn't affect the performance of these algorithms.
  (Производительность кеша не влияет на производительность этих алгоритмов.)

Why is Quick Sort generally faster than Merge Sort in practice?

• Because Quick Sort uses fewer recursive calls.

• Because Quick Sort has lower constant factors in its time complexity.

• Because Merge Sort is not efficient in handling large datasets.

• Because Quick Sort uses a simpler sorting technique

What is one key advantage of Quick Sort's in-place sorting feature?

• It doesn't require additional memory for a temporary array.

• It sorts data faster by avoiding recursion.

• It makes Quick Sort easier to implement.

• It is more stable than Merge Sort.