Skip to content

Commit d22fec7

Browse files
kdgyunkdgyun
committed
add gallopMode(right)
1 parent 0e9f0c1 commit d22fec7

1 file changed

Lines changed: 193 additions & 6 deletions

File tree

‎SortingAlgorithm/Java/TimSort/TimSort.java‎

Lines changed: 193 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ public class TimSort {
2020
private static class IntMerge {
2121

2222
private int[] array;
23-
private final int[] runBase;
23+
private final int[] startPointOfRun;
2424
private final int[] runLen;
2525
private int stackSize = 0; // run 스택의 원소 개수를 가리킬 변수
2626

@@ -51,17 +51,187 @@ public IntMerge(int[] a) {
5151
int stackLen = (len < 120 ? 5 :
5252
len < 1542 ? 10 :
5353
len < 119151 ? 19 : 35);
54-
runBase = new int[stackLen];
54+
startPointOfRun = new int[stackLen];
5555
runLen = new int[stackLen];
5656
}
5757

58-
public void pushRun(int runBase, int runLen) {
59-
this.runBase[stackSize] = runBase;
58+
public void pushRun(int startPoint, int runLen) {
59+
this.startPointOfRun[stackSize] = startPoint;
6060
this.runLen[stackSize] = runLen;
6161
stackSize++;
6262
}
63+
64+
public void merge() {
65+
while(stackSize > 1) {
66+
67+
/*
68+
* stack의 상위 3개 원소를 비교하며
69+
* 병합하기 위한 상위 3개 원소의 중간 피벗
70+
*
71+
*/
72+
int pivot = stackSize - 2;
73+
74+
/*
75+
* 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
76+
* 2. runLen[i - 2] > runLen[i - 1]
77+
*
78+
* runLen[n-1] = A, runLen[n] = B, runLen[n+1] = C를 상위 세 요소로 합니다.
79+
* 운영상 루프는 다음과 같은 경우에 기초한다.
80+
* 1. A <= B + C 및 A < C일 경우 A 과 B 병합. 즉, n-1 과 n 병합
81+
* 2. A <= B + C 및 A >= C일 경우, B와 C 병합. 즉, n 과 n+1 병합
82+
* 3. A > B + C 및 B <= C일 경우, B와 C 병합. 즉, n 과 n+1 병합
83+
* 4. A > B + C 및 B > C일 경우 루프 종료
84+
*/
85+
86+
// stack 요소가 3개 이상일 경우에만 3개를 비교할 수 있음
87+
if(stackSize > 2) {
88+
// A <= B + C
89+
if(runLen[pivot - 1] <= runLen[pivot] + runLen[pivot + 1]) {
90+
// A < C
91+
if(runLen[pivot - 1] < runLen[pivot + 1]) {
92+
// A 와 B 병합 (pivot-1 and pivot merged)
93+
//merge(n - 1)
94+
}
95+
else { // A >= C
96+
//merge(n)
97+
}
98+
}
99+
// A > B + C && B <= C
100+
else if(runLen[pivot] <= runLen[pivot + 1]) {
101+
//merge(n)
102+
}
103+
else {
104+
break;
105+
}
106+
}
107+
// 유일하게 두 개만 남은 경우
108+
else if(stackSize > 1) {
109+
// merge(n)
110+
}
111+
}
112+
}
113+
114+
/**
115+
* run[idx] 와 run[idx + 1]이 병합 됨
116+
* @param idx 병합되는 두 서브리스트(run) 중 낮은 인덱스
117+
*/
118+
private void merge(int idx) {
119+
120+
int start1 = startPointOfRun[idx];
121+
int length1 = runLen[idx];
122+
int start2 = startPointOfRun[idx + 1];
123+
int length2 = runLen[idx + 1];
124+
}
125+
126+
127+
/**
128+
* gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다
129+
* 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다.
130+
*
131+
*
132+
* @param key run B의 startPoint key
133+
* @param array 배열
134+
* @param startPoint run A의 startPoint
135+
* @param len run A 의 길이
136+
* @param hint
137+
* @return
138+
*/
139+
private int gallopRight(int key, int[] array, int startPoint, int len, int hint) {
140+
141+
/*
142+
* lastOffset과 다음 오프셋인 offset 사이를 구하고 이 구간에 대해
143+
* 이분탐색을 통해 최종 오프셋을 반환한다.
144+
*/
145+
int lo = 0;
146+
int hi = 1;
147+
148+
/*
149+
* RUN A의 시작지점 값이 RUN B의 시작지점보다 클 경우
150+
*/
151+
if(key < array[startPoint + hint]) {
152+
153+
int maxOffset = hint + 1; // 최대 오프셋은 RUN A의 길이다.
154+
155+
// Gallop left until a[b + hint - hi] <= key < array[b + hint - lo]
156+
while(hi < maxOffset && key < array[startPoint + hint - hi]) {
157+
lo = hi;
158+
hi = (hi << 1) + 1; // 2배씩 건너뜀 탐색
159+
160+
// overflow가 발생시 maxOffset으로 만들어 while문의 break를 건다.
161+
if(hi <= 0) {
162+
hi = maxOffset;
163+
break;
164+
}
165+
}
166+
167+
// 최대로 가질 수 있는 오프셋을 벗어났을 경우 최대 값으로 초기화
168+
if(hi > maxOffset) {
169+
hi = maxOffset;
170+
}
171+
172+
int temp = lo;
173+
lo = hint - hi;
174+
hi = hint - temp;
175+
}
176+
177+
else {
178+
// Gallop right until a[b + hint + lo] <= key < a[b + hint + hi]
179+
int maxOffset = len - hint; // 최대로 가질 수 있는 offset
180+
181+
while(hi < maxOffset && array[startPoint + hint + hi] <= key) {
182+
lo = hi;
183+
hi = (hi << 1) + 1;
184+
185+
if(hi <= 0) { // overflow
186+
hi = maxOffset;
187+
break;
188+
}
189+
}
190+
191+
if(hi > maxOffset) {
192+
hi = maxOffset;
193+
}
194+
195+
lo += hint;
196+
hi += hint;
197+
}
198+
199+
lo++;
200+
201+
// binary search
202+
while(lo < hi) {
203+
204+
/*
205+
* 중간 값을 구할 때 (lo + hi) / 2 를 하면
206+
* (lo + hi) 여기서 int overflow가 발생할 수 있다.
207+
*
208+
* 그러므로 hi - lo의 차이값에 2를 나눈 뒤,
209+
* lo을 더하는 방식으로 해준다.
210+
*
211+
* ex) lo = 3, hi = 7
212+
* 3 + ((7 - 3) / 2)
213+
* = 3 + (4 / 2)
214+
* = 3 + 2
215+
* = 5
216+
* ( == ((3 + 7) / 2 = 5) )
217+
*/
218+
int mid = lo + ((hi - lo) >>> 1);
219+
220+
if(key < array[startPoint + mid]) {
221+
hi = mid;
222+
}
223+
else {
224+
lo = mid + 1;
225+
}
226+
}
227+
return hi;
228+
}
63229
}
64230

231+
232+
233+
234+
65235
public static void sort(int[] a) {
66236
sort(a, 0, a.length);
67237
}
@@ -100,11 +270,28 @@ public static void sort(int[] a, int lo, int hi) {
100270
* minRun = 18 이라고 가정
101271
* [0, 2, 3, 8, 16, 4, 7, 26, 13, ..., 21]
102272
* incLength = 5
103-
*
273+
* -> (lo + incLength) 이 이진삽입정렬 수행 시작점이 됨
104274
*/
105275
if(incLength < minRun) {
106276

277+
// 최소 run 크기가 남은 원소 개수보다 작을 수 있으므로 이를 처리해준다.
278+
int endPoint = remain < minRun ? remain : minRun;
279+
280+
/*
281+
* BinarySort(array, lo, hi, start);
282+
* index[lo] <= index < index[endPoint] 구간을 삽입 정렬을 하되,
283+
* index[lo + incLength] 부터 삽입정렬을 시작함.
284+
* (이전 인덱스는 이미 오름차순 상태임)
285+
*/
286+
BinarySort(a, lo, lo + endPoint, lo + incLength);
287+
288+
// 이진 삽입 정렬이 수행되었기에 증가하는 길이는 endPoint가 된다.
289+
incLength = endPoint;
107290
}
291+
292+
// stack에 run의 시작점과 해당 run의 길이를 스택에 push한다.
293+
im.pushRun(lo, incLength);
294+
108295
} while(remain > 0);
109296

110297
}
@@ -180,7 +367,7 @@ private static void reversing(int[] a, int lo, int hi) {
180367

181368
/*
182369
* arrayLength / runSize 이 2의 제곱근에 가까울수록 좋음(병합정렬 특성)
183-
* 즉, 나오는 수는 THRESHOLD <= runSize <+ THRESHOLD 사잇값이 됨.
370+
* 즉, 나오는 수는 THRESHOLD <= runSize <= THRESHOLD 사잇값이 됨.
184371
*
185372
* 이를 구하기 위해 runSize을 THRESHOLD(32) 보다 작을 떄 까지 2씩 매 번 나눠가며
186373
* runSize 로 나눴을 때 근접하도록 한다.

0 commit comments

Comments
 (0)