정렬 알고리즘

정렬 알고리즘이란?
n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘

정렬이 일어나는 장소에 따라

내부정렬(internal sorting)
데이터의 크기가 주 기억장소 용량보다 적을 경우 기억장소를 활용하여 정렬하는 방법
- 버블정렬, 삽입정렬, 선택정렬, 퀵정렬, 쉘정렬 힙정렬

외부정렬(external sorting)
데이터의 크기가 주기억장소의 용량보다 클 경우 외부 기억장치를 사용하여 정렬하는 방법
- 머지정렬

 

 

 

---

 

 

 

선택정렬(Selection sort)

현재 위치에 들어갈 값을 찾아 정렬하는 배열

1.  정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾는다.
2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
   
   
3. 다음 인덱스에서 위 과정을 반복해준다.
   
   

이 정렬 알고리즘은 n-1개, n-2개, ...1개 씩 비교를 반복한다.
배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)
공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)

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

 

삽입 정렬(Insertion Sort)
현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아,
그 위치에 삽입하는 배열 알고리즘

1. 삽입 정렬은 두 번째 인덱스부터 시작한다.
   현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
   
   
2. 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
   
   
3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를
   -1하여 비교를 반복한다.
4. 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장한다.
   
   

최악의 경우(역으로 정렬되어있는 경우) n-1개, n-2개, ...1개 씩 비교를 반복하여 시간복잡도는 O(n^2)
이미 정렬되어 있는 경우에는 한번씩밖에 비교를 하지 않아 시간 복잡도는 O(n)이다.
하지만 상한을 기준으로 하는 빅오 표기법은 최악의 경우를 기준으로 평가하므로 삽입 정렬의
시간 복잡도는 O(n^2)이다.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)

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

 

 

버블 정렬(Bubble Sort)
매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법
오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하며,
1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.
맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에,
(전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 만 반복해 주면 된다.

 

1. 삽입 정렬은 두 번째 인덱스부터 시작한다,
   현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
   
   
2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
   
   
3. 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
   
   
4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.
   
   

이 정렬 알고리즘은 1부터 비교를 시작하여 n-1개, n-2개,...,1개씩 비교를 반복하며,
선택 정렬과 같이 배열이 어떻게 되어있던지 간에 전체 비교를 진행하므르 
시간 복잡도는 O(n^2)이다.
공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(n)이다.

 

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

 

 

합병 정렬(Merge Sort)
합병 정렬은 분할 정복(Divide and conquer)방식으로 설계된 알고리즘
분할 정복은 큰 문제를 반으로 쪼개어 문제를 해결해 나가는 방식
분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.

입력으로 하나의 배열을 받고, 연산 중에 두 개의 배열로 계속 쪼게 나간 뒤, 
합치면서 정렬해 최후에는 하나의 정렬을 출력한다.

합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.
오름차순의 경우 배열 A, 배열 B를 비교하여 A에 있는 값이 더 작다면 
새 배열에 저장해주고, A인덱스를 증가시킨후 A,B의 반복을 진행한다.

이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때까지 반복하며,
전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.

 

합병 과정은 두 배열 A,B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우
O(n1+n2)와 같다. 
배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우
N = N1 + N2 이므로 O(N)이라고 할 수 있다.

 

분할 과정은 lgN만큼 일어나는데, 이 이유는 크기가 N인 배열을 분할하면,
한번 분할하면 N/2,N/2 2개, 그 다음 분할하면 N/4,N/4,N/4,N/4 4개
즉 분할 과정은 매번 반씩 감소하므로 lgN만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 O(NlgN)이다.

사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다.

 

 

merge sort는 O(nlongn)

 

 

퀵 정렬(Quick Sort)
퀵 정렬 또한 분할 정복을 이용하여 정렬을 수행하는 알고리즘
pivot point 라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽,

큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.
이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것.

 

 

각 정렬은 배열의 크기 N만큼 비교하여, 이를 총 분할 깊이인 lgN만큼 진행하므로 총 비교횟수는 NlgN, 즉 시간복잡도는 O(NlgN)이다.
다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 pivot point가 계속 0,1 이런식으로 가장 작은 값을 선택할 때이다.

 

 최악의 퀵 정렬일 경우

이 경우 분할이 N만큼 일어나므로 시간 복잡도는 O(N^2)이다.
이를 방지하기 위해 전체 배열 값 중 중간값이나 랜덤 값으로 pivot point를 정하는 방법을 쓰기도 한다.