<div><br></div> <div>정말 신기하게도 합병정렬 보단 이해하기가 쉬웠습니다.</div> <div><br></div> <div>뭔가 왼쪽, 오른쪽 따로 움직이는게 확실히 상상된다는 느낌이랄까 머리속에 그림도 그려지고</div> <div><br></div> <div>이거 역시 재귀를 쓰지않고 만들어보려 했는데 잘 안되네요. ㅠㅠ</div> <div><br></div> <div>재귀를 쓰지 않음으로써 오는 손해가 너무 큰듯하고 만들면 계속 스파게티화 되버려서....</div> <div><br></div> <div>시간은 합병정렬 보다 빠르긴 한데 때때로 삽입정렬보다 느릴때가 있어서 당황스럽습니다.</div> <div><br></div> <div>이론상으로는 합병정렬과 퀵정렬의 정렬시간이 거의 비슷해야 할텐데 말이죠.</div> <div><br></div> <div><br></div> <div><span style="white-space:pre;"> </span>public  int[] quickSort(int[] array) {</div> <div><span style="white-space:pre;"> </span>long startTime = System.nanoTime();</div> <div><span style="white-space:pre;"> </span>Quick_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("QuickSort TIME : " + (endTime - startTime) / 1000.0 + "(ms)");</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><br></div> <div><span style="white-space:pre;"> </span>private  int[] Quick_Sort(int[] array, int start, int end) {</div> <div><span style="white-space:pre;"> </span>int part = partition(array, start, end);</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(start < part - 1) {</div> <div><span style="white-space:pre;"> </span>Quick_Sort(array, start, part - 1);</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(part < end) {</div> <div><span style="white-space:pre;"> </span>Quick_Sort(array, part, 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 int partition(int[]array, int start, int end) {</div> <div><span style="white-space:pre;"> </span>int pivot = array[(start + end) / 2];</div> <div><span style="white-space:pre;"> </span>int temp;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>while(start <= end) {</div> <div><span style="white-space:pre;"> </span>while(array[start] < pivot) start++;</div> <div><span style="white-space:pre;"> </span>while(pivot < array[end]) end--;</div> <div><span style="white-space:pre;"> </span>if(start <= end) {</div> <div><span style="white-space:pre;"> </span>temp = array[start];</div> <div><span style="white-space:pre;"> </span>array[start] = array[end];</div> <div><span style="white-space:pre;"> </span>array[end] = temp;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>start++; 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></div> <div><span style="white-space:pre;"> </span>return start;</div> <div><span style="white-space:pre;"> </span>}</div>