Quick Sort

http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/Database/algorithm/Quick_Sort

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

  • 최악일 때 n^2, 최선 nlogn, 그러나 컴퓨터 아키텍처에서 효율적으로 작동하기 때문에 오히려 다른 nlogn 정렬보다 빠름
  • 피봇의 위치가 퀵 정렬의 성능을 좌우

 

과정

  1. 리스트 안에 있는 한 요소 (피벗)을 선택
  2. 피벗을 기준으로 피벗보다 작은 요소는 피벗 왼쪽, 큰 요소는 피벗 오른쪽으로 옮김
  3. 피벗을 제외한 왼쪽 리스트와 오르쪽 리스트를 다시 정렬
    • 분할된 부분 리스트에 대하여 순환 호출하여 정렬 반복
    • 부분 리스트에서도 다시 피벗 정하고 피벗 기준으로 2개의 부분 리스트로 나누는 과정 반복
  4. 부분 리스트들이 더이상 분할 불가능 할 때까지 반복
    • 리스트의 크기가 0이나 1이 될 때 까지

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat