💬 SOFTWARE 003

021 선택 정렬 & 퀵 정렬

---

선택 정렬 [$O(N^2)$]

• 주어진 항목들이 정렬되어 있지 않으면 이진 검색을 할 수 없음

• 정렬(sorting)은 항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 해줌

• 선택 정렬(Selection Sort)은 아직 정렬되지 않은 항목 중에서 다음 항목을 계속 선택함

• 알고리즘을 연구하는 컴퓨터과학자들은 비관론자라서 지름길 없이 모든 작업을 수행해야 하는 최악의 경우를 가정함

• [항목을 훑어보는 횟수] = [N + N-1 + N-2 + ... + 1] = [N * (N+1) / 2]

• 일의 양은 $N^2$, 계수를 제외해서 최고차항인 2차(quadratic)인 증가율을 보임

---

퀵 정렬 [$O(NlogN)$]

• 퀵 정렬(Quick Sort)은 분할 정복의 훌륭한 사례

• 항상 데이터를 정렬하지만 그룹을 나눌 때마다 거의 같은 크기의 덩어리로 나눠야만 효율적 [$1/2$]

• $NlogN$의 연산이 필요

• 선형보다는 효율이 낮지만 심하지는 않고, N이 조금이라도 크면 2차($N^2$)보다 훨씬 효율적

• 선택 정렬과 퀵 정렬 시간 비교

개수(N)	선택 정렬 시간(초)	퀵 정렬 시간(초)
1000	0.047	-
1,0000	4.15	0.025
10,0000	771	0.23
100,0000	-	3.07
1000,0000	-	39.9

• 선택정렬에서 10,0000개의 데이터를 처리하는 데 걸리는 시간이 1,0000개의 데이터를 처리하는 시간에 비해 100배 클 것으로 예상했지만 실제로는 거의 200배임

  • 캐싱의 영향 일수도

  • 데이터가 캐시에 모두 들어가지 못하면서 정렬이 느려진 것

  • 계산 과정을 이론적으로 추상화한 것과 프로그램임 실제로 계산을 수행하는 상황 간의 차이를 보여줌

---

📌시간 복잡도 그래프 참고 블로그