개발기록장

정렬 기법

9 min read

용어 정리

주어진 요소를 정해진 기준에 맞게 요소의 위치를 바꾸는 것

알고리즘 별 비교표

종류평균 시간복잡도최악 시간복잡도추가 메모리안정 정렬
삽입 정렬O(n2)O(n2)O(1)O
병합 정렬O(nlogn)O(nlogn)O(n)O
퀵 정렬O(nlogn)O(n2)O(nlogn)X
힙 정렬O(nlogn)O(nlogn)O(1)X
버킷 정렬O(N + A)O(N + A)O(N + A)O

In-Place : 자료구조를 추가로 사용하지 않는 경우. 추가 메모리가 O(1)이면 In-Place이다. 안정 정렬 : 정렬을 진행했을 때, 같은 값을 가진 데이터끼리의 위치가 변하지 않는 정렬이다.

삽입 정렬

자기 자리에 맞는 자리로 “삽입” 시켜주는 정렬 매 회전마다 앞에 i개는 정렬되어 있다고 가정하고, 그 뒤에 맞는 요소를 하나씩 찾아서 가정된 부분을 하나씩 늘린다.

vector<int> InsertSort(vector<int> &a){
	int N = a.size();
	int key;
	for(int i = 1; i < N; i++) {
		key = a[i];
		int j = i-1
		for(; i>=0 && a[j] > key; j--) a[j+1] = a[j];
		a[j+1] = key;
	}
}

병합 정렬

쪼갠 배열의 크기가 1이 될 때 까지 계속 쪼갠다 (분할) 두 리스트의 값을 처음부터 하나씩 비교해서 두개의 리스트 값 중에서 더 적합한 값을 따로 저장 (정복)

void MergeSort(vector<int> &a, int left, int right) {
	if(a.size() == 1) return a;
	int mid = left + (right-left) / 2;
	if(left < right) {
		MergeSort(a, left, mid);
		MergeSort(a, mid+1, right);
		Merge(a, left, mid, right);
	}
}
 
vector<int> Merge(vector<int> &a, int left, int mid, int right) {
	int i = left; // left 시작 지점
	int j = mid + 1; // right 시작 지점
	int k = left; // 정렬 기준점
 
	while(i <= mid && j <= right) {
		if(a[i] <= a[j]) { // 왼쪽에 있는게 오른쪽에 있는거보다 작음
			swap(a[k], a[i]);
			k++; // 삽입 기준점 다음으로
			i++; // 왼쪽 기준점 다음으로
		}
		else { // 오른쪽에 있는게 왼쪽에 있는거보다 작음
			swap(a[k], a[j]);
			k++; // 삽입 기준점 다음으로
			j++; // 오른쪽 기준점 다음으로
		}
	}
 
	// 이제 남은거 있나 보기
	// i가 mid보다 크다 = 왼쪽은 다 돌았다 => 오른쪽 남은거 다 넣기
	if(i > mid) {
		for(int l = j; l <= right; l++) {
			swap(a[k], a[l]);
			k++;
		}
	}
	// i가 mid보다 작다 = 오른쪽은 다 돌았다 => 왼쪽 남은거 다 넣기
	else { 
		for(int l = i; l <= mid; l++){
			swap(a[k], a[l]);
			k++;
		}
	}
 
	return a;
 
}

퀵 정렬

배열에서 하나를 피벗으로 정함. 그 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한다 두 부분 배열을 정렬한다.

int partition(vector<int> &a, int low, int high) {
	int pivot = arr[high];
	int i = low - 1;
 
	for(int j = 0; j < high; j++){
		if(a[j] <= pivot) {
			i++; 
			swap(a[i], a[j]); // 작은거 발견하면 왼쪽으로 옮겨줘야됨
		}
	}
	swap(a[i+1], a[high]);
	return i+1;
}
 
 
void QuickSort(vector<int> &a, int low, int high){
	if (low < high) {
		int pivot = partition(a, low, high); // 분할 인덱스 구하기
 
		QuickSort(a, low, pivot - 1); // pivot 위치는 이미 정렬되었기 때문에 포함 X
		QuickSort(a, pivot + 1, high);
	}
}

힙 정렬

완전 이진트리 구조인 힙 자료구조를 이용해서 정렬함. 최적값에 빠르게 접근할 수 있음.

