[Algorithm] 자료구조_정렬(Sorting)

오늘은 정렬에 대해서 공부하고자 한다. 

 

정렬이란 데이터의 집합을 일정한 순서로 나열하는 집합을 의미한다.

즉 알고리즘을 이용해 데이터를 정렬하게 되면 검색을 쉽게 할 수 있다.

 

정렬 알고리즘의 핵심 요소는 교환, 삽입, 선택이다. 대부분의 정렬 알고리즘은 이 3가지 요소들을 응용한 것이다.

 

대표적인 정렬 알고리즘은 크게 8종류가 있는데  아래와 같다.

 

1. 버블 정렬
: 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라서 교환을 하는 알고리즘으로 단순교환정렬이라고도 한다.

2. 단순선택정렬
: 가장 작은 요소를 맨앞으로 이동하고, 두번째 작은 요소는 맨앞에서 두번째로 이동하는 등의 작업을 반복하는 것이다.

3. 단순삽입정렬
: 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 "삽입하는" 작업을 방법하여 정렬하는 것이다.

4. 셀 정렬
: 단순 삽입 정렬의 장점을 살리고 단점을 보안하여 좀 더 빠르게 정렬하는 알고리즘이다.

5. 퀵정렬
: 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되고 있다.

6. 병합 정렬
: 배열을 앞부분과 뒷부분 둘로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘이다.

7. 힙정렬 
: 선택정렬을 응용한 알고리즘으로 힙의 특성을 이용하여 정렬한 알고리즘이다.

8. 도수정렬
: 요소의 대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.

이 중에서 나는 가장 빠른 정렬이면서 많이 사용되는 퀵정렬에 대해 좀더 알아보고자 한다.