[데브코스 6일차] 정렬 알고리즘

🤔 생각해볼 것

1. 선택 정렬을 구현해보세요.

2. 버블 정렬을 구현해보세요.

3. 삽입 정렬을 구현해보세요.

4. 퀵 정렬을 구현해보세요.

5. 병합 정렬을 구현해보세요.

6. 힙 정렬을 구현해보세요.

7. 계수 정렬을 구현해보세요.

 

[1] 왜 정렬 알고리즘을 배우는가?

대부분 언어에서는 빌트인으로 정렬 메서드를 제공해준다. (대부분 팀소트 정렬 알고리즘을 사용한다)

온라인 코딩테스트에서는 빌트인 정렬만 잘 사용해도 좋지만, 간혹가다 면접 라이브 코딩으로 정렬 알고리즘을 낸다고도.. (언젠가 구글이 선택, 버블, 삽입 정렬을 냈다가 많은 개발자들의 반발을 샀다는...) 어쨌든 정렬은 여러가지 방법(알고리즘)들이 있고 효율성 차이가 극명하게 보이기 때문에 일반적으로 알고리즘을 공부할 때 가장 먼저 풀어보는 문제이기도 하다.

[2] 비교식 정렬과 분산식 정렬

[2-1] 비교식 정렬

두 원소를 비교하여 정렬한다. 선택정렬, 버블정렬, 삽입정렬이 여기에 해당한다. 대부분 O(N^2)로 효율이 좋지 않다. (특히 선택정렬과 버블정렬은 멍청한 알고리즘이라고도 한...) 삽입정렬의 경우, 정렬되어 있다면 속도가 매우 빨라질 수 있다. 거의 정렬되어 있다면, 퀵 정렬보다 좋은 성능을 기대할수도 있다.

[2-2] 분산식 정렬

분할 정복을 기반으로 한 알고리즘. 병합 정렬은 아주 뛰어난 알고리즘이다. O(NlogN)의 성능을 보여주기도 하고 최선과 최악이 같은 안정적 정렬 알고리즘이다. 퀵 정렬의 경우, 평균적으로 O(NlogN)이지만 알고리즘 특성상 이미 정렬된 배열도 정렬을 하려하기 때문에 불안정 정렬이다.

 

💡 오늘의 회고

는 생략....