Skip to content

Commit a996b63

Browse files
kdgyunkdgyun
committed
before test
1 parent d22fec7 commit a996b63

1 file changed

Lines changed: 266 additions & 0 deletions

File tree

‎SortingAlgorithm/Java/TimSort/TimSort.java‎

Lines changed: 266 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,17 @@ public void pushRun(int startPoint, int runLen) {
6161
stackSize++;
6262
}
6363

64+
public void mergeForce() {
65+
while(stackSize > 1) {
66+
int pivot = stackSize - 2;
67+
if(pivot > 0 && runLen[pivot - 1] < runLen[pivot + 1]) {
68+
pivot--;
69+
}
70+
merge(pivot);
71+
}
72+
}
73+
74+
6475
public void merge() {
6576
while(stackSize > 1) {
6677

@@ -121,6 +132,79 @@ private void merge(int idx) {
121132
int length1 = runLen[idx];
122133
int start2 = startPointOfRun[idx + 1];
123134
int length2 = runLen[idx + 1];
135+
136+
137+
// idx 와 idx + 1 번째 run을 병합
138+
runLen[idx] = length1 + length2;
139+
140+
/*
141+
* 상위 3개 (A, B, C)에서 A를 기준으로 병합 할 경우
142+
* 앞서 A, B가 병합되므로, C를 당겨온다.
143+
*
144+
* ex)
145+
* stack [[A], [B], [C]]
146+
*
147+
* runLen[idx] = length1 + length2
148+
* stack[[A + B], [B], [C]]
149+
*
150+
* C를 B위치로 당겨온다.
151+
* stack[[A + B], [C], [C]]
152+
*
153+
* 이 때 마지막 [C]는 더이상 참조될 일 없음
154+
*/
155+
156+
if(idx == (stackSize - 3)) {
157+
startPointOfRun[idx + 1] = startPointOfRun[idx + 2];
158+
runLen[idx + 1] = runLen[idx + 2];
159+
}
160+
stackSize--;
161+
162+
163+
/*
164+
165+
gallopRight -> <- gallopLeft
166+
RUN A RUN B
167+
______________________________ ______________________________
168+
[ | | || | | |MAX] [MIN| | | | || | ]
169+
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
170+
|___________| |______________| |___________________| |______|
171+
less than MIN RUN A' RUN B' greater than MAX
172+
173+
|____________________________________|
174+
merge RUN A' and RUN B'
175+
*/
176+
177+
178+
// start2(RUN B의 시작점보다 작으면서 RUN A 에서 merge를 시작할 위치)
179+
int lo = gallopRight(start2, array, start1, length1, 0);
180+
181+
/*
182+
* 만약 RUN A의 길이와 merge를 시작할 지점이 같을 경우
183+
* 이미 정렬되어있는 상태로 정렳 할 필요 없음
184+
*/
185+
if(length1 == lo) {
186+
return;
187+
}
188+
189+
int hi = gallopLeft(array[start1 + length1 - 1], array, start2, length2, length2 - 1);
190+
191+
/*
192+
* 만약 merge를 시작할 지점이 0이라는 것은
193+
* 이미 정렬되어있는 상태로 정렳 할 필요 없음
194+
*/
195+
if(hi == 0) {
196+
return;
197+
}
198+
199+
start1 += lo;
200+
length1 -= lo;
201+
length2 = hi;
202+
if(length1 <= length2) {
203+
mergeLo(start1, length1, start2, length2);
204+
}
205+
else {
206+
mergeHi(start1, length1, start2, length2);
207+
}
124208
}
125209

126210

@@ -226,6 +310,183 @@ private int gallopRight(int key, int[] array, int startPoint, int len, int hint)
226310
}
227311
return hi;
228312
}
313+
314+
/**
315+
* gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다
316+
* 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다.
317+
*
318+
*
319+
* @param key run B의 startPoint key
320+
* @param array 배열
321+
* @param startPoint run A의 startPoint
322+
* @param len run A 의 길이
323+
* @param hint
324+
* @return
325+
*/
326+
private int gallopLeft(int key, int[] array, int startPoint, int len, int hint) {
327+
328+
/*
329+
* lastOffset과 다음 오프셋인 offset 사이를 구하고 이 구간에 대해
330+
* 이분탐색을 통해 최종 오프셋을 반환한다.
331+
*/
332+
int lo = 0;
333+
int hi = 1;
334+
335+
/*
336+
* RUN A의 시작지점 값이 RUN B의 시작지점보다 클 경우
337+
*/
338+
if(key <= array[startPoint + hint]) {
339+
340+
int maxOffset = hint + 1; // 최대 오프셋은 RUN A의 길이다.
341+
342+
// Gallop left until a[b + hint - hi] <= key < array[b + hint - lo]
343+
while(hi < maxOffset && key <= array[startPoint + hint - hi]) {
344+
lo = hi;
345+
hi = (hi << 1) + 1; // 2배씩 건너뜀 탐색
346+
347+
// overflow가 발생시 maxOffset으로 만들어 while문의 break를 건다.
348+
if(hi <= 0) {
349+
hi = maxOffset;
350+
break;
351+
}
352+
}
353+
354+
// 최대로 가질 수 있는 오프셋을 벗어났을 경우 최대 값으로 초기화
355+
if(hi > maxOffset) {
356+
hi = maxOffset;
357+
}
358+
359+
int temp = lo;
360+
lo = hint - hi;
361+
hi = hint - temp;
362+
}
363+
364+
else {
365+
// Gallop right until a[b + hint + lo] <= key < a[b + hint + hi]
366+
int maxOffset = len - hint; // 최대로 가질 수 있는 offset
367+
368+
while(hi < maxOffset && array[startPoint + hint + hi] < key) {
369+
lo = hi;
370+
hi = (hi << 1) + 1;
371+
372+
if(hi <= 0) { // overflow
373+
hi = maxOffset;
374+
break;
375+
}
376+
}
377+
378+
if(hi > maxOffset) {
379+
hi = maxOffset;
380+
}
381+
382+
lo += hint;
383+
hi += hint;
384+
}
385+
386+
lo++;
387+
388+
// binary search
389+
while(lo < hi) {
390+
391+
/*
392+
* 중간 값을 구할 때 (lo + hi) / 2 를 하면
393+
* (lo + hi) 여기서 int overflow가 발생할 수 있다.
394+
*
395+
* 그러므로 hi - lo의 차이값에 2를 나눈 뒤,
396+
* lo을 더하는 방식으로 해준다.
397+
*
398+
* ex) lo = 3, hi = 7
399+
* 3 + ((7 - 3) / 2)
400+
* = 3 + (4 / 2)
401+
* = 3 + 2
402+
* = 5
403+
* ( == ((3 + 7) / 2 = 5) )
404+
*/
405+
int mid = lo + ((hi - lo) >>> 1);
406+
407+
if(key < array[startPoint + mid]) {
408+
hi = mid;
409+
}
410+
else {
411+
lo = mid + 1;
412+
}
413+
}
414+
return hi;
415+
}
416+
417+
418+
// start1, length1, start2, length2
419+
private void mergeLo(int start1, int length1, int start2, int length2) {
420+
421+
// RUN A' 를 담을 임시 복사 배열
422+
int[] temp = new int[length1];
423+
System.arraycopy(array, start1, temp, 0, length1);
424+
425+
int left = start1;
426+
int right = start2;
427+
428+
int tempIdx = 0;
429+
int leftRemain = length1;
430+
int rightRemain = length2;
431+
432+
while(leftRemain != 0 && rightRemain != 0) {
433+
434+
// RUN B' < RUN A' 라면 RUN B' 원소 삽입
435+
if(array[right] < temp[tempIdx]) {
436+
array[left++] = array[right++];
437+
rightRemain--;
438+
}
439+
else {
440+
array[left++] = temp[tempIdx++];
441+
leftRemain--;
442+
}
443+
}
444+
445+
// 왼쪽 부분 리스트가 남아있을 경우
446+
if(leftRemain != 0) {
447+
System.arraycopy(temp, tempIdx, array, left, leftRemain);
448+
}
449+
else {
450+
System.arraycopy(array, right, array, left, rightRemain);
451+
}
452+
}
453+
454+
// start1, length1, start2, length2
455+
private void mergeHi(int start1, int length1, int start2, int length2) {
456+
457+
// RUN B' 를 담을 임시 복사 배열
458+
int[] temp = new int[length2];
459+
System.arraycopy(array, start2, temp, 0, length2);
460+
461+
int left = start1 + length1 - 1;
462+
int right = start2 + length2 - 1;
463+
464+
int tempIdx = length2 - 1;
465+
466+
int leftRemain = length1;
467+
int rightRemain = length2;
468+
469+
while(leftRemain != 0 && rightRemain != 0) {
470+
471+
// RUN A' > RUN B' 라면 RUN A' 원소 삽입 (내림차순이기 때문)
472+
if(array[left] > temp[tempIdx]) {
473+
array[right--] = array[left--];
474+
leftRemain--;
475+
}
476+
else {
477+
array[right--] = temp[tempIdx--];
478+
rightRemain--;
479+
}
480+
}
481+
482+
// 오른쪽 부분 리스트가 남아있을 경우
483+
if(rightRemain != 0) {
484+
System.arraycopy(temp, 0, array, start1, rightRemain);
485+
}
486+
else {
487+
System.arraycopy(array, start1, array, start1, leftRemain);
488+
}
489+
}
229490
}
230491

231492

@@ -291,9 +552,14 @@ public static void sort(int[] a, int lo, int hi) {
291552

292553
// stack에 run의 시작점과 해당 run의 길이를 스택에 push한다.
293554
im.pushRun(lo, incLength);
555+
im.merge();
294556

557+
lo += incLength;
558+
remain -= incLength;
295559
} while(remain > 0);
296560

561+
im.mergeForce();
562+
297563
}
298564

299565
private static void BinarySort(int[] a, int lo, int hi ,int start) {

0 commit comments

Comments
 (0)