|
| 1 | +packagecom.thealgorithms.searches; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +/** |
| 6 | + * An implementation of the Quickselect algorithm as described |
| 7 | + * <a href="https://en.wikipedia.org/wiki/Median_of_medians">here</a>. |
| 8 | + */ |
| 9 | +publicfinalclassQuickSelect { |
| 10 | + |
| 11 | +/** |
| 12 | + * Selects the {@code n}-th largest element of {@code list}, i.e. the element that would |
| 13 | + * be at index n if the list was sorted. |
| 14 | + * <p> |
| 15 | + * Calling this function might change the order of elements in {@code list}. |
| 16 | + * |
| 17 | + * @param list the list of elements |
| 18 | + * @param n the index |
| 19 | + * @param <T> the type of list elements |
| 20 | + * @return the n-th largest element in the list |
| 21 | + * @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to |
| 22 | + * the number of elements in the list |
| 23 | + * @throws IllegalArgumentException if the list is empty |
| 24 | + * @throws NullPointerException if {@code list} is null |
| 25 | + */ |
| 26 | +publicstatic <TextendsComparable<T>>Tselect(List<T>list,intn) { |
| 27 | +Objects.requireNonNull(list,"The list of elements must not be null."); |
| 28 | + |
| 29 | +if (list.size() ==0) { |
| 30 | +Stringmsg ="The list of elements must not be empty."; |
| 31 | +thrownewIllegalArgumentException(msg); |
| 32 | + } |
| 33 | + |
| 34 | +if (n <0) { |
| 35 | +Stringmsg ="The index must not be negative."; |
| 36 | +thrownewIndexOutOfBoundsException(msg); |
| 37 | + } |
| 38 | + |
| 39 | +if (n >=list.size()) { |
| 40 | +Stringmsg ="The index must be less than the number of elements."; |
| 41 | +thrownewIndexOutOfBoundsException(msg); |
| 42 | + } |
| 43 | + |
| 44 | +intindex =selectIndex(list,n); |
| 45 | +returnlist.get(index); |
| 46 | + } |
| 47 | + |
| 48 | +privatestatic <TextendsComparable<T>>intselectIndex(List<T>list,intn) { |
| 49 | +returnselectIndex(list,0,list.size() -1,n); |
| 50 | + } |
| 51 | + |
| 52 | +privatestatic <TextendsComparable<T>>intselectIndex( |
| 53 | +List<T>list, |
| 54 | +intleft, |
| 55 | +intright, |
| 56 | +intn |
| 57 | + ) { |
| 58 | +while (true) { |
| 59 | +if (left ==right) |
| 60 | +returnleft; |
| 61 | +intpivotIndex =pivot(list,left,right); |
| 62 | +pivotIndex =partition(list,left,right,pivotIndex,n); |
| 63 | +if (n ==pivotIndex) { |
| 64 | +returnn; |
| 65 | + }elseif (n <pivotIndex) { |
| 66 | +right =pivotIndex -1; |
| 67 | + }else { |
| 68 | +left =pivotIndex +1; |
| 69 | + } |
| 70 | + } |
| 71 | + } |
| 72 | + |
| 73 | +privatestatic <TextendsComparable<T>>intpartition( |
| 74 | +List<T>list, |
| 75 | +intleft, |
| 76 | +intright, |
| 77 | +intpivotIndex, |
| 78 | +intn |
| 79 | + ) { |
| 80 | +TpivotValue =list.get(pivotIndex); |
| 81 | +Collections.swap(list,pivotIndex,right); |
| 82 | +intstoreIndex =left; |
| 83 | + |
| 84 | +for (inti =left;i <right;i++) { |
| 85 | +if (list.get(i).compareTo(pivotValue) <0) { |
| 86 | +Collections.swap(list,storeIndex,i); |
| 87 | +storeIndex++; |
| 88 | + } |
| 89 | + } |
| 90 | + |
| 91 | +intstoreIndexEq =storeIndex; |
| 92 | + |
| 93 | +for (inti =storeIndex;i <right;i++) { |
| 94 | +if (list.get(i).compareTo(pivotValue) ==0) { |
| 95 | +Collections.swap(list,storeIndexEq,i); |
| 96 | +storeIndexEq++; |
| 97 | + } |
| 98 | + } |
| 99 | + |
| 100 | +Collections.swap(list,right,storeIndexEq); |
| 101 | + |
| 102 | +return (n <storeIndex) |
| 103 | + ?storeIndex |
| 104 | + :Math.min(n,storeIndexEq); |
| 105 | + } |
| 106 | + |
| 107 | +privatestatic <TextendsComparable<T>>intpivot( |
| 108 | +List<T>list, |
| 109 | +intleft, |
| 110 | +intright |
| 111 | + ) { |
| 112 | +if (right -left <5) { |
| 113 | +returnpartition5(list,left,right); |
| 114 | + } |
| 115 | + |
| 116 | +for (inti =left;i <right;i +=5) { |
| 117 | +intsubRight =i +4; |
| 118 | +if (subRight >right) { |
| 119 | +subRight =right; |
| 120 | + } |
| 121 | +intmedian5 =partition5(list,i,subRight); |
| 122 | +intrightIndex =left + (i -left) /5; |
| 123 | +Collections.swap(list,median5,rightIndex); |
| 124 | + } |
| 125 | + |
| 126 | +intmid = (right -left) /10 +left +1; |
| 127 | +intrightIndex =left + (right -left) /5; |
| 128 | +returnselectIndex(list,left,rightIndex,mid); |
| 129 | + } |
| 130 | + |
| 131 | +privatestatic <TextendsComparable<T>>intpartition5( |
| 132 | +List<T>list, |
| 133 | +intleft, |
| 134 | +intright |
| 135 | + ) { |
| 136 | +List<T>ts =list.subList(left,right); |
| 137 | +ts.sort(Comparator.naturalOrder()); |
| 138 | +return (left +right) >>>1; |
| 139 | + } |
| 140 | +} |
