Developer Ahn

- BFS (Breadth First Search)

- 큐를 사용하여 구현 가능

- visited 정보 필요

-  시간복잡도

  : 정정의 수 n, 간선의 수 e
  : 인접 리스트 
  : 인접 행렬 

- DFS (Depth First Search)

- 재귀, 스택을 사용하여 구현 가능

- 스택을 이용하여 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

- visited 정보 필요

-  시간복잡도
  : 정정의 수 n, 간선의 수 e
  : 인접 리스트 
  : 인접 행렬

- 정렬 알고리즘 시간 복잡도

- 정렬 알고리즘별 실험 결과

- 정렬 알고리즘별 안정성, 추가 메모리 필요 여부

- 안정성 있는 정렬 : 같은 값을 가진 데이터의 순서가 정렬 후에도 바뀌지 않고 그대로 유지하는 정렬

출처: http://wonjayk.tistory.com/225

- radix sort

- 기수(radix)는 숫자의 자릿수, 숫자의 버켓(bucket)은 10개, 알파뱃의 버켓은 26개

- 이라는 이론적인 하한선을 깰 수 있는 유일한 기법

- 시간복잡도 : O(dn)

- But, 추가적인 메모리 필요하고, 레코드의 타입이 한정 (동일한 길이를 가지는 숫자나 문자열로 구성)

- 배열을 힙으로 변환 (삽입에 , n개 삽입)

- 루트에서 하나씩 추출 (삭제에 , n개 삭제)

- 시간 복잡도: 

- quick sort
 

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 합병 정렬과 달리 비균등하게 분할

- 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고 피벗을 기준으로 분할

- 속도가 빠르고 추가 메모리 공간을 필요로 하지 않음, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인

- 시간 복잡도 분석
 : 재귀 호출의 깊이는 
 : 각각의 패스에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐, 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시
 : 총 시간 복잡도는 

- 단점으로
 : 정렬된 리스트에 대해서는 오히려 수행시간이  되버리는 불균형 분할 발생 -> 단순히 왼쪽 데이터를 피벗으로 사용하지 않고 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하여 극복 (왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간값을 선택하는 방법(median of three)

- CODE

#include < iostream>
using namespace std;

int arr[1000001];

int partition(int *a, int low, int high) {
	int pivotIndex = low + (high - low) / 2;
	int pivotValue = arr[pivotIndex];
	swap(arr[pivotIndex], arr[high]);
	int pos = low;
	for (int i = low; i < high; i++) {
		if (a[i] < pivotValue) {
			swap(a[i], a[pos]);
			pos++;
		}
	}
	swap(arr[pos], arr[high]);
	
	return pos;
}

void quicksort(int *a, int low, int high){
	if (low < high) {
		int pivot = partition(a, low, high);
		quicksort(a, low, pivot - 1);
		quicksort(a, pivot + 1, high);
	}
}

int main()
{
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	quicksort(arr, 0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

- merge sort

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

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

- 시간복잡도 분석
 : 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산이 수행되지 않는다. 재귀 호출의 깊이는 
 : 합병단계에서 비교 연산 최대 n번, 임시 배열에 복사했다가 다시 가져와야하는 이동 연산 n 번으로 총 2n번 레코드의 이동 발생
 : 총 시간 복잡도는 

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

- 단점으로
  : 임시 배열이 필요함
  : 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래 -> 연결리스트로 극복

- CODE

#include <iostream>
using namespace std;

int arr[1000001];
int save[1000001];

void merge_sort(int* a, int start, int end) {
	if (start == end) {
		return;
	}
	else if (start + 1 == end) {
		if (a[start] > a[end]) {
			swap(a[start], a[end]);
		}
		return;
	}

	// divide
	int mid = (start + end) / 2;
	merge_sort(a, start, mid);
	merge_sort(a, mid + 1, end);
	int left = start;
	int right = mid + 1;
	int k = 0;

	// conquer
	while (left <= mid && right <= end) {
		if (a[left] <= a[right]) {
			save[k++] = a[left++];
		}
		else {
			save[k++] = a[right++];
		}
	}
	while (left <= mid) {
		save[k++] = a[left++];
	}
	while (right <= end) {
		save[k++] = a[right++];
	}

	// combine
	for (int i = start; i <= end; i++) {
		a[i] = save[i - start];
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	merge_sort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";

	return 0;
}

- shell sort

- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것을 착안한 방법

- 셸 정렬은 삽입 정렬의 보다 빠르다.

- 전체의 리스트를 한 번에 정렬하지 않고, 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬

- gap만큼 떨어진 요소들을 삽입 정렬하고, gap을 반씩 줄여가면서 1까지 반복

- 최악의 경우의 시간복잡도 지만 평균적인 경우는 로 삽입 정렬보다 빠르다

출처: http://wonjayk.tistory.com/220

- bubble sort

- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행

- 시간 복잡도 : 로 항상 일정

- 코드

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

- insertion sort

- 오른쪽 리스트(정렬 안 된)에서 왼쪽 리스트(정렬 된)로 하나씩 자리를 찾아 삽입하면서 정렬

- 삽입을 위해 배열을 계속 이동시켜야 함

- 자료가 이미 정렬되어 있는 경우의 시간 복잡도 : 
  자료가 역순일 경우 최악의 복잡도 : 


- 코드

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    j = i;
    remember = data[j];
    while ( --j >= 0 && remember < data[j] )
        data[j+1] = data[j];
    data[j+1] = remember; 
  }
}