C++ 정렬 알고리즘 (버블정렬, 삽입정렬, 선택정렬, 합병정렬, 퀵정렬, 힙정렬, 셀정렬, 기수정렬)

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 

업데이트 중입니다.

 

---

버블 정렬( Bubble Sort )

삽입 정렬( Insertion Sort )

선택 정렬( Selection Sort )

합병 정렬( Merge Sort )

퀵 정렬( Quick Sort )

힙 정렬( Heap Sort )

셸 정렬( Shell Sort )

기수 정렬 ( Radix Sort )

 

---

◾  제자리 정렬

정렬에 추가적인 메모리 공간이 들지 않는다.

아예 안 드는 것은 아니고 거의 무시할 정도의 메모리를 사용한다.

•  Insertion, Bubble, Selection, Quick

•  Tip : 최악이 O(n^2)인 것들이라고 기억

 

---

◾  안정 정렬 ( Stable Sort ) 

정렬 전의 순서를 유지하고 정렬된다.

•  Insertion, Bubble, Merge

•  Tip : IBM 이라고 외우면 쉽다.

 

◾  불안정 정렬 ( Unstable Sort ) 

정렬 전의 순서를 유지하지 않고 정렬된다.

•  Selection, Quick, Heap, Intro

 

---

◾  내부 정렬 ( Internal Sort ) 

정렬하고자 하는 모든 데이터가 메모리에 올라와 정렬이 수행됨

•  교환 방식 ( Selection, Bubble, Quick)

•  삽입 방식 ( Insertion, Shell )

•  병합 방식 ( Merge )

•  분배 방식 ( Radix, Counting, Bucket )

•  선택 방식 ( Heap, Tree )

 

◾  외부 정렬 ( External Sort ) 

정렬하고자 하는 데이터가 너무 크기 때문에 일부만 올려서 정렬하고 다시 합하는 방식

파일이 저장된 디스크나 테이프 장치를 마치 메모리처럼 생각해서 정렬한다.

 

1. 파일을 쪼개어 읽어 내부 정렬하여 임시 파일로 저장

2. 임시 파일들을 병합

 

디스크 이용

•  2-way, n-way 병합

 

테이프 이용

•  균형 병합 ( Balanced Merge Sort )

•  계단식 병합 ( Cascade Merge Sort )

•  다단계 병합 ( Polyphase Merge Sort )

•  교대식 병합 ( Oscillating Merge Sort )

 

---

버블 정렬( Bubble Sort )

	설명
방식	인접한 두 원소를 검사하여 순서가 맞지 않으면 교환하는 방식 앞에서 부터 차례대로 비교하여 가장 큰 값을 맨 뒤로 밀어낸다. 마지막 까지 밀려난 값은 앞의 값 보다 크니까 검사에서 제외 배열 크기가 4일 때 0 1 2 3 0 1 2 0 1 이런 식으로 검사한다.
분류	내부 정렬 - 교환 방식 안정 정렬, 제자리 정렬
시간 복잡도	최선 O( N^2 ) 평균 O( N^2 ) 최악 O( N^2 )

 

과정

초기 상태	7 4 5 1 3
1 회전	( 4 7 )5 1 3 4 ( 5 7)1 3 4 5 ( 1 7 )3 4 5 1 ( 3 7 ) 결과 4 5 1 3 7
2 회전	4( 1 5 )3 7 4 1 ( 3 5 ) 7 결과 4 1 3 5 7
3 회전	( 1 4 ) 3 5 7 1 ( 3 4 ) 5 7 결과 1 3 4 5 7
4 회전	결과 1 3 4 5 7

코드

