정렬 알고리즘 정리

정렬 알고리즘(sorting algorithm)

정렬의 사전적 의미는 '데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일'를 말하는 것으로 예를들자면 학교에서 각 반 학생들을 키 순으로 세우는 것, 제목 순으로 정리하는 것 등 이것 모두가 '정렬'입니다.

지금부터 소개하고자 하는 '정렬 알고리즘(sorting algorithm)'을 사용하면 편하게 데이터를 찾을 수 있게됩니다.

 

1. 버블 정렬(Bubble Sort) 뽀글뽀글 뽀글뽀글!

 

지금부터 소개하고자 하는 버블 정렬은 정렬 알고리즘 중 활용도가 높은 알고리즘이며, 구현도 쉽게 가능하여 많은 프로그래머들이 즐겨 쓰는 알고리즘 입니다. 버블 정렬은 데이터를 차례대로 정렬하는 과정이 수중 거품의 움직임과 유사하여 거품 정렬이라고도 부릅니다.

[버블 정렬(Bubble sort)의 예]

 

버블 정렬은 자신과 인접한 데이터와 비교하여 정렬하는 방식입니다. 위의 예를 보시면 첫번째로 84와 69를 비교하여 84가 더 큰걸 확인하고 위치를 바꾸었습니다. 또다시 84와 76을 비교하여 84가 더 큰걸 확인하고 위치를 바꾸고, 84와 86을 비교하여 84가 작으므로 데이터의 위치를 바꾸지 않고 다음으로 넘어갑니다.

 

이렇게 정렬을 하다, 더이상 위치 교환이 일어나지 않게되면 루프를 빠져나옵니다. 그렇다면 이 버블 정렬은 얼마나 빠른것일까요? 한번 순회를 할때마다 교환이 일어나는 범위가 하나씩 줄어듭니다. 만약 어느 데이터 집합에 데이터가 n개 존재한다면 n-1만큼 반복해야 정렬이 끝납니다. 이 정렬의 비교 횟수를 알아볼까요?

 

버블 정렬의 비교 횟수 = (n-1)+(n-2)+(n-3)+...+(n-(n-2))+(n-(n-1)) = (n-1)+(n-2)+(n-3)+...+3+2+1 = n(n-1)/2

 

이 식을 이용하여 10000개의 데이터가 존재한다면 49,995,000번의 데이터 교환이 일어납니다. 버블 정렬 알고리즘의 시간 복잡도를 계산하면 O(n^2), n값이 증가하면 실행 시간이 기하급수적으로 늘어나게 된다. 여기서 시간 복잡도란 무엇일까? 시간 복잡도란 문제의 크기에 따라 걸리는 시간이며 보통 빅 O표기법을 사용합니다.

 

 

 

2. 퀵 정렬(Quick Sort)

 

퀵 정렬의 기본 방식은 분할이다.

분할의 의미는 축, (Pivot 이라고 많이 쓴다.)값을 중심으로 하는데,

왼쪽은 이 축 값보다 작은 값으로, 오른쪽은 이 축 값보다 큰 값으로 배열 시킨다.

이렇게 한 뒤, 축값을 조정하여 방금 한 것의 왼쪽과 오른쪽 부분을 각각 또 다시 분할하고,

마찬가지고 왼쪽은 축 값보다 작은값, 오른쪽은 큰 값으로 배열 시키는 것을 반복한다.

이 과정을 분할의 크기가 1이 될 때 까지 반복하면 전체적으로 정렬이 완료된다.

여기서 눈치 빠르신 분들은 이미 알아채셨겠지만,

퀵정렬은 작은 단위로 분할하는 과정을 반복하기 때문에 재귀함수를 사용합니다.

문제를 작은 단위로 쪼갤 때 재귀함수를 응용할 수 있다는 점은 저번에 한번 거론했었고,

아시는 분도 많이 계실겁니다.

자세히 설명을 해보겠습니다.

1. 일단, 피봇값을 데이터배열의 오른쪽 값으로 정한다 (임의로)

-----------------------------------------------

2. i는 왼쪽부터 시작해서, 배열의 [i] 인자가 피봇보다 크면 멈추고,

j는 오른쪽부터 시작해서 배열의 [j] 인자가 피봇보다 작으면 멈춘다.

-----------------------------------------

3. i인자의 값과 j인자의 값을 교환한다

------------------------------------------

4. i > j 가 될 때 까지 2.와 3.을 반복한다.

---------------------------------------------

5. i > j 가 되면, i인자의 값과 pivot 을 교환한다.

여기까지가 1회전 이다.

1회전 후, i를 기준으로 두 데이터 배열로 분할하고,

두 데이터 배열에 대해서 또 이 것을 반복한다.

이 반복은 분할의 크기가 1이 될 때 까지 계속한다.

 

3. 삽입 정렬(Insert Sort)

 

기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)중 하나.

·     수행 방법

o정렬 되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

o정렬할 자료를 두 개의 부분집합 S와 U로 가정

§  부분집합 S : 정렬된 앞부분의 원소들

§  부분집합 U : 아직 정렬되지 않은 나머지 원소들

§  정렬되지 않은 부분집합 U의 원소를 하나씩 거내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입

§  삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분 집합 U가 공집합이 되면 삽입 정렬이 완성된다.

·     삽입 정렬 수행 과정

o정렬 되지 않은 [ 69, 10, 30, 2, 16, 8, 31, 22 ]의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자.

§  초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.
S=[69], U=[10, 30, 2, 16, 8, 31, 22]

1. U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69)이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할

S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.

