[알고리즘] 이진 검색과 정렬

이진검색

배열에 데이터들이 오름차순으로 정렬되어 저장되어 있습니다. 

 

이진검색은 사전 찾는 방법을 생각하시면 됩니다. 

int binarySearch(int n, char *data[], char *target)
{
	int begin = 0, end = n - 1;
	while(begin<=end)
	{
		int middle = (begin + end) / 2;
		int result = strcmp(data[middle], target);
		if (result == 0)
			return middle;
		else if (result < 0)
			begin = middle + 1;
		else
			end = middle - 1;
	}
	return -1;
}

시간복잡도는 O(log n)입니다. 

 

탐색 범위가 1이하가 되는 순간 루프가 종료됩니다.

 

이를 수식으로 표현하면 n/2^k = 1입니다.

 

양변에 로그를 취하면 k = log n이 됩니다. 따라서 루프는 최대 log n 번 반복됩니다. 

 

시간 복잡도 예제

시간 복잡도	예제
O(1)	상수 시간 연산 (예: 배열 인덱스 접근)
O(log⁡n)	이진 탐색, 반씩 줄어드는 반복문
O(n)	단일 루프 (예: 선형 탐색)
O(nlog⁡n)	퀵 정렬, 병합 정렬
O(n^2)	중첩 루프 (예: 버블 정렬)
O(2^n)	피보나치 재귀 호출
O(n!)	브루트포스 순열

 

버블정렬

void bubbleSort(int data[], int n)
{
	for(int i=n-1; i>0; i--)
	{
		for(int j=0; j<i; j++)
		{
			if(data[j] > data[j+1])
			{
				int tmp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = tmp;
			}
		}
	}
}

 

• 최악의 경우 (O(n^2))
  • 배열이 완전히 내림차순으로 정렬된 경우 → 모든 비교에서 교환 발생.
  • 비교 횟수: (n−1)+(n−2)+⋯+1=n(n−1)2=O(n^2)
• 최선의 경우 (O(n))
  • 배열이 이미 정렬된 경우 → 한 번도 교환이 발생하지 않으면 바로 종료 가능.
  • O(n)번만 반복하면 됨 (최적화 필요).

삽입정렬

void insertion_sort(int n, int data[]) {
    for (int i = 1; i < n; i++) {  // (1) i번째 원소를 정렬된 부분에 삽입
        int tmp = data[i];  // (2) 삽입할 값 저장
        int j = i - 1;
        while (j >= 0 && data[j] > tmp) {  // (3) tmp보다 큰 값들은 오른쪽으로 이동
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = tmp;  // (4) 적절한 위치에 삽입
    }
}

 

 

 

1 5 3 7 9 

 

tmp = data[1];

j = 0;

 

data[1] = 1;

 

첫 번째 원소부터 마지막 원소까지 비교 횟수는 차례대로 0, 1, 2, 3, ..., n-1번 발생. 그래서 총 비교 횟수는 (n-1) + (n-2) + ... + 1로 합계는 n(n-1)/2

이것은 O(n^2)의 시간 복잡도를 가짐.

 

최선의 경우는 O(n)일 것입니다.

 

1. 퀵소트 (Quick Sort)
   • 최선/평균 시간복잡도: O(n log n)
   • 최악 시간복잡도: O(n²)
     퀵소트는 분할정복 알고리즘으로, 배열을 분할하고 각 부분 배열을 재귀적으로 정렬합니다. 최선과 평균적인 경우 O(n log n)의 성능을 보이지만, 피벗 선택이 잘못되면 최악의 경우 O(n²)의 시간이 걸릴 수 있습니다. 최악의 경우는 배열이 이미 정렬되었거나 역순으로 정렬된 경우입니다.
2. 합병정렬 (Merge Sort)
   • 최선/평균/최악 시간복잡도: O(n log n)
     합병정렬도 분할정복 알고리즘으로, 배열을 반으로 나누어 재귀적으로 정렬하고 병합합니다. 병합 과정에서 항상 O(n)의 시간이 걸리고, 나누는 과정에서 O(log n)이 걸리기 때문에 전체 시간복잡도는 O(n log n)입니다. 최악의 경우에도 O(n log n)으로 안정적인 성능을 보입니다.
3. 힙정렬 (Heap Sort)
   • 최선/평균/최악 시간복잡도: O(n log n)
     힙정렬은 힙 자료구조를 사용하여 최대값 또는 최소값을 반복적으로 꺼내어 정렬하는 방법입니다. 힙을 구성하는데 O(n) 시간이 걸리고, 힙에서 원소를 하나씩 꺼내는 데 O(log n)이 걸리므로 전체 시간복잡도는 O(n log n)입니다. 합병정렬과 마찬가지로 최악의 경우에도 O(n log n)을 유지합니다.

요약:

• 퀵소트: 평균적으로 O(n log n), 최악은 O(n²)
• 합병정렬: O(n log n) (모든 경우에 동일)
• 힙정렬: O(n log n) (모든 경우에 동일)