Найдите самый маленький элемент в списке с помощью раздела - Помогите мне понять

Question

Хорошо, у меня есть задание найти самый маленький K-й элемент в списке, используя несколько различных методов ....

Первый метод - это сортировка списка, а затем возвращение K-го наименьшего элемента.просто, мой менталитет: скажем, список = 10 элементов, сортировка списка в порядке возрастания, затем возврат элемента в 10-ю позицию

следующий метод использует раздел из быстрой сортировки:

«Второй алгоритм заключается в применении процедуры Partition, используемой в быстрой сортировке. Процедура разделяет массив так, что все элементы, меньшие, чем какой-либо элемент сводки, располагаются перед ним в массиве, а все элементы, размер которых превышает этот элемент сводки, идут после него. Слот, в которомЭлемент pivot расположен и называется pivotposition. Мы можем решить проблему выбора путем разбиения, пока элемент pivot не окажется в k-м слоте. Мы делаем это путем рекурсивного разбиения левого подмассива, если k меньше, чем pivotposition, и рекурсивным разбиением правогоПодмассив, если k больше, чем поворот. Когда k = поворот, мы закончили. "

Скажем, у меня есть список из 10 элементов:

3 8 9 2 4 5 17 10 6, где 5 - это точка. Я знаю, что обычно у меня будет 2 массива

32 4 1 и 8 9 7 10 6

но я не понимаю: «Мы можем решить проблему выбора, разбивая ее, пока элемент поворота не окажется в k-м слоте».

что такое k-й слот?для меня я продолжаю думать, kth = длина массива, так что в этом случае 10. который будет иметь значение 6, которое, очевидно, не самое низкое ... и не правильно.

можеткто-то использует этот образец массива и просто показывает мне, что означает этот алгоритм и как он находит k-й / самый маленький элемент?спасибо

Answer 1

Я думаю, что вы смотрите на решение сложным образом.

Вот как вы можете найти k-й наименьший элемент, используя QuickSort (ну, не совсем быстрая сортировка, я расскажу почему).

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

В этой проблеме вам не нужно этого делать. Все, что вы делаете, это,

1. Выберите случайный элемент поворота.
2. Разделите массив с [Подмассив 1] Pivot [Sub-array2], где Subarray 1 имеет элементы меньше чем pivot, а sub-array2 имеет элементы больше, чем пивот.
3. Проверить размер подмассива1.

   If it is,
        a.Greater than 'k' then your kth element lies in the first sub-array. Go recursively. Start sorting the sub-array1 alone and you can entirely discard the sub-array2 as you can be sure that 'kth' element cannot occur at a position greater than k! Repeat step-1 for the right sub-array
        b.Lesser than 'k' then your kth element lies in the second sub-array. Again do as said above. Repeat step-1 for left subarray.
        c.If the size of sub-array1 is k-1 then your pivot element must be the kth largest element in your array.Bingo! you have your 'kth' largest element in the array

Итак, чтобы решить ваши сомнения,

Здесь вы сортируете не весь массив, а только часть это. (даже это не совсем верно. Вы получите это, если вы полностью понять мое объяснение выше.)

Answer 2

В быстрой сортировке, когда ваша точка поворота равна k, все слева меньше, а справа больше, поэтому нет необходимости продолжать сортировку, если вам нужно только значение kth.