정렬

정렬

제자리(in place) 알고리즘 : 입력 배열 이외의 추가 기억장소의 수가 상수 개를 넘지 않음

안정적(stable) 알고리즘 : 같은 키 값을 가지는 레코드의 상대적인 위치가 정렬 후에도 유지

거품정렬(Bubble Sort)

안정적인 제자리 정렬

시간복잡도

• 평균: O(n^2)

void bubbleSort(int[] arr) {
	int temp = 0;
	for(int i = 0; i < arr.length; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j]<arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

선택정렬(Selection Sort)

제자리 정렬, 불안정 정렬

최소값을 찾아 0번 인덱스부터 차례대로 교환한다.

시간복잡도

• 평균: O(n^2)

void selectionSort(int[] arr) {
    int indexMin, temp;

    for (int i = 0; i < arr.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[indexMin]) {
                indexMin = j;
            }
        }
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
}

삽입정렬

제자리 정렬, 안정적 정렬

시간복잡도

• 평균: O(n^2)

void insertionSort(int[] arr) {
	for(int i = 1 ; i < arr.length ; i++){
		int temp = arr[i];
		int index = i - 1;
		while( (index >= 0) && ( arr[index] > temp ) ) {
			arr[index + 1] = arr[index];
			index--;
		}
		arr[index + 1] = temp;
	}
}

퀵정렬

불안정적 정렬

pivot을 정하고 피봇을 기준으로 왼쪽은 작은 값 오른쪽은 큰값으로 나눈후 분할하여 정렬하는 방식을 재귀로 수행한다.

시간복잡도

• 평균: O(nlogn)
• 최악: O(n^2)

void quickSort(int[] array, int left, int right){
	int i = left, j = right;
	int pivot = array[(left + right) / 2];
	int temp;
	do{
		while (pivot > array[i])
			i++;
		while (array[j] > pivot)
			j--;
		if (i<= j){
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
			i++;
			j--;
		}
	} while (i<= j);

	if (left < j)
		quickSort(array, left, j);

	if (i < right)
		quickSort(array, i, right);
}

힙정렬

불안정정렬

최대 힙 트리나 최소 힙 트리를 구성하여 정렬을 하는 방법

내림 차순일 경우 최대 힙을 구성하여 최대 값을 꺼내어 정렬한다.

오름 차순일 경우 최소 힙을 구성하여 최소 값을 꺼내어 정렬한다.

시간복잡도

• 평균: O(nlogn)
• 최악: O(nlogn)
• 최선: O(nlogn)

자료구조

이진트리

최대 두 개의 자식 노드를 가지는 트리 자료 구조

탐색

• in-order(중위순회): 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.
• pre-order(전위순회): 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.
• post-order(후위순회): 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.

힙트리

완전이진트리로 이루어진 트리이다.

최대 힙 트리는 부모 노드의 값은 자식 노드의 값보다 항상 커야하고, 최소 힙 트리는 부모 노드의 값이 자식 노드의 값보다 항상 작아야한다.

시간 복잡도

• 최대값(최소값) 찾기: O(1)
• 데이터 삽입 및 삭제: O(logn)

B트리

이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자 M이 2보다 큰 트리 구조이다.

조건

모든 단말노드는 동일한 높이를 가진다.

각 내부노드의 자식노드는 M/2 이상 M이하이다.

루트의 자식 수는 2이상이다.

삽입

부적절한 상태에 있는 노드란, 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드를 의미한다.

• 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입한다.
• 부적절한 상태의 노드가 없다면, 삽입 과정을 종료한다.
• 만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리한다. 이 과정을 반복적으로 트리를 타고 올라가며 진행한다. 만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다.