정렬 알고리즘

[ 삽입정렬 ]

모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣음

과정

손 안의 카드를 정렬하는 방법과 유사함

1. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입
2. 새로운 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬됨

알고리즘의 구체적인 개념

1. 2번째 자료부터 시작하여 (즉 첫번째 key 값은 두번째 자료부터 시작함) 앞의 원소들과 비교하여 삽입할 위치를 지정한후 원소를 뒤로 옮기고 지정한 자리에 원소를 삽입하여 정렬
2. 2번째 자료는 1번째 자료, 3번째 자료는 1-2번째 자료 ... 와 비교한후 원소가 삽입될 위치를 찾음
3. 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한칸씩 뒤로 이동

한회차 예시

3	1	5	2	4
3		5	2	4
1	3	5	2	4

예시

3	1	5	2	4
1	3	5	2	4
1	3	5	2	4
1	2	3	5	4
1	2	3	4	5

장점과 단점

장점

• 안정한 정렬 방법
• 구현이 간단
• 선택 정렬이나 거품 정렬과 같은 알고리즘에 비교하여 빠름
• 대부분의 원소가 이미 정렬되어 있는 경우 메우 효율적

단점

• 비교적 많은 원소의 이동을 포함함
• 원소 수가 많아질수록 효율이 떨어짐

시간복잡도

O(n^2)

 

[ 선택정렬 ]

제자리 정렬 알고리즘

해당 순서에 넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘

 

- 제자리 정렬 알고리즘

입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

과정

1. 주어진 배열 중에서 최솟값을 찾음
2. 그 값을 맨앞에 위치한 값과 교체함
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체함
4. 하나의 원소만 남을때까지 위의 1-3 과정을 반복함

알고리즘의 구체적인 개념

1. 1번째 원소를 2번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 값을 찾아 첫번째 놓음
2. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 2회전에는 두번째 원소를 3번째 원소부터 비교함
3. 반복하며 마지막 원소까지 정렬

예시

3	1	5	2	4
1	3	5	2	4
1	2	5	3	4
1	2	3	5	4
1	2	3	4	5

장점과 단점

장점

• 자료 이동 횟수가 미리 결정됨

단점

• 안전성을 만족하지 않음
• 같은 원소가 있는 경우에 상대적인 위치가 변경될 수 있음

시간복잡도

O(n^2)

 

[ 버블정렬 ]

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환함

양방향으로 번갈아 수행하면 칵테일 정렬이 됨

선택 정렬과 기본 개념이 유사함

알고리즘의 구체적인 개념

1. 1번째 자료와 2번째 자료, 2번째 자료와 3번째 자료 ... (n-1)번째 자료와 n번째 자료를 비교하여 교환하면서 정렬
2. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨끝에 있는 자료는 정렬에서 제외됨
3. 이렇게 정렬이 1회전 수행할때마다 정렬에서 제외되는 데이터가 늘어남

한회차 예시

3	1	5	2	4
1	3	5	2	4
1	3	5	2	4
1	3	2	5	4
1	3	2	4	5

예시

3	1	5	2	4
1	3	2	4	5
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5

장점과 단점

장점

• 구현이 매우 간단

단점

• 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 모든 원소와 교환되어야 함
• 특정 원소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 발생함

일반적으로 자료의 교환작업(Swap)이 자료의 이동작업(Move)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않음

시간복잡도

O(n^2)

 

[ 셸정렬 ]

Donald L.Shell이라는 사람이 제안한 방법으로 삽입정렬을 보완한 알고리즘

삽입정렬이 어느 정도 정렬된 배열에 대해서는 빠른것에서 착안

삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한번에 정렬하지 않음

과정

1. 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬
2. 데이터를 다시 잘게 나누어서 삽입 정렬
3. 계속 반복하며 마침내 정렬이 됨

알고리즘의 구체적인 개념

1. 정렬해야 할 리스트의 각 k(간격, gap)번째 요소를 추출해서 부분 리스트를 만듬
   • 간격의 초깃값: 정렬할 요소의 수 / 2
   • 생된 부분 리스트의 개수는 gap과 같음
2. 각 회전마다 간격 k를 절반으로 줄임
   • 즉 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가함
   • 간격은 홀수로 하는 것이 좋음
   • 간격을 절반으로 줄일때 짝수가 나오면 +1을 해서 홀수로 만듬
3. 간격 k가 1이 될때까지 반복함

한회차 예시

5	1	6	3	2	4
5			3
	1			2
		6			4

3			5
	1			2
		4			6
3	1	4	5	2	6

예시

5	1	6	3	2	4
3	1	4	5	2	6
2	1	3	5	4	6
1	2	3	4	5	6

장점과 단점

장점

• 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동함
  • 삽입 정렬보다는 최종 위치에 있을 가능성이 높아짐
• 정렬은 기본적으로 삽입정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행됨

단점

