[Algorithm]기본 정렬 알고리즘

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다.

 

서론

 예전에 취업준비를 하면서 코딩 테스트 연습을 한 적이 있습니다. 코딩 테스트 출제 문제는 수학적 사고가 필요한 Dynamic programming이나 트리 같은 자료구조 등 다양 하지만 데이터의 정렬과 탐색이 꽤나 많았던 걸로 기억합니다.

이번 글에서는 기본적인 정렬 알고리즘 몇가지를 다뤄 보려 합니다.

다루는 주 내용은, 알고리즘의 특징과 시간 복잡도 그리고 간단한 코드 예시 입니다.

---

선택정렬

• 시간 복잡도 : O(n^2) 공간 복잡도 : O(n)
• 현재 위치에 들어갈 자리를 선택해 정렬하는 방식
• 로직
  1. 제일 앞에서 부터, 배열값 중 가장 작은 값을 찾음
  2. 찾은 가장 작은값을 현재 인덱스와 교체
  3. 위 과정 반복
• 코드 예시

void selectionSort(vector<int> v){
	int vecSize = v.size();
	for(int i = 0; i < vecSize; ++i){
    	int temp = i;
        for(int j = (i+1); j < vecSize; ++j){
        	if(v[temp] >= v[j]){
            	temp = j;
            }
        }
        swap(v[i], v[temp]);
    }
}

---

삽입정렬

• 현재 위치에서 아래 배열들을 비교하여 찾아들어갈 위치를 찾아 그 위치에 삽입하는 방식
• 시간 복잡도 : 최악 O(n^2), 이미 정렬된 경우 O(n) 공간 복잡도 : O(n)
• 로직
  • 첫번째가 아닌 두번째 인덱스부터 시작, 비교 인덱스는 현재 인덱스의 -1
  • 비교 인덱스와 별도로 저장해둔 삽입을 위한 값을 비교
  • 삽입을 위한값이 더 작을 경우 들어갈 자리를 -1 씩 감소
  • 삽입 변수가 더 크면 비교 인덱스의+1 자리에 값을 삽입
• 코드 예시

void insertionSort(vector<int> v){
    for(int i = 0; i < v.size(); ++i){
    	int key = v[i];
        int j = i - 1;
        while(j >= 0 && key < v[j]){
        	swap(v[j], v[j+1]);
            j--;
        }
        v[j+1] = key;
    }
}

---

버블정렬

• 연속된 두개의 값들을 비교하여 정한 기준(오름, 내림차순)의 값을 교체하는 방식
• 시간 복잡도 : O(n^2) 공간 복잡도 : O(n)
• 로직
  • 현재 인덱스와 바로 다음 인덱스를 비교
  • 정한기준에 따라 비교 인덱스가 작거나 크면 교체
  • 정한기준에 따라 비교 인덱스가 크거나 작으면 교체하지 않고 다음 연속된 두개로 넘어감
  • 이를 전체 배열의 크기 - 현재까지 순환한 바퀴 수 만큼 반복
• 코드 예시

void bubbleSort(vector<int> v){
    int vecSize = v.size();
    for(int i = 0; i < vecSize; ++i){
    	for(int j = 1; j < vecSize - 1;++j){
        	if(v[j-1] > v[j]){
            	swap(v[j-1], v[j]);
            }
        }
    }
}

---

병합정렬

• 분할 정복방식으로 설계됨. 큰 문제를 반씩 쪼개 문제를 해결해 나가는 방식
• 시간 복잡도 : O(n*log n)
• 로직 과정(분할)
  1. 현재 배열을 반으로 나눔
  2. 각각의 시작위치와 끝 위치를 받아 중간 지점을 찾음
  3. 이 과정을 나뉜 배열의 크기가 1이하 일때까지 반복

void mergeSort(vector<int>& v, int s, int e){
	if(s < e){
    	int  m = (s+e)/2;
        mergeSort(v, s, m);
        mergeSort(v, m+1, e);
        merge(v, s, e, m);
    }
}

