하도 손디버깅을 많이해서 그런가 코드를 그냥 외워버려서 쭉 치긴 했는데 사실 블로그 배껴서 작성한겁니다 ㅠㅠ <div><br></div> <div>아직도 잘 이해가 안가는 코드입니다.(재귀함수 연상이 어렵네요... 그래서 재귀를 안쓰고 구현해보려고 했는데 실패했습니다 ㅠㅠㅠ)</div> <div><br></div> <div>거기다 이유는 모르겠지만 제가 작성한 삽입정렬보다 느립니다. 원래 빨라야 할것 같은데....</div> <div><br></div> <div>머릿속으로 그려낸걸 코드로 옮기기란 정말 어렵습니다.</div> <div><br></div> <div><div> <span style="white-space:pre;"> </span>public int[] mergeSort(int[] array) {</div> <div><span style="white-space:pre;"> </span>long startTime = System.nanoTime();</div> <div><span style="white-space:pre;"> </span>array = Merge_Sort(array, 0, array.length - 1);</div> <div><span style="white-space:pre;"> </span>long endTime = System.nanoTime();</div> <div><span style="white-space:pre;"> </span>System.out.println("MergeSort TIME : " + (endTime - startTime) / 1000.0 + "(ms)");</div> <div><span style="white-space:pre;"> </span>return array;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>private int[] Merge_Sort(int[] array, int start, int end) {</div> <div><span style="white-space:pre;"> </span>if(start < end) {</div> <div><span style="white-space:pre;"> </span>int middle = (start + end)/2;</div> <div><span style="white-space:pre;"> </span>Merge_Sort(array, start, middle);</div> <div><span style="white-space:pre;"> </span>Merge_Sort(array, middle + 1, end);</div> <div><span style="white-space:pre;"> </span>merge(array, start, middle, end);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>return array;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>private void merge(int[] array, int start, int middle, int end) {</div> <div><span style="white-space:pre;"> </span>int leftIndex = start;</div> <div><span style="white-space:pre;"> </span>int rightIndex = middle+1;</div> <div><span style="white-space:pre;"> </span>int tempIndex = start;</div> <div><span style="white-space:pre;"> </span>int temp[] = new int[array.length];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>while(leftIndex <= middle && rightIndex <= end) {</div> <div><span style="white-space:pre;"> </span>if(array[leftIndex] < array[rightIndex]) {</div> <div><span style="white-space:pre;"> </span>temp[tempIndex++] = array[leftIndex++];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>}else {</div> <div><span style="white-space:pre;"> </span>temp[tempIndex++] = array[rightIndex++];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>while(leftIndex <= middle)</div> <div><span style="white-space:pre;"> </span>temp[tempIndex++] = array[leftIndex++];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>while(rightIndex <= end)</div> <div><span style="white-space:pre;"> </span>temp[tempIndex++] = array[rightIndex++];</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>for(int index = start; index < tempIndex; index++)</div> <div><span style="white-space:pre;"> </span>array[index] = temp[index];</div> <div><span style="white-space:pre;"> </span>}</div></div> <div><br></div> <div><br></div> <div><<100개 데이터 정렬 결과(시간)>></div> <div>InsertionSort TIME : 56.19(ms)</div> <div>MergeSort TIME : 65.555(ms)</div> <div><br></div> <div>삽입정렬보다 엄청 느리네요...</div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.