S = [10, 69], U = [30, 2, 16, 8, 31, 22]

2. U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69)이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10)이므로

원소 10과 69 사이에 삽입한다.

S = [10, 30, 69], U = [2, 16, 8, 31, 22]

3. U의 첫 번째 원소 2을 S의 마지막 원소 69와 비교하여 (2 < 69)이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30)이므로

다시 그 앞자리 원소 10과 비교하는데, (2 < 10)이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.

S = [2, 10, 30, 69], U = [16, 8, 31, 22]

4. U의 첫 번째 원소 16을 S의 마지막 원소 69와 비교하여 (16 < 69)이므로 그 앞자리 원소 30과 비교한다. (16 < 30)이므로

다시 그 앞자리 원소 10과 비교하여, (16 > 10)이므로 원소 10과 30 사이에 삽입한다.

S = [2, 10, 16, 30, 69], U = [8, 31, 22]

5. U의 첫 번째 원소 8을 S의 마지막 원소 69와 비교하여 (8 < 69)이므로 그 앞자리 원소 30과 비교한다. (8 < 30)이므로 그 앞자리

원소 10과 비교하여, (8 < 10)이므로 다시 그 앞자리 원소 2와 비교하는데, (8 > 2)이므로 원소 2와 10사이에 삽입한다.

S = [2, 8, 10, 16, 30, 69], U = [31, 22]

6. U의 첫 번째 원소 31을 S의 마지막 원소 69와 비교하여 (31 < 69)이므로 그 앞자리 원소 30과 비교한다. (31 > 30)이므로 원소30과

69 사이에 삽입한다.

S = [2, 8, 10, 16, 30, 31, 69], U = [22]

7. U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69)이므로 그 앞자리 원소 31과 비교한다. (22 < 31)이므로 그앞자리

원소 30과 비교한다. (22 < 30)이므로 다시 그 앞자리 원소 16과 비교하여, (22 > 16)이므로 원소 16과 30사이에 삽입한다.

S = [2, 8, 10, 16, 22, 30, 31, 69], U = []

·     삽입 정렬 알고리즘

·     삽입 정렬 알고리즘의 분석

o메모리 사용공간

§  n개의 원소에 대하여 n개의 메모리 사용

o연산 시간

§  최선의 경우 : 원소들이 이미 정렬되어 있어서 비교횟수가 최소인 경우
- 이미 정렬되어있는 경우에는 바로 앞자리 원소와 한번만 비교한다.
- 전체 비교횟수 = n-1
- 시간 복잡도 : O(n)

§  최악의 경우 : 모든 원소가 역순으로 되어있어서 비굣횟수가 최대인 경우
- 전체 비교횟수 = 1+2+3+...+(n-1) = n(n-1)/2
- 시간 복잡도 : O(n²)

§  삽입 정렬의 평균 비교횟수 = n(n-1)/4

§  평균 시간 복잡도 : O(n²)

 

 

4. 선택 정렬(Selection Sort)

 

기초적인 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입정렬) 중 하나

·     전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

·     수행 방법

o전체 원소 중에서 가장 작은 원소를 찾아서 선택하여 첫 번째 원소와 자리를 교환한다.

o그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.

o그 다음에는 세 번째로 작은 원소를 찾아서 세 번째 원소와 자리를 교환한다.

o이 과정을 반복하면서 정렬을 완성한다.

·     선택 정렬 수행 과정

o정렬 되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택정렬 방법으로 정렬하는 과정을 살펴보자.

1. 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69 와 자리를 교환한다.

2. 두 번째 자리를 기준 위치로 정하고 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리를 교환한다.

3. 세 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 10을 선택하여 기준 위치에 있는 원소 30과 자리를 교환한다.

4. 네 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 16을 선택하여 기준 위치에 있는 원소 69와자리를 교환한다.

 

5. 다섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 22를 선택하여 기준 위치에 있는 원소 69와 자리를 교환한다.

6. 여섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 30을 선택하여 기준 위치에 있는 30과 자리를 교환한다. (자기자신 교환 = 제자리)

7. 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리를 교환한다. (위와 마찬가지 경우임)

·     선택 정렬 알고리즘

·     선택 정렬 알고리즘 분석

o메모리 사용공간

§  n개의 원소에 대하여 n개의 메모리 사용

o비교 횟수

§  1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교

§  2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교

§  3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교

§  i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교

o어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n²)이다

 

 

========================================================================================

‣ 프로그램 소개 : 선택, 버블, 삽입, 쉘, 퀵, 합병정렬을 구현하여 동작시간 비교

========================================================================================

‣ 세부작업 내용 :

- 선택정렬(평균 O(n^2))

최소 원소를 찾아 제자리에 위치

- 버블정렬(평균 O(n^2))

인접한 두 키를 비교하여 제자리에 위치(선택정렬보다 자료이동이 많다)

- 삽입정렬(평균 O(n^2))

좌측으로부터 한 원소씩 제자리에 삽입

- 쉘정렬(평균 O(N logN))

삽입정렬을 확장한 것으로 멀리 떨어진 원소를 교환하여 속도를 빠르게한 알고리즘

- 퀵정렬(평균 O(N logN))

분할원소를 기준으로 좌/우측을 분할하여 정렬

- 합병정렬(평균 O(N logN))

퀵 정렬과 유사하지만 분할 후 부분배열을 합치면서 정렬하는 방식

========================================================================================

[출처] 자료구조 : 정렬 알고리즘 (이상호의 게임 프로그래머되기 프로젝트!!) |작성자 Soul Coder

 

정렬 알고리즘 정리

정렬 알고리즘.docx