• 로직 과정(합병)
  1. 나눈 배열의 크기를 비교하고 각각의 현재 인덱스를 가정
  2. 현재 인덱스중 하나는 나뉜배열중 하나의 시작 위치를, 나머지 현재 인덱스에는 다른 배열의 시작 위치를 지정
  3. 각각 현재위치에 있는 값들을 비교하고 기준에 따라 알맞은 값을 새로운 배열의 시작 위치부터 저장
  4. 저장된 값의 원래 위치를 하나씩 증가시키며 각 배열의 끝에 도달할때까지 반복
  5. 최종적으로 완성된 임시 배열의 값을 원래 배열에 저장

 

void merge(vecotr<int>& v, int s, int e, int m){
    vector<int> ref;
    int i = s;
    int j = m + 1;
    
    while(i <= m && j <= e){
    	if(v[i] < v[j]){
        	ref.push_back(v[i++]);
        }else if(v[i] > v[j]){
        	ref.push_back(v[j++]);
        }
    }
    
    while(i <= m){
    	ref.push_back(v[i++]);
    }
    while(j <= e){
    	ref.push_back(v[j++]);
    }
    
    int index = 0;
    for(int k = s; k <= e; ++k){
    	v[k] = ref[index++];
    }
}

 

---

퀵 정렬

• 합병 정렬과 마찬가지로 분할 정복을 이용하여 정렬을 수행 피봇이라는 기준을 설정하여 해당 피봇보다 작은값은 왼쪽 큰값은 오른쪽으로 보내는 방식
• 시간 복잡도 : O(n*log n), 최악(이미 정렬된 배열의 경우) O(n^2) 공간 복잡도 : O(n)
• 로직
  • 피봇을 하나 정한다 (일반적으로 맨앞, 맨뒤, 전체의 중간값, 랜덤 값)
  • 분할 전에 왼쪽 배열을 저장할 변수와 오른쪽 배열의 인덱스를 저장할 변수를 지정(L, R)
  • L에는 피봇보다 작은 인덱스를 R에는 피봇보다 큰 인덱스의 값을 저장
  • 분할된 두개의 리스트에 대해 재귀적 호출(혹은 반복)을 통해 이 과정을 반복
• 코드 예시

void qsort(vector<int>& v, int s, int e){
    int pivot = v[s];
    int bs = s;
    int be = e;
    
    while(s < e){
    	while(pivot <= v[e] && s < e){ e--; }
        if(s > e){ break; }
        while(pivot >= v[s] && s <e){ s++; }
        if(s > e){ break; }
        
        swap(v[bs], v[e]);
    }
    
    swap(v[bs], v[s]);
    
    if(bs < s){
    	qsort(v, bs, s - 1);
    }
    
    if(be > e){
    	qsort(v, s + 1, be);
    }
}

---

힙 정렬

• 힙 트리를 이용한 알고리즘 최소 힙 구성 : 오름 차순 최대 힙 구성 : 내림 차순
• 시간 복잡도 : O(n*lon n)
• 로직
  • N개의 노드에 대한 완전 이진트리를 구성(왼쪽에서 오른쪽으로 단말 노드를 채운 트리, h-1 까진 포화 이진트리)
  • 부모노드가 자식노드 보다 큰 트리(최대 힙) 부모노드가 자식노드보다 작은 트리(최소 힙)
  • 힙에 대하여 삭제 연산을 수행하여 삭제한 원소를 배열의 마지막 자리에 배치
  • 나머지 노드에 대하여 힙 트리 재구성
  • 모든 노드가 삭제될때까지 반복
• 코드 예시

int data[LENG];

void downHeap(int cur, int k){
    int l, r, p;
    while(cur < k){
    	l = (cur * 2) + 1;
        r = (cur * 2) + 2;
        
        if(l >= k && r >= k) { break; }
        
        p = cur;
        if(l < k && data[p] < data[l]){
        	p = l;
        }
        
        if(r < k && data[p] < data[r]){
        	p = r;
        }
        
        if(p == cur) { break; }
        
        swap(data[cur], data[p]);
        cur = p;
    }
}

void heapIfy(int n){
    int i, p;
    for(int i = (n - 1) / 2; i >= 0; --i){
    	downHeap(i, n);
    }
}

void heap(){
    int k;
    int dataSize = data.size();
    heapIfy(dataSize);
    for(k = dataSize - 1; k > 0;){
    	swap(data[0], data[k]);
        k--;
        downHeap(0, k-1);
    }
}