[알고리즘] Quick Sort

치치·2025년 1월 19일
알고리즘

알고리즘C++

목록 보기
9/24
post-thumbnail

퀵 정렬

  • 기준점을 얻은 다음, 기준점을 기준으로 부분 배열로 나누고, 한쪽은 기준점보다 작은 값들이 위치하고 다른 한 쪽은 기준점보다 큰 값들이 위치하도록 정렬하는 알고리즘이다
  • 나누어진 하위 배열들에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열이 될 때까지 반복하면서 정렬한다

[퀵정렬의 순서]

  1. pivot값을 정한다 (주로 제일 앞 윈소 or 제일 뒷 원소)
    -> 나는 제일 앞의 원소를 pivot 으로 정했다

  2. left와 right를 선언하고 배열에 접근한 두 원소가 pivot 값과 큰지 비교한다
    -> pivot보다 left가 작다면 오른쪽으로 이동(left++)
    -> pivot보다 right가 크다면 왼쪽으로 이동(right--)

  3. left와 right가 더이상 이동할 수 없다면 안쪽while문이 종료된 후 아래의 조건문을 시행한다

  4. start >= end가 되는겨우 재귀함수를 탈출한다

  5. 모든 재귀함수가 종료되면 정렬이 완료된다

이 과정을 파티셔닝 (Partitioning) 이라고 한다


퀵정렬 전체코드

#include <iostream>
#define SIZE 6
using namespace std;

// pivot > left left 이동
// pivot < right right 이동

void QuickSort(int list[], int start, int end)
{
	if (start >= end)
	{
		return;
	}
    
	int pivot = start;
	int left = start + 1;
	int right = end;

	while (left <= right)
	{
		while (left <= end && list[pivot] >= list[left])
		{
			left++;
		}
		while (right > start && list[pivot] <= list[right])
		{
			right--; 
		}

		if (left > right)
		{
			swap(list[pivot], list[right]);
		}
		else
		{
			swap(list[left], list[right]);
		}
	}
    
	QuickSort(list, start, right - 1); 
	QuickSort(list, right + 1, end);


}

int main()
{
#pragma region 퀵 정렬

	int list[SIZE] = { 4,5,6,2,3,1 };

	QuickSort(list, 0, SIZE - 1);

	for (const int& element : list)
	{
		cout << element << " ";
	}

#pragma endregion


	return 0;
}

출력값: 1 2 3 4 5 6 (오름차순 정렬 완료)


과정 자세히 살펴보기

양쪽 부분 배열을 모두 살피는 예시

  • 예시로 배열의 원소는 {5, 3, 8, 4, 9, 1, 6, 2, 7}로 정하였다
  • 1회차가 종료되고 기존의 pivot값을 가리키고 있는 right자리를 기준으로 다시 재귀함수를 실행하게 된다
  • 원소 5는 이미 정렬되어서 더이상 건드리지 않음!

  1. 1회차

  2. pivot을 기준으로 두 부분 배열로 나눈 2회차
    -> 각각의 부분배열이 또 나누어져 pivot을 기준으로 정렬된다


코드 자세히 살펴보기

  1. 인자로 배열을 받고, start값과 end값을 받는다
    -> 초기값으로 start는 배열의 첫번째 요소를 가리키고, end는 마지막 원소인 SIZE - 1을 가리킨다

  2. 우리는 재귀적으로 퀵정렬을 수행하기 때문에 반드시 재귀함수를 종료할 수 있는 조건문이 필요하다

start >= end인 이유!

  • 재귀적으로 배열의 크기가 1이 될때까지 쪼개는 과정을 수행하는데, 배열의 크기가 1일때 start == end가 된다. 더 이상 쪼갤 필요가 없기에 재귀함수를 탈출한다

  • 퀵정렬을 수행하다 재귀함수도 호출할때 start > end가 되는 상황이 발생하기도 한다

    1. 예를 들어, 퀵정렬을 수행하다가 pivot값과 교체한 곳이 end인 경우, 새로 재귀를 호출할때 기준이 end위치(right)에 있는 pivot값을 기준으로 반씩 나눠진다

    1. 재귀를 호출할때의 범위가 왼쪽은 start ~ right - 1, 오른쪽은 right + 1 ~ end인데 pivot이 end로 끝나버리면 start는 그대로 right + 1이지만 end가 start의 이전위치에 있다
      -> 이 의미는 오른쪽 배열이 비어있다는 것!!
      -> 재귀를 호출 할 필요가 없어서 종료조건이 된다