힙에서 루트는 최적값임. 만약에 힙 정렬을 오름차순으로 한다고 가정할 때, 힙이 된 배열에서 i번째 인덱스에 위치하는 값은 2*i+1번째 인덱스, 2*i+2번째 인덱스에 위치하는 값 (자식들) 보다 큼 맨 처음 회차에서 힙의 루트는 전체에서 제일 큰 값일 것임 그 값을 맨 뒤로 보내고, 전체 N개의 수 중 방금 뒤로 간 최댓값을 제외한 N-1개를 다시 힙으로 만듬

그리고 또 맨 앞에 있는 루트를 뒤로 보냄 (최댓값 한 자리 앞에) 이걸 반복함

요약

  1. 배열을 힙 화 (Heapify)
  2. 배열에서 i(n-1, n-2, …, 1, 0)번째 데이터를 힙의 최적값으로 바꿈 (HeapSort)
  3. 배열을 다시 처음부터 i-1(n-2, n-3, …, 0)번째 인덱스까지 힙으로 바꿈
  4. 다시 2로…

힙이 제대로 구성되어있기만 한다면, 힙의 루트는 항상 최적값임을 잊지말기!

 
// 배열 a에서 i번째 데이터 까지 힙의 최적값으로 바꿈
// 예시로 오름차순 정렬을 한다고 가정 => 최적값은 최대값
// 자식부터 시작해서 부모와 교환하는 과정을 계속 함
void Heapify(vector<int> &a, int end){
	for(int i = 1; i <= end; i++) {
		int current = i;
		while(current > 0) {
			int parent = (current - 1) / 2;
 
			if(a[parent] < a[current]) swap(a[parent] , a[current]);
			
			current = parent;
		}
	}
}
 
void HeapSort(vector<int> &a){
	for(int i = a.size() - 1; i >= 1; i--) {
		Heapify(a, i);
		swap(a[0], a[i]);
	}
}

계수 정렬

배열 크기가 작을 때 쓸 수 있는 방법 위의 정렬 알고리즘과는 다르게 값을 비교해서 자리를 정하는게 아님 배열 안에 요소가 몇 번이나 등장했는지 그 횟수를 기록함

vector<int> CountingSort(vector<int> &a)
{
    int min = 1; // min(a.begin(), a.end());
    int max = 10; // max(a.begin(), a.end());
    int size = max - min + 1;
 
    vector<int> cnt(size, 0);
    vector<int> result;
 
    for(int i = 0; i < a.size(); i++) cnt[a[i] - min]++;
    for(int i = 0; i < cnt.size(); i++) {
        for(int j = 0; j < cnt[i]; j++){
            result.push_back(i + min);
        }
    }
    return result;
}

버킷 정렬

요소를 일정 간격(버킷)으로 나눠서 저장함 ex. 최소가 1이고 최대가 100인 요소들이 있을 때, 버킷 크기를 10으로 함 한 버킷 안에 요소가 여러 개 있을 수 있는데, 그건 정렬함

따라서, 비 비교 알고리즘 안에 비교 알고리즘으로 구성됨

vector<int> BucketSort(vector<int> &a)
{
    int max = 100;
    int interval = (int)max * 0.2f;
 
    vector<vector<int>> bucket(5);
    vector<int> result;
 
    // 버킷에 담기
    for(int i = 0; i < a.size(); i++){
        int index = a[i] / interval;
        bucket[index].push_back(a[i]);
    }
 
    // 버킷들 정렬하기
    for(int i = 0; i < 5; i++) {
        if(bucket[i].size() == 0 || bucket[i].size() == 1) continue;
        sort(bucket[i].begin(), bucket[i].end());
    }
 
	// 버킷에서 순서대로 빼기
    for(int i = 0; i < bucket.size(); i++) {
        if(bucket[i].size() == 0) continue;
        for(int j = 0; j < bucket[i].size(); j++){
            result.push_back(bucket[i][j]);
        }
    }
 
    return result;
 
}

참고자료

삽입 정렬 코드 참고자료

병합 정렬 코드 참고자료

힙 정렬 코드 참고자료

버킷 정렬 참고자료 버킷 정렬 참고자료 2

문제 해결력을 높이는 알고리즘과 자료 구조

그래프 뷰