• k 간격을 잘못 설정한다면 성능이 굉장히 안 좋아질수 있음

시간복잡도

O(n^1.5)

 

[ 퀵정렬 ]

찰스 엔터니 리처드 호허(Charles Antony Richard Hoare)가 개발한 알고리즘

불안정 정렬, 비교정렬

분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑함

합병정렬과는 달리 리스트를 비균등하게 분할

 

- 비교정렬

다른 원소와 비교만으로 정렬을 수행

 

과정

1. 리스트 안에 있는 한 요소를 선택하여 선택한 원소를 피벗(pivot)이라고 함
2. 피멋을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소는 오른쪽으로 옮겨짐
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 순환 호출을 이용하여 정렬을 반복함
4. 부분 리스트들이 더 이상 분할이 불가능할때까지(0, 1) 반복

알고리즘의 구체적인 개념

하나의 리스트를 피벗을 기준으로 두개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법임

순환 호출이 한번 진행될때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로 알고리즘이 반드시 끝난다는 것을 보장할 수 있음

1. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할(왼쪽: 피벗보다 작은 요소, 오른쪽: 피벗보다 큰 요소)
2. 정복(Conquer): 부분 배열의 크기가 충분히 작다면 부분 배열을 정렬하며 충분히 작지 않다면 순환 호출을 이용하여 다시 분할 정복 방법을 적용함
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병함

예시

3	4	5	2	1
2	1	3	4	5
1	2	3	4	5

장점과 단점

장점

• 속도가 빠름
  • 다른 O(n log n) 알고리즘에 비해 훨씬 바르게 동작함
• 추가 메모리 공간을 필요로 하지 않음
  • O(log n)만큼의 메모리를 필요로 함

단점

• 불안정 정렬
• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림 => O(n^2)
• 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할때는 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택해야함

- 단점을 극복하기 위해 피벗을 한자리에서만 하는것이 아니라 랜덤으로 뽑게 하는 방법도 있음

시간복잡도

O(n log n)

 

[ 힙정렬 ]

- 힙

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조

과정

최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨

1. 정렬해야할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만듬
2. 한번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 됨
3. 삭제되는 요소들(최대값부터 삭제)은 값이 감소되는 순서로 정렬되게 됨

알고리즘의 구체적인 개념

• 힙은 1차원 배열로 쉽게 구현될 수 있음
• 정렬해야 할 n개의 요소들은 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입
• 최대 힙으로 구성된 배열에서 최댓값부터 삭제함

최대 힙(max heap)의 삽입

1. 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴

최대 힙(max heap)의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨
   • 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
3. 힙을 재구성함
   
   • 즉 힙의 마지막 노드를 가져아가 다시 정렬하여 밑으로 보내는 것

장점과 단점

장점

• 시간 복잡도가 좋은편(최악의 상황에서도 O(n log n))
• 추가적인 메모리 공간을 사용하지 않음
• 전체 자료를 정렬하는 것이 아닌 가장 큰 값 몇개만 필요할때 매우 유용

단점

• 구현이 복잡함
• 안전성을 보장받지 못함

시간복잡도

O(n log n)

 

[ 합병정렬 ]

존 폰 노이만(John von Neumann)이라는 사람이 제안한 방법

일반적인 방법으로 구현했을대 안정정렬에 속하며 분할 정복 알고리즘의 하나

 

- 분할 정복(divide and conquer) 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략

분할 정복 방법은 대개 순환 호출을 이용하여 구현함

 

과정

리스트의 길이가 0또는 1이면 이미 정렬된 것으로 봄

1. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분으로 리스트를 나눔
2. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

알고리즘의 구체적인 개념

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용함
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계임

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할함
2. 정복(Conquer): 부분 배열의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할 정복 방법을 적용하며 부분 배열의 크기가 충분히 작다면 부분 배열을 정렬함
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병함

예시

장점과 단점

장점

• • 안정적인 정렬 방법
    • 데이터의 분포에 영향을 더 받아 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일(O(n log n))

단점

• 배열로 구성하면 임시 배열이 필요함(즉 추가적인 저장 공간 필요)
  • 추가 공간을 사용하므로 제자리 정렬이 아님
• 데이터 크기가 큰 경우 이동 횟수가 많으므로 시간 낭비 발생

시간복잡도

O(n log n)

 

[ 정렬알고리즘 시간 복잡도 비교 ]

정렬	최고	평균	최악
삽입정렬	O(n)	O(n^2)	O(n^2)
선택정렬	O(n^2)	O(n^2)	O(n^2)
버블정렬	O(n^2)	O(n^2)	O(n^2)
셸 정렬	O(n)	O(n^1.5)	O(n^2)
퀵정렬	O(n log n)	O(n log n)	O(n^2)
힙정렬	O(n log n)	O(n log n)	O(n log n)
합병정렬	O(n log n)	O(n log n)	O(n log n)