O(n²) sorting

Sort
Algorithm T(n) S(n) Data Limit
Bubble O(n^2) n X
Selection O(n^2) n X
Merge O(nlgn) 2n X
Quick O(nlgn) n X
Heap O(nlgn) 2n X
Counting O(n+k) n+k O
Raidx O(d(n+k)) n+k O
  • n : 데이터 개수, k : 데이터 범위, d : 데이터의 자릿수
  • T(n) : 시간 복잡도, S(n) : 공간 복잡도
  • 위의 표만 보고 퀵이 제일 좋고, counting이 radix보다 좋다고 판단하면 안된다. 다상황에 따라 유리한 경우가 다름

 

버블 정렬

인접한 두 항을 비교하여 swap 하는 방식

한번 돌 때 마다 최대값이 뒤로 감

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

선택 정렬

한번 돌 때 마다 최솟값을 찾아 가장 앞에 넣어주는 방법을 N번 반복

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

 

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