Причина вашего недоразумения по поводу алгоритма медианы медиан состоит в том, что, хотя медиана медиан возвращает приблизительный результат в пределах 20% от фактического медианы, на некоторых этапах алгоритма нам также необходимо вычислить точные медианы,Если вы перепутаете их, вы не получите ожидаемого результата, как показано в вашем примере.
Медиана медиан использует три функции в качестве строительных блоков:
medianOfFive(array, first, last) {
// ...
return median;
}
Эта функция возвращает точную медиану пяти (или менее) элементов из (части) массива.Есть несколько способов закодировать это, например, на основе сортировочной сети или сортировки вставкой.Детали не важны для этого вопроса, но важно отметить, что эта функция возвращает точную медиану, а не приближение.
medianOfMedians(array, first, last) {
// ...
return median;
}
Эта функция возвращает аппроксимацию медианы из (части) массива, который гарантированно будет больше 30% наименьших элементов и меньше 30% наибольших элементов.Мы углубимся в подробности ниже.
select(array, first, last, n) {
// ...
return element;
}
Эта функция возвращает n-й наименьший элемент из (части) массива.Эта функция также возвращает точный результат, а не приближение.
По своей сути, общий алгоритм работает следующим образом:
medianOfMedians(array, first, last) {
call medianOfFive() for every group of five elements
fill an array with these medians
call select() for this array to find the middle element
return this middle element (i.e. the median of medians)
}
Так что здесь ваши вычисления пошли неправильно.После создания массива с медианой пяти, вы снова использовали функцию медиана медиан в этом массиве, которая дает вам приближение медианы (27), но здесь вам нужна фактическая медиана (1038).
Все это звучит довольно просто, но в этом случае усложняется то, что функция select () вызывает medianOfMedians () для получения первой оценки медианы, которую затем использует для вычисления точной медианы, поэтому вы получаетедвусторонняя рекурсия, где две функции вызывают друг друга.Эта рекурсия останавливается, когда medianOfMedians () вызывается для 25 элементов или меньше, потому что тогда есть только 5 медиан, и вместо использования select () для поиска их медианы, он может использовать medianOfFive ().
Причина, по которой метод select () вызывает medianOfMedians (), заключается в том, что он использует разбиение массива для разбиения (части) массива на две части, близких к одинаковому размеру, и для этого требуется хорошее сводное значение.После того, как он разделил массив на две части с элементами, которые меньше и больше, чем стержень, он проверяет, в какой части находится n-й наименьший элемент, и рекурсивно обращается с этой частью.Если размер детали с меньшими значениями равен n-1, стержень является n-м значением, и дальнейшая рекурсия не требуется.
select(array, first, last, n) {
call medianOfMedians() to get approximate median as pivot
partition (the range of) the array into smaller and larger than pivot
if part with smaller elements is size n-1, return pivot
call select() on the part which contains the n-th element
}
Как видите, функция select () рекурсивно (если только не случается, что ось является n-ным элементом), но на все меньших диапазонах массива, поэтому в некоторой точке (например, два элемента) поиск n-го элемента станет тривиальным, и дальнейшее повторение больше не требуется.
Итак, наконец, мы получим более подробно:
medianOfFive(array, first, last) {
// some algorithmic magic ...
return median;
}
medianOfMedians(array, first, last) {
if 5 elements or fewer, call medianOfFive() and return result
call medianOfFive() for every group of five elements
store the results in an array medians[]
if 5 elements or fewer, call medianOfFive() and return result
call select(medians[]) to find the middle element
return the result (i.e. the median of medians)
}
select(array, first, last, n) {
if 2 elements, compare and return n-th element
if 5 elements or fewer, call medianOfFive() to get median as pivot
else call medianOfMedians() to get approximate median as pivot
partition (the range of) the array into smaller and larger than pivot
if part with smaller elements is size n-1, return pivot
if n-th value is in part with larger values, recalculate value of n
call select() on the part which contains the n-th element
}
ПРИМЕР
Входной массив (125 значений, 25 групп по пять):
#1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13 #14 #15 #16 #17 #18 #19 #20 #21 #22 #23 #24 #25
1 4 7 1020 1025 10 13 16 1029 1036 19 22 25 1041 1046 1051 1056 1061 1066 1071 1076 1081 1086 1091 1096
2 5 8 1021 1026 11 14 17 1030 1037 20 23 26 1042 1047 1052 1057 1062 1067 1072 1077 1082 1087 1092 1097
3 6 9 1022 1027 12 15 18 1031 1038 21 24 27 1043 1048 1053 1058 1063 1068 1073 1078 1083 1088 1093 1098
1001 1003 1005 1023 1028 1007 1009 1011 1032 1039 1014 1016 1018 1044 1049 1054 1059 1064 1069 1074 1079 1084 1089 1094 1099
1002 1004 1006 1034 1035 1008 1010 1013 1033 1040 1015 1017 1019 1045 1050 1055 1060 1065 1070 1075 1080 1085 1090 1095 1100
Медианы групп из пяти (25 значений):
3, 6, 9, 1022, 1027, 12, 15, 18, 1031, 1038, 21, 24, 27, 1043,
1048, 1053, 1058, 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098
Группы из пяти человек для приблизительной медианы:
#1 #2 #3 #4 #5
3 12 21 1053 1078
6 15 24 1058 1083
9 18 27 1063 1088
1022 1031 1043 1068 1096
1027 1038 1048 1073 1098
Медианы из пяти для приблизительной медианы:
9, 18, 27, 1063, 1088
Приблизительный средний, как стержень:
1 045 * * 1 046 * медианы пяти секционированных с шарниром 27 (в зависимости от метода):
small: 3, 6, 9, 24, 21, 12, 15, 18
pivot: 27
large: 1031, 1038, 1027, 1022, 1043, 1048, 1053, 1058,
1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098
Чем меньше группа имеет 8 элементов,большая группа из 16 элементов.Мы искали средний 13-й элемент из 25, поэтому теперь мы ищем 13 - 8 - 1 = 4-й элемент из 16:
Группы из пяти:
#1 #2 #3 #4
1031 1048 1073 1098
1038 1053 1078
1027 1058 1083
1022 1063 1088
1043 1068 1093
Медианыиз пяти групп:
1031, 1058, 1083, 1098
Приблизительная медиана как центр:
1058
Диапазон медиан из пяти, разделенных с центром 1058 (зависит от метода):
small: 1031, 1038, 1027, 1022, 1043, 1048, 1053
pivot: 1058
large: 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098
Меньшая группа состоит из 7 элементов.Мы искали 4-й элемент из 16, поэтому теперь мы ищем 4-й элемент из 7:
Группы по пять:
#1 #2
1031 1048
1038 1053
1027
1022
1043
Медианы групп по пять:
1031, 1048
* Тысяча семьдесят-одина * Приблизительная средние, как стержень: * тысяча семьдесят-дв *
1031
* +1074 * Диапазон медиан пяти секционированных с шарниром 1031 (в зависимости от метода):
small: 1022, 1027
pivot: 1031
large: 1038, 1043, 1048, 1053
Меньшая часть имеет 2 элемента, ибольше, имеет 4, поэтому теперь мы ищем 4 - 2 - 1 = 1-й элемент из 4:
Медиана пяти в качестве оси:
1043
Диапазон медиан пяти из разделенных сpivot 1043 (зависит от метода):
small: 1038
pivot: 1043
large: 1048, 1053
Меньшая часть имеет только один элемент, и мы искали первый элемент, поэтому мы можем вернуть маленький элемент 1038.
Каквы увидите, что 1038 является точной медианой исходных 25 медиан пяти, и в исходном массиве 125 есть 62 меньших значения:
1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037
, которое не только помещает его в 30 ~70% диапазон, но означает, что это на самом деле точное медиана.