Search

'책상 위 컴퓨터/Research_report'에 해당되는 글 1건

  1. 2008.05.22 Selection sort & Heap sort & quick sort 정렬 속도 비교

Selection sort & Heap sort & Quick sort  정렬 속도 비교




사용자 삽입 이미지


학교 과제로 나온 ... 시간 복잡도를 비교하는 과제 ...

음 ... quick 정렬이 나름 제일 빠른 줄 알았지만 ( nlogn 이라고 하지만 ... ) 이런 속도 차이가 ...

selection, insert, bubble 등 이런 정렬들은 ... 일정 자릿수 이상의 값을 입력 하였을 시에 ...

미칠듯한 정렬 시간이 나왔다.

첨부 된 그림은 실제로 적용 해 본 후 나온 결과 화면 ...


※ 정렬 되지 않은 자료일 경우 정렬하는데 얼마 걸리지 않는데, 정렬 된 자료 일 경우 ... 생각보다 시간이 걸렸다. 여러 책에 따르면 Quick sort는 정렬된 자료일 경우 정렬하는데 걸리는 시간이 더 걸린다고 하는데 ... 으흠 ... 쏘스에 따라 달라짐은 이를 어떡하랴 ?

화면을 클릭하면 크게 보일까? 흠흠 ...

( 테스트한 자료는 ... 50,000 에서부터 시작하여 2,000,000 까지의 데이터를 무작위로 생성하여 테스트 하였다. JAVA로 작업 하였음 )


- PS -
 이론상 Quick sort의 경우 정렬된 경우는 위의 결과처럼 나오지 않는다. 즉 복잡도가 증가해서 Selection sort의 경우처럼 느린 경우를 볼 수 있다.
 즉 작성하는 소스에 따라서 결과값은 달리 나온다.