start > end 상황도 정상 실행은 되는이유!

  • 이 경우는 배열의 크기가 1이 되었을 상황이 아닌, 배열이 아예 비었을때만 종료되는 것임
  • 그렇기 때문에 배열의 크기가 1일때 재귀함수가 호출이 된다
  • 배열 크기가 1일때 start == end일텐데 그럼 재귀함수로 다시 start와 end가 지정될텐데 그때 start > end 조건이 되어서 재귀 탈출이 되는 것
    -> 결국 재귀함수를 한번 더 호출하고 종료되기 때문에, 비효율적이다 (그냥 등호쓰자)

  1. 변수를 설정하고 초기화 한다
    -> pivot값은 재귀를 호출할때마다 가장 앞의 값으로 결정하도록 했다
    -> left와 right는 다음과 같다

  2. 내가 가장 어려워했던 부분인 함수내의 pivot값과 비교하여 값을 swap하고 종료되는 조건문이다 (정말 진짜 오래걸렸다)

  • 1. 종료되고 재귀함수가 호출되는 조건

    -> left <= right일때 안에 로직을 수행한다
    -> 4번 코드가 실행되고 난 뒤 1번 반복문을 빠져나온다
    ->left > right가 되면 엇갈린 상황으로 더이상 탐색할 원소가 없는 것!(안의 원소를 다 봤다는 거)

  • 2. pivot값과 left값을 비교해야하는 데, left값이 pivot보다 작다면 left를 이동시킨다

    -> 여기서 left <= end 인 이유!!

    pivot과 값을 비교하다가 left가 end에 도달하는 경우도 생긴다
    만약, left < end 이 상황이 되버리면 left가 right보다 커지는 상황이 발생하지 않게된다!!
    무조건, 무한루프에 빠지지 않기 위해서는 left가 end인 상황에서도 한번은 이동이 가능해야한다
    ->left > right 가 되는 상황을 만들어주어야함

    • 혹시나 의문이 들까봐, left의 값이 배열의 범위를 넘어갔는데 상관없는 이유 :
      left와 pivot값이 변경되는 조건이 아니기 때문에, 범위를 넘어가도 상관은 없다
      만약 right와 같이 pivot값과 변경되어야 해서 접근하는 경우에는 위험하지만, left는 left > right 조건일때 접근하는 게 아무것도 없기 때문에 잘못된 인덱스에 접근할 일도 없다

  • 3. pivot값과 right값을 비교하는 데, right값이 pivot보다 크다면 이동시킨다

    -> 여기서 right > start인 이유!!
    -> left는 등호를 붙였는데 왜 right는 등호를 붙이지 않았을까?

    • right > start조건은 right의 위치가 start에 오면 반복문을 종료한다
    • right가 더 이동해버리면 잘못된 인덱스로 가게되고, 조건문이 만족하면 swap될 가능성이 있기 때문에 등호를 붙이지 않는다
    • left와 다르게 right는 pivot이 접근하여 값을 변경하는 조건을 가지고 있기 때문에 이 경우에 잘못된 인덱스로 접근하게 될 수 있다

  • left > right 조건문

    left > right는 1번 반복문을 빠져나오는 조건이기도 하다

    1. 엇갈린 상황이 발생하면 pivot값과 right값이 바뀌고 바깥 반복문도 종료된 뒤 재귀함수가 호출된다
    1. 그러면 새로운 부분 배열로 나눠지고, 기준점도 새로 잡혀서 다시 이 과정을 반복한다

  • else문 (left < right) 조건문

    left < right는 아직 바깥 반복문을 빠져나올 수 없음
    따라서 left와 right의 값을 swap한 다음, 계속 퀵정렬을 진행한다(안쪽 반복문(2,3)으로 다시 이동)


기준점(pivot)을 기준으로 부분 배열로 재귀함수 실행

내가 처음에 잘못 이해한 부분이 있다

  1. pivot의 위치를 기준으로 부분 배열을 나누는 줄 알았다

  2. pivot은 단순히 부분 배열의 가장 앞부분을 가리키는 것이고, 우리가 부분 배열로 나누는 기준은 "pivot의 값" 의 위치이다

  3. 쉽게 말하면 pivot의 값은 무조건 right와 교환한다

  4. 그렇다면 다음 부분 배열로 나누는 기준은 right의 위치를 기준으로 하겠지?

  5. 그렇기 때문에 재귀함수의 왼쪽 부분과 오른쪽 부분이 right -1 이고 right +1인것이다


퀵 정렬 시간복잡도

평균, 최선O(NlogN)
계속 쪼개져 나가기 때문에 깊이는 logN, 각 단계별로 연산을 N번 수행하기 때문에
O(NlogN) 시간복잡도가 걸린다
-> 분할정복을 기반으로 한 알고리즘이기 때문

최악O(N²)
기준점(pivot)이 항상 가장 작은 값이나 항상 가장 큰 값으로 선택되어 균등하게 나누어 지지 않을경우, logN으로 깊이가 발생하지 않고 N이 된다
N x N = N ²


퀵정렬 다시보기

left와 right의 이동로직에서 후위증가 후위감소를 조심하자..
right에서 계속 버그 터져서 디버그 찍어봐도 모르겠던데
right++ 했더라... 당연히 터질 수 밖에 없네

#include <iostream>
#define SIZE 8
using namespace std;

void QuickSort(int list[], int start, int end)
{
	// 기준점 재귀함수마다 새로 설정
	int pivot = start;

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

	// 재귀를 탈출 조건(배열의 크기가 1이하)
	if (start >= end)
	{
		return;
	}

	// left > right면 반복문 종료
	while (left <= right)
	{
		// left는 end쪽으로 이동, left값이 더 작으면 이동
		while (end >= left && list[left] <= list[pivot])
		{
			left++;
		}
		// right는 start쪽으로 이동, right값이 더 크면 이동
     	while (start < right && list[right] >= list[pivot])
		{
			right--;
		}

		// 반복문이 종료된 후 값 스왑 & 반복문 종료되고 다시 재귀함수 호출
		if (list[left] > list[right])
		{
			swap(list[right], list[pivot]);
		}

		// left > right가 아닌경우, 바깥쪽 반복문도 종료되지 않기 때문에 
		// 계속 이동하면 값 정렬
		else
		{
			swap(list[left], list[right]);
		}
	}

	// 실제 pivot값이 들어있는 위치는 right의 위치
	QuickSort(list, start, right - 1);
	QuickSort(list, right + 1, end);
}


int main()
{
	int list[SIZE] = { 8,5,2,1,4,3,7,9 };

	QuickSort(list, 0, SIZE - 1);

	for (const int & element : list)
	{
		cout << element << " ";
	}

	return 0;
}
profile
치치
뉴비 개발자
이전 포스트

[알고리즘] 정렬 알고리즘 판단

다음 포스트

[알고리즘] Merge Sort

1개의 댓글

comment-user-thumbnail
JSH1C
2025년 1월 24일

최고에요!

답글 달기