void bubble_sort(int list[], int n)
{
  int i, j, temp;
  for(i = n-1; i > 0; i--)
  {
    for(j = 0; j < i; j++)
    {
      if(list[j] < list[j+1])
      {
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

 

 

 

---

삽입 정렬( Insertion Sort )

	설명
방식	모든 요소를 앞에서 부터 차례대로 비교하여 자신의 위치를 찾아 삽입하는 방식 특이한 것은 2번 째 ( idx 1 ) 부터 시작한다는 것이다. 2번 째 부터 앞의 숫자들과 비교해서 자신의 위치를 찾는다. 배열 크기가 4일 때 1 0 2 1 0 3 2 1 0 이런 식으로 검사한다. 물론 검사하다가 자신의 위치를 찾으면 삽입
분류	내부 정렬 - 삽입 방식 안정 정렬, 제자리 정렬
시간 복잡도	최선 O( N ) 평균 O( N^2 ) 최악 O( N^2 )

 

과정

초기 상태	7 4 5 1 3
1 회전	7 4 5 1 3 ( 4 7 )5 1 3 결과 4 7 5 1 3
2 회전	4 7 5 1 3 4 ( 5 7 ) 1 3 결과 4 5 7 1 3
3 회전	4 5 7 1 3 4 5 ( 1 7 ) 3 4 ( 1 5 ) 7 3 ( 1 4 ) 5 7 3 결과 1 4 5 7 3
4 회전	1 4 5 7 3 1 4 5 ( 3 7 ) 1 4 ( 3 5 ) 7 1 ( 3 4 ) 5 7 결과 1 3 4 5 7

코드

void insertion_sort(int list[], int n)
{
  int i, j, key;
  for(i = 1; i < n; i++)
  {
    key = list[i];
    for(j = i-1; j >= 0 && list[j] > key; j--)
    {
      list[j+1] = list[j];
    }
    list[j+1] = key;
  }
}

 

 

---

선택 정렬( Selection Sort )

	설명
방식	내 위치에서 끝까지 차례로 탐색하며 선택하는 방식 제자리 정렬 알고리즘 배열 크기가 4일 때 0 1 2 3 1 2 3 2 3 이런 식으로 검사한다.
분류	내부 정렬 - 교환 방식 불안정 정렬
시간 복잡도	최선 O( N^2 ) 평균 O( N^2 ) 최악 O( N^2 )

 

과정

초기 상태	7 4 5 1 3
1 회전	결과 1 4 5 7 3
2 회전	결과 1 3 5 7 4
3 회전	결과 1 3 4 7 5
4 회전	결과 1 3 4 5 7

코드

void selection_sort(int list[], int n)
{
  int i, j, least, temp;
  for(i = 0; i < n-1; i++)
  {
    least = i;
    for(j=i+1; j<n; j++)
    {
      if(list[j] < list[least])
      {
        least = j;
      }
    }

    if(i != least)
    {
    	temp = list[i];
        list[i] = list[least];
        list[least] = temp;
    }
  }
}

 

 

---

합병, 병합 정렬( Merge Sort )

	설명
방식	전체 배열을 두 개의 같은 크기로 분할하여 각각을 정복하고 병합하는 방식 병합 과정에서 정렬된다.
분류	내부 정렬 - 병합 방식 안정 정렬, 분할 정복 알고리즘
시간 복잡도	최선 O( N log N ) 평균 O( N log N ) 최악 O( N log N )

 

과정

초기 상태	7 4 5 1 3
분할	( 7 4 ) | ( 5 1 3 )
분할	( 7 4 ) | ( 5 1 | 3 )
분할	( 7 | 4 ) | ( ( 5 | 1 ) | 3 )
병합	( 4 7 ) | ( 1 5 ) | 3
병합	( 4 7 ) | ( 1 3 5 )
병합	1 3 4 5 7

 

 

코드

// 대상 배열 arr
// 정렬된 배열 sotred

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left, j = mid + 1, k = left;
	while (i <= mid && j <= right)
		 sorted[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    
    // 남은 것을 뒤에 붙이기
	int tmp = (i > mid) ? j : i;	
	while(k <= right) sorted[k++] = arr[tmp++];
    
    // 정렬된 것을 복사
	for (int i = left; i <= right; i++) arr[i] = sorted[i];
}

void merge_sort(int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; 
		merge_sort(left, mid);
		merge_sort(mid + 1, right);
		merge(left, right);
	}
}

 

 

---

퀵 정렬(quick sort)

방식	배열을 피벗( Pivot )을 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽으로 옮기면서 정렬 하고 분할하는 방식으로 분할을 다 하면 정렬이 완료된다. pivot은 임의로 정해준다. low는 pivot 보다 큰 것을 만나면 stop high는 pivot 보다 작은 것을 만나면 stop 1) low, high 둘 다 멈춘 경우 swap( low, high ) 2) low, high 엇갈린 경우 swap( pivot, high )
분류	내부 정렬 - 교환 방식 불안정 정렬, 제자리 정렬, 분할 정복 알고리즘
시간 복잡도	최선 O( N log N ) 평균 O( N log N ) 최악 O( N^2 ) 최악의 경우는 이미 정렬, 역 정렬된 경우

 

과정

초기 상태	7 4 5 1 3
정렬	pivot = 7 7 4 5 1 3 1. low = 4, high = 3 2. low = 5, high = 3 3. low = 1, high = 3 4. low = 3, high = 3 5. high와 pivot 교환 = 3 4 5 1 7  결과 3 4 5 1 7
분할	3 4 5 1 | 7
정렬	pivot = 3 3 4 5 1 1. low = 4, high = 1 ( 둘 다 Stop ) 2. high와 low 교환 = 3 1 5 4  3. low = 5, high = 5 4. low = 4, high = 1  5. high와 pivot 교환 = 1 3 5 4 결과 1 3 5 4
분할	1 | 3 | 5 4 좌 : 1 우 : 5 4
정렬	좌 : 1 은 1개만 남았음으로 끝 우 : pivot = 5 5 4 1. low = 4, high = 4 2. high와 pivot 교환 = 4 5 결과 4 5
결과	분할해서 정렬한 것이 다음과 같은 모양으로 나옴 1 | 3 | 4 5 | 7 1 3 4 5 7

 

 

코드

void QuickSort(int left, int right)
{
	int L = left, R = right;
	int pivot = (L + R) / 2; // 피벗을 중심으로 두었습니다.
	if (L < R)
	{
		while (L < R)
		{
			while (data[L] <= data[pivot]) L++;
			while (data[R] > data[pivot] && R > pivot) R--;
			if (L < R)  SWAP(data[L], data[R]);
		}
		SWAP(data[R], data[pivot]);
		pivot = R;
		QuickSort(left, pivot - 1);
		QuickSort(pivot + 1, right);
	}
}

 

 

---

힙 정렬(heap sort)

설명
방식	최대 / 최소 힙 트리를 구성해 정렬하는 방식 주로 전체 자료를 정렬하기 보다는 가장 큰 값 몇개를 뽑아낼 때 사용한다. 내림차순 : 최대 힙 오름차순 : 최소 힙
분류	내부 정렬 - 선택 방식 불안정 정렬
시간 복잡도	최선 O( N log N ) 평균 O( N log N ) 최악 O( N log N )
최대 힙( Max Heap )	루트 노드에 가장 큰 값이 들어간다. 삽입 1. 새 노드를 마지막 노드에 삽입 2. 새 노드를 부모와 비교 새 노드가 부모보다 크면 교환, 아니면 중단 삭제 1. 최대 값 = 루트를 삭제한다. 2. 마지막 노드를 루트로 삽입 3. 삽입한 노드를 자식과 비교 ( 둘 중 큰 것과 비교 시도 ) 삽입한 노드가 더 작으면 교환, 아니면 중단
최소 힙( Min Heap )	루트 노드에 가장 작은 값이 들어간다. 삽입 1. 새 노드를 마지막 노드에 삽입 2. 새 노드를 부모와 비교 새 노드가 부모보다 작으면 교환, 아니면 중단 삭제 1. 최소 값 = 루트를 삭제한다. 2. 마지막 노드를 루트로 삽입 3. 삽입한 노드를 자식과 비교 ( 둘 중 작은 것과 비교 시도 ) 삽입한 노드가 더 크면 교환, 아니면 중단

 

코드

 

 

 

---

셸 정렬(Shell Sort)

설명	곧 업데이트 삽입 정렬이 어느 정도 정렬된 상태에서 정렬 속도가 빠른 것에 착안하여 보완한 알고리즘
방식	내부 정렬 - 삽입 방식
시간 복잡도	최선 O( N ) 평균 O( N^1.5 ) 최악 O( N^2 )

 

과정

처음 상태

7 4 5 1 3

코드

 

---

기수 정렬 ( Radix Sort )

설명	곧 업데이트
방식	내부 정렬 - 분배 방식

 

 

---

C 언어

 

퀵 정렬 라이브러리 함수

 

#include <stdlib.h>

qsort()

 #include <stdlib.h>
/*
base : 배열의 시작주소
num : 배열 요소 개수
width : 배열 요소 하나의 크기 ( 바이트 )
compare : 비교함수 ( 두 요소를 비교하여 결과를 정수로 반환 )

*/
void qsort( 
            void *base,
            size_t num,
            size_t width,
            int(*compare)(const void *, const void *)
);

int compare(const void *u, const void *v)
{
	if(a > b) return 1;
    else if (a == b) return 0;
    else -1;
}

int main()
{
	int arr[5] = { 1, 2, 5, 3, 4 };
	qsort( (void *)arr, (size_t)5, sizeof(int), compare);
}

 

 

C ++

#include<algorithm>

sort()

stable_srot()

 

 

---

균형 병합 ( Balanced Merge Sort )

n개의 테이프 장치가 주어지면 각 테이프에 똑같은 크기의 레코드들이 작은 블록으로 나누어 내부 정렬

계단식 병합 ( Cascade Merge Sort )

부분적으로 정렬된 서브파일들을 한 개의 빈 테이프에 병합해 정렬하는 방법을 반복하여 정렬

다단계 병합 ( Polyphase Merge Sort )

분산수록되는 레코드의 수를 피보나치 수열을 이용하여 레코드를 분산수록하여 정렬

교대식 병합 ( Oscillating Merge Sort )

테이프의 읽기 쓰기 기능이 역방향과 순방향 다 가능한 테이프 장치의 기능을 이용하여 정렬

n 개의 테이프가 있을 때 1개의 테이프에 정렬되지 않은 입력 파일 저장, 나머지 n-1개의 테이프로 정렬

 

수정 중입니다...