cs50 4강 정렬 알고리즘

버블 정렬

앞에서 살펴보았듯, 자료를 찾을 때에는 정렬의 유무에 따라 소요 시간이 크게 차이날 수 있다.
정렬 알고리즘엔 크게 버블 정렬과 선택 정렬이 있으며, 우리는 비교적 간단한 버블 정렬에 대해 먼저 알아보도록 하자.

정의

집합 내의 이웃 요소들을 교환하여 정렬한다.
그 이후 마지막 인덱스까지 갔다면 두번째 요소와 비교를 하는 방식으로 계속 반복해서 진행한다
이렇게 텍스트로 보면 뭔 소리일까 싶은데 영상을 보면 이 소리였구나싶게 된다.

장단점

만약 크기가 작은 배열을 정렬하는 상황이라면, 직관적인 코드를 짜기 좋다.
또한 데이터 하나하나를 비교하는 알고리즘의 특성상 정확도나 정밀도가 높을 것이다.
하지만, 시간 복잡도가 O($n^2)이므로 크기가 큰 배열이나 벡터를 정리하는 데에는 어마어마한 시간이 소요될 수도 있다.

선택 정렬

선택 정렬은 말 그대로 최소 혹은 최대 요소를 선택하여 정렬해나가는 알고리즘이다.

장단점

원칙적으로는 선택 정렬과 버블 정렬이 차지하는 시간 복잡도는 일치하다.
그러나, 최소값 혹은 최대값에 대한 정보가 있는 상황이라면 이미 기준점이 확보되어있기 때문에 버블 정렬보다 훨씬 빠른 정렬이 가능하다.
대신 for문이 두개 필요하다는 점(바깥 루프: 순차적 방문, 안쪽 루프: 기준점 찾기)에서 코드가 복잡해지기 쉬우므로 크기가 작은 배열이라면 버블 정렬을 쓰는 것이 좋을 수 있다.

stl 정렬

c++를 기준으로 sort함수는 퀵 정렬을 사용하여 비교하는 방식이다.
그래서 위의 설명한 일반적인 정렬과 달리 최악의 경우 소요되는 시간이 O(n log n) 밖에 되지 않기 때문에 상당히 빠른 편이다.

정렬 알고리즘 별 소요시간

실행시간의 상한선

• O(n^2): 선택 정렬, 버블 정렬
  
• O(n log n)
  
• O(n): 선형 검색
  
• O(log n): 이진 검색
  
• O(1)

실행시간의 하한선

• Ω(n^2): 선택 정렬
  
• Ω(n log n)
  
• Ω(n): 버블 정렬
  
• Ω(log n)
  
• Ω(1): 선형 검색, 이진 검색
  

왜 하한선과 상한선이 다를까

여기 보면 몇 개의 알고리즘은 상한선과 하한선이 다른 것을 볼 수 있다.
이는 선형 검색이나 이진 검색의 경우 운이 좋으면 바로내가 원하는 값을 찾을 수 있는 가능성이 존재하기 때문이다.
그에 선택 정렬은 필연적으로 배열의 크기 만큼은 탐색을 끝마쳐야만 한다.
또한 버블 정렬의 경우 이미 정렬된 경우라면, 인접한 두 요소를 한번씩만 비교해도 정렬이 완료되기 때문에 운이 좋다면 선택 정렬보다 빠르게 돌아갈 수도 있는 것이다.