корректность алгоритма быстрой статистики малого порядка для массива нечетной длины

Задача 9-3 учебника Введение в алгоритмы (CLRS) описывает быстрый Алгоритм O (n) для нахождения статистики k-го порядка (k-й элемент в массиве при сортировке) массива длины n для частного случая, когда k намного меньше, чем n. Я не уверен в правильности этого алгоритма, когда n нечетно, и хочу найти способ доказать его правильность.

Основная идея заключается в том, что сначала мы разделяем массив на две половины: первую с элементами floor(n/2), а вторую — с элементами ceil(n/2). Затем мы «сопоставляем» каждый элемент в первой половине с соответствующим элементом во второй половине. Когда n нечетно, остается оставшийся непарный элемент.

Для каждой пары партнеров мы убеждаемся, что левый партнер >= правый партнер, меняем их местами, если нет. Затем рекурсивно найдите статистику k-го порядка второй половины, отражающую любые свопы, сделанные во второй половине, с соответствующими свопами в первой половине. После этого статистика k-го порядка всего массива должна быть либо в первых k элементах первой половины, либо в первых k элементах второй половины.

Меня смущает случай, когда длина массива n нечетна, а во второй половине есть одинокий элемент, у которого нет партнера. Поскольку рекурсия выполняется на второй половине, состоящей из последних ceil(n/2) элементов массива, включая единственный последний элемент без партнера, и мы должны отразить все обмены, сделанные во второй половине, обменами, сделанными в соответствующем партнеров в первой половине, непонятно, что делать, когда в одном из обменов задействован финальный элемент, так как у него нет партнера.

Учебник, кажется, не уделяет особого внимания этому вопросу, поэтому я предполагаю, что когда обмен включает в себя последний элемент, то просто не делайте никаких зеркальных движений партнера в первой половине вообще. В результате последний элемент просто «крадет» партнера того, с кем его поменяли местами. Однако в этом случае есть ли простой способ убедиться, что алгоритм по-прежнему верен? Что если, когда последний элемент крадет чьего-то партнера, этот партнер на самом деле является статистикой k-го порядка и позже перемещается в недоступное место? Механика рекурсии и разбиения, включающая выборку по порядку статистики, для меня достаточно непрозрачна, поэтому я не могу с уверенностью исключить этот сценарий.


arrays sorting median algorithm median-of-medians
person xdavidliu    schedule 15.12.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я не думаю, что ваше описание алгоритма является полностью точным (но тогда объяснение, на которое вы ссылаетесь, далеко не ясно). Насколько я понимаю, причина корректности алгоритма для массива нечетной длины заключается в следующем:

Давайте сначала рассмотрим несколько примеров массивов четной длины с n = 10 и k = 3 (т.е. мы ищем третий наименьший элемент, равный 2):

a.  5 2 7 6 1 9 3 8 4 0  
b.  5 1 7 6 2 9 3 8 4 0  
c.  5 0 7 6 2 9 3 8 4 1  
d.  5 0 7 6 2 9 3 8 1 4

Если мы разделим массивы на две части, мы получим:

a.  5 2 7 6 1    9 3 8 4 0  
b.  5 1 7 6 2    9 3 8 4 0  
c.  5 0 7 6 2    9 3 8 4 1  
d.  5 0 7 6 2    9 3 8 1 4

и эти пары:

a.  (5,9) (2,3) (7,8) (6,4) (1,0)  <- 0 coupled with 1
b.  (5,9) (1,3) (7,8) (6,4) (2,0)  <- 0 coupled with 2
c.  (5,9) (0,3) (7,8) (6,4) (2,1)  <- 1 coupled with 2
d.  (5,9) (0,3) (7,8) (6,1) (2,4)  <- 0, 1 and 2 not coupled with each other

После сравнения и перестановки пар так, чтобы их наименьший элемент находился в первой группе, получаем:

a.  5 2 7 4 0    9 3 8 6 1  
b.  5 1 7 4 0    9 3 8 6 2  
c.  5 0 7 4 1    9 3 8 6 2  
d.  5 0 7 1 2    9 3 8 6 4

Вы увидите, что наименьший элемент 0 всегда будет в первой группе. Второй наименьший элемент 1 будет либо в первой группе, либо во второй группе, если он был связан с наименьшим элементом 0. Третий наименьший элемент 2 будет либо в первой группе, либо во второй группе, если он был связан либо с наименьшим элементом 0, либо со вторым по величине элементом 1.

Таким образом, наименьший элемент находится в первой группе, а второй и третий наименьшие элементы могут быть в любой группе. Это означает, что третий по величине элемент является либо одним из 3-х наименьших элементов в первой группе, либо одним из 2-х (!) наименьших элементов во второй группе.

a.  5 2 7 4 0    9 3 8 6 1  ->  0 2 4 + 1 3  
b.  5 1 7 4 0    9 3 8 6 2  ->  0 1 4 + 2 3  
c.  5 0 7 4 1    9 3 8 6 2  ->  0 1 4 + 2 3  
d.  5 0 7 1 2    9 3 8 6 4  ->  0 1 2 + 3 4

Итак, если мы говорим, что k-й наименьший элемент всего массива теперь является одним из k-м наименьшим элементом в любой из групп, во второй группе есть доступное место, и поэтому в нечетной- length, мы бы добавили несвязанный элемент во вторую группу. Независимо от того, является ли несвязанный элемент искомым элементом, он обязательно будет одним из k-х наименьших элементов в любой из групп.

На самом деле правильнее сказать, что k-й наименьший элемент является либо одним из k наименьших элементов в первой группе, либо одним из k/2+1 наименьших элементов во второй группе. На самом деле я не уверен, что алгоритм оптимален или даже правилен. Происходит множество повторяющихся сравнений и обменов, и идея отслеживать пары и менять местами элементы в одной группе, когда меняются местами соответствующие им элементы в другой группе, кажется бессмысленной.

person m69 ''snarky and unwelcoming''    schedule 15.12.2017
comment
сокращение его до k/2+1 наименьших элементов во второй группе кажется ключевым и позволяет нам, по крайней мере, поместить несвязанный элемент с ними, не вовлекая его сначала в зеркальное отображение, и я думаю, что это намного лучший способ . (Я взял свое описание непосредственно из официального руководства по решению из более старого издания книги, и, кажется, ссылка в моем исходном сообщении также ссылалась на это. Официальное решение помещает меньшие элементы в правую половину массива, а не в левую половина, так что когда рекурсия будет выполнена, в правой половине она будет включать непартнерский элемент) - person xdavidliu; 15.12.2017