[Algorithm] 정렬

정렬이란?

n개의 서로 다른 수가 주어졌을 떄, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순)으로 만드는 문제이다.

                                   ex)          4 2 1 9 5  ->  1 2 3 5 9

 

이런 식의 문제들은 아주 기본적이지만 실생활에 자주 쓰인다. 수능시험을 본 후 수십 만개의 omr카드를 성적순으로 분류해야하는데 이를 일일히 카운팅하면 정말 피곤할것같다. 머리가 대머리가 되버릴 수도 있다!

이 문제를 풀기 위해선 여러가지 정렬방법을 적용할 수 있다.

대표적인 정렬 방법으로는

 

• 버블 정렬 (Bubble sort)
• 삽입 정렬 (Insert sort)
• 병합 정렬 (Merge sort)
• 퀵 정렬 (Quick sort)
• 힙 정렬 (Heap sort)

그 이외에 버킷 정렬, stable sort, 기수 정렬, 계수 정렬 등이 있다.

이 9가지 정렬 방법에 대해 이후 포스팅에서 설명할 예정이다. (그 외엔 이 블로그에 없어요!)

 

이 많은 정렬 방법중에 어떤 것이 가장 효율적일까?? 정렬 알고리즘의 시간복잡도 비교표를 살펴보자.

정렬 방법	가장 좋을 때	평균	최악의 경우
버블 정렬	n^2	n^2	n^2
삽입 정렬	n^2	n^2	n^2
병합 정렬	nlogn	nlogn	nlogn
퀵 정렬	nlogn	nlogn	n^2
힙 정렬	nlogn	nlogn	nlogn

이 표를 보면 육안상으로 가장 빠른 정렬은 병합정렬과 힙정렬이 된다

하지만 보통 내가 코드로 구현하려면 난이도는 대부분 그 반대가 된다! 세상에 공짜는 없음에 유의하자

대체 이 정렬들은 어떤식으로 작동하고, 어떻게 짜야하는걸까??

다음 포스팅에서 버블 정렬과 삽입 정렬에 대해 살펴보자.