🔧소프트웨어 개발반드시
정렬 알고리즘
버블·선택·삽입은 O(n²), 병합·힙은 O(n log n), 퀵은 평균 O(n log n) 최악 O(n²).
버블 정렬은 옆 자리와 비교해 바꾸며 큰 것을 뒤로 보낸다. 한 회전마다 가장 큰 것이 끝에 박힌다.
선택 정렬은 남은 것 중 가장 작은 것을 골라 앞에 놓는다. 삽입 정렬은 이미 정렬된 앞쪽에 끼워 넣는다.
퀵 정렬은 기준(피벗)보다 작은 것과 큰 것으로 나누며 재귀로 돈다. 평균 O(n log n), 최악 O(n²).
병합 정렬은 반으로 쪼갠 뒤 합치며 정렬한다. 어떤 경우에도 O(n log n)이지만 추가 메모리가 든다.
외울 것
O(n²)버블 · 선택 · 삽입
O(n log n)병합 · 힙 · 퀵(평균)
퀵 최악O(n²) — 이미 정렬된 자료에 첫 원소를 피벗으로 잡을 때
시험에는 이렇게
'3회전 후의 상태를 적으시오' 형태가 실기에 나온다. 필기는 시간 복잡도를 바꿔 낸다 — 특히 퀵의 최악이 O(n²)이라는 점.
실기에도 나오는 개념입니다. 실기는 고르는 것이 아니라 적으므로 용어를 글자 그대로 외워 두세요.
확인 문제
이 개념은 실기에도 3문항 나옵니다. 고르는 것과 적는 것은 다르니 실기 탭에서 손으로도 한 번 적어 보세요.