[알고리즘] O(nlogn) 정렬

개요

시간복잡도가 O(n log n)인 정렬 알고리즘을 공부하고 복습이 필요하다고 느껴 작성한 글이다. 

여러 종류가 있지만 병합 정렬, 퀵 정렬을 공부하였다. 

 

 

병합 정렬

https://en.wikipedia.org/wiki/Merge_sort

 

 

병합 정렬의 작동 방식은 (오름차순 기준)

1. 배열의 요소가 하나가 될 때 까지 나눈다. 
2. 이웃하는 배열의 요소끼리 크기를 비교한다
3. 원하는 정렬에 맞게 비교한 수를 저장용 배열에 삽입한다. 
4. 한 쌍의 배열의 정렬이 완료되면 저장용 배열에 삽입된 수를 원본 배열에 복사한다.

코드로는 아래처럼 구현할 수 있다.

vector<int> arr;
vector<int> tArr;

void mergeSort(int start, int end)
{
	if (start >= end)
		return;

	int m = (start + end) / 2;

	//배열을 반으로 나눔
	mergeSort(start, m);
	mergeSort(m + 1, end);

	int left = start, right = m + 1, cur = start;

	while (left <= m && right <= end)
	{
		//값을 비교하여 저장용 배열에 삽입
		if (arr[left] > arr[right])
		{
			tArr[cur] = arr[right];
			right++;
		}
		else
		{
			tArr[cur] = arr[left];
			left++;
		}

		cur++;
	}
	
	//정렬중인 두 배열중 아직 정렬이 안된 요소가 있다면 저장용 배열에 일괄 복사
	while (left <= m)
	{
		tArr[cur] = arr[left];
		left++;
		cur++;
	}
	while (right <= end)
	{
		tArr[cur] = arr[right];
		right++;
		cur++;
	}

	//원본 배열에 저장용 배열 복사
	for (int i = start; i <= end; i++)
		arr[i] = tArr[i];
}

 

 

 

퀵 정렬

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

퀵 정렬의 작동 방식은(오름차순 기준)

1. 정렬의 기준으로할 인덱스 pivot을 잡는다.(보통 가장 오른쪽 인덱스)
2. 배열의 시작과 끝에서 부터 한 칸씩 이동하며 피봇을 기준으로 값을 비교한다. 
3. 각각의 값 비교가 피봇보다 큰 값, 작은 값을 만나면 두 값을 교환한다.
4. 만약 두 값 비교가 교차하게 되면 피봇과 배열의 끝에서 시작한 값 비교에 위치한 수를 교환한다.
5. 피봇을 기준으로 배열을 나누어 위의 작업을 반복한다. 

코드로는 아래처럼 구현할 수 있다.

vector<int> arr;

void quickSort(int start, int end)
{
    if (start >= end)
        return;

    int left = start + 1;
    int right = end;
    int temp;

    while (true)
    {
    	//배열의 시작 부터 값 비교
        while (arr[left] < arr[start] && left < end)
            left++;
        ///배열의 끝 부터 값 비교
        while (arr[right] >= arr[start] && right > start)
            right--;
        //각각의 비교가 피봇보다 큰 값, 작은 값을 만나면 두 값을 교환
        if (right > left)
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        else //두 값 비교가 교차할 경우 값 비교 중지
            break;
    }

	//배열의 끝에서 시작한 비교에 위치한 값과 피봇값 교환
    temp = arr[start];
    arr[start] = arr[right];
    arr[right] = temp;

	//피봇을 기준으로 배열을 나누어 위의 작업 반복
    quickSort(start, right - 1);
    quickSort(right + 1, end);
}