20181113

정렬 알고리즘

퀵 소트

  • 가장 많이 사용되는 방법.
  • 분할정복 방식으로 재귀적으로 호출.
  • 불안정 정렬.
  • 피봇 값을 기준으로 가장 왼쪽부터 left 인덱스는 증가하며 피봇 값보다 큰 값을 보면 홀드.
    • 가장 오른쪽부터 right 인덱스는 감소하며 피봇 값 보다 작은 값을 보면 홀드.
    • 스왑, left 인덱스 1 증가, right 인덱스 1 감소.
    • 위 행위를 반복하다가, left 인덱스가 right 인덱스를 지나칠 경우(left > right)
      • left 인덱스를 기준으로 분할(start ~ left, left+1 ~ end)하여 재귀.
  • O(nlogn) 시간복잡도를 가진다.
    • 최악의 경우 n^2 의 시간복잡도.
      • 고르는 피봇 값마다, 가장 큰 값이나 가장 작은 값일 때 최악.
	static void quick(int[] arr, int start, int end) {
		int part = partition(arr, start, end);
		if(part - 1 > start) quick(arr, start, part-1);
		if(end > part) quick(arr, part, end);
	}
	
	static int partition(int[] arr, int start, int end) {
		int pivot = arr[(start+end) / 2];
		while(start <= end) {
			while(arr[start] < pivot) start++;
			while(arr[end] > pivot) end--;
			if(start <= end) {
				int temp = arr[start];
				arr[start] = arr[end];
				arr[end] = temp;
				start++;
				end--;
			}
		}
		return start;
	}

머지 소트

  • 안정 정렬.
  • 분할 정복 방식으로 재귀적으로 호출.
  • 개념
    • 배열을 계속해서 균등하게 분할
    • 작은 단위 배열 두 개를 비교해서 정렬하여 합병.
    • 반복.
  • 추가적인 메모리 공간이 필요하다.
  • 최악의 경우에도 O(nlogn)
	static void mergeSort(int[] arr, int[] temp, int start, int end) {
		if(start < end) {
			int mid = (start + end) / 2;
			mergeSort(arr, temp, start, mid);
			mergeSort(arr, temp, mid+1, end);
			merge(arr, temp, start, mid, end);
		}
	}
	
	static void merge(int[] arr, int[] temp, int start, int mid, int end) {
		for(int i = start; i <= end; i++) {
			temp[i] = arr[i];
		}
		int part1 = start;
		int part2 = mid+1;
		int index = start;
		while(part1 <= mid && part2 <= end) {
			if(temp[part1] < temp[part2]) {
				arr[index] = temp[part1];
				part1++;
			}
			else {
				arr[index] = temp[part2];
				part2++;
			}
			index++;
		}
		for(int i = part1; i <= mid; i++) {
			arr[index] = temp[i];
			index++;
		}
	}

트리

  • Full binary tree
    • 트리가 빈 노드 없는 완전 이진 트리.
  • Complete binary tree
    • 마지막 레벨을 제외하면 빈 노드가 없으며,
      • 마지막 레벨에서 오른쪽 부터 연속된 몇 개가 빈 노드일 수 있다.

힙

  • complete binary tree 이면서 heap property를 만족한다.
    • max heap property : 부모는 자식보다 크거나 같다.
    • min heap property : 부모는 자식보다 작거나 같다.
  • 동일한 데이터를 가진 힙이 존재할 수 있다.
    • 즉, 힙은 유일하지 않다.