[자료구조] 정렬과 탐색(2) - 퀵, 합병, 이진탐색

1. 퀵 정렬(분할정복법)

 

1) 과정

- 리스트에 원소 하나를 고른다(피벗)

- 피벗과 다른 n-1개 원소 각각을 비교하여, 피벗보다 작은 것과 큰 것으로 분할한다.

- 분할된 두 개의 작은 리스트를 재귀적으로 정렬한다.

 

2) 피벗 선택방법

- 중앙값(최선 피벗)

- 랜덤선택

- 리스트 맨앞, 중간, 맨뒤에 있는 세 원소의 중앙값을 선택

 

3) 코드

void Quick_sort(int arr[],int i, int j)
{
	int n, cnt = 0;
	if (i >= j) return;
	int pivot = arr[(i + j) / 2];
	int left = i;
	int right = j;

	while (left <= right)
	{
		while (arr[left] < pivot) left++;
		while (arr[right] > pivot) right--;
		if (left <= right)
		{
			swap(arr[left], arr[right]);
			left++; right--;
		}
	}
	Quick_sort(arr,i, right);
	Quick_sort(arr,left, j);
}

int main() {
	int n = 7; //정렬할 원소의 개수
	int arr[] = { 1,7,2,5,6,10,3 };

	Quick_sort(arr, 0, n-1);

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

> 코드 이해하기

피벗은 제일 왼쪽과 제일 오른쪽의 중앙값 입니다. 

left가 right보다 클 때 까지, 

피벗이 left보다 크면 left의 인덱스를 +해주고, 피벗이 right보다 작으면 right의 인덱스를 -해줍니다.

그리고 right이 left보다 크면 두개의 값을 서로 바꿔줍니다. 그리고 인덱스를 +, - 해줍니다.

이러한 과정을 재귀적으로 돌면서 정렬을 하게 됩니다.

 

 

4) 시간복잡도

최선의 피벗일 때 (중앙값일 때) = O(nlogn)

최악의 피벗일 때(최솟값, 최대값일때) = O(n^2)

 

2. 합병 정렬(merge sort)

 

1) 개념

- 모든 배열을 나누고 정렬 한뒤, 합치는 정렬이다.

- 분할정복법

 

2) 코드

void merge(int arr[], int left, int right) {
     
    int L, R, k, a;
    int mid = ( left + right ) / 2;
    L = left;
    R = mid + 1;
    k = left;
 
    while (L <= mid && R <= right)
        tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
 
    if (L>mid) 
        for (a = R; a <= right; a++)
            tmp[k++] = arr[a];
    else
        for (a = L; a <= mid; a++)
            tmp[k++] = arr[a];
     
    for (a = left; a <= right; a++) 
        arr[a] = tmp[a];
     
}
void mergeSort(int arr[], int left, int right) {
     
    if (left == right) return;
    int mid;
    mid = (left + right) / 2;
    mergeSort(arr, left, mid); 
    mergeSort(arr, mid + 1, right); 
    merge(arr, left, right); 
     
}

> 코드이해(이해중...)

REAKWON :: [알고리즘] 병합 정렬 (Merge Sort) 기본 개념과 코드 구현, 설명 (tistory.com)

 

 

3) 시간복잡도 : O(nlogn)

 

3. 이진탐색(Binary search)

- 이진탐색이란 데이터가 정렬되어있을 때 그 배열에서 특정한 겂을 찾는 알고리즘이다.

- 분할정복법

1) 과정

- 중앙값을 피벗으로 정한다

- 피벗과 찾으려는 값과 비교한다.

- 만약 찾으려는 값이 피벗보다 작으면 피벗보다 왼쪽배열에서, 크면 오른쪽배열에서 재탐색한다.

- 목표값을 찾을 때까지 위 과정을 반복한다.

 

2) 코드(재귀함수로 구현)

int Binary_Search(int arr[], int target, int low, int high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return Binary_Search(arr, target, low, mid-1);
    else
        return Binary_Search(arr, target, mid+1, high);
}

3) 시간복잡도 : O(logN)