Sort Algorithm

목차

1. 정렬이란?
2. Bubble Sort
3. Selection Sort
4. Insertion Sort
5. Quick Sort
6. Merge Sort

본문내용

정렬이란?
정렬(Sort)이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미한다. 예를 들어서 1부터 10까지의 번호가 적힌 카드가 순서 없이 배열되어있다고 하자 이때 오름차순(ascending order)으로 정렬한다 함은 1, 2, 3, 4순으로 10까지의 카드를 순서대로 배열함을 말한다. 그래서 알고리즘들 중에서는 가장 역사가 깊으며, 가장 연구가 많이 되어 왔으며, 가장 다양한 알고리즘들이 선택을 기다리고 있다. 일반적으로 가장 빠른 정렬 알고리즘은 퀵 정렬(Quick Sort)이라고 알려져 있고 실제로도 가장 빠른 속력을 나타낸다. 하지만 퀵 정렬은 거의 정렬이 되어 있는 자료에 대해서는 다른 기본적인 정렬 알고리즘(예를 들어 삽입 정렬)보다는 성능이 떨어진다, 즉 어떤 알고리즘이 가장 좋은 알고리즘이라는 일반 해는 없다. 단지 주어진 상황과 여건에 가장 적합한 알고리즘이 있을 뿐이다.

<중 략>

Quick Sort
1. 개요
1960년에 C.A.R. Hoare라는 사람에 의해 처음으로 고안된 가장 널리 사용되는 정렬 방법중 하나. 아주 빠른 속도를 나타낼 뿐만 아니라 원리도 간단하여, 많은 분야에서 응용되고 있다.

2. Quick Sort의 전략

<그 림>

Quick Sort는 연속적인 분할에 의해 정렬한다. 분할의 의미는 단순히 입력 배열을 나누는 것이 아니라, 축 값을 중심으로 왼쪽은 축 값보다 작은 값을, 오른쪽은 축 값보다 큰 값으로 배열시키는 것이다. 이렇게 하여 축 값의 왼쪽과 오른쪽 부분을 각각 또다시 분할하고 하는 과정을 분할의 크기가 1이 될 때 까지 반복하면 전체적으로는 정렬이 완료된다.

① 만약 N>1이면
A. N크기의 a배열을 분할 하여 축 값의 위치를 mid로 넘긴다.
B. Quick 정렬 알고리즘(a, mid)
C. Quick 정렬 알고리즘(a+mid+1, N-mid-1)

1-A과정의 mid는 배열에서의 위치
1-B 과정의 (a, mid)에 대해서 Quick 정렬 알고리즘을 적용한다는 것은 배열의 처음부터 축의 바로 앞까지의 구간에 대해 재귀적으로 Quick정렬 알고리즘을 다시 수행한다는 뜻이다.

참고 자료

없음