[정렬] 퀵 정렬 (Quick Sort)

[정렬] 퀵 정렬 (Quick Sort)

---

From Wikimedia Commons, the free media repository (https://commons.wikimedia.org/wiki/File:Quicksort-example.gif)

 

• 퀵 정렬(quick sort)은 기준 키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.
• 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
• 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로 한다. 또한 퀵 정렬은 불안정 정렬에 속한다.
  

 

📔 퀵 정렬 작동원리 (Quick Sort Mechanism)

 

• 적당한 수(피봇, pivot)를 선택한다. 일반적으로 데이터의 총 평균값을 취한다.
• 피봇보다 작은 수들을 피봇 앞으로, 큰 수를 뒤로 이동시킨다. (분할)
• 두 분할된 각각의 데이터를 재귀적으로 각각 정렬한다.
• 분할된 원소가 0개나 1개가 될 때까지 계속 재귀 호출이 반복된다.

💊 알고리즘 복잡도 (Algorithm Complcomplexity)

⏰ 시간 복잡도 (Time Complcomplexity)	O(N log N)
📦 공간 복잡도 (Space Complcomplexity)	O(log N)

---

📄 [정렬] Qucik Sort C++ Source Code

#define SWAP(X, Y, Z) Z=X; X=Y; Y=Z;

/* Quick Sorting */
void QuickSort(int * mArr, int left, int right)
{
	int pivot = mArr[(left + right) / 2]; /* 중심축 */
	int mLeft = left; /* 정렬 대상의 가장 왼쪽 지점 */
	int mRight = right; /* 정렬 대상의 가장 오른쪽 지점 */
	int mTemp = 0;

	while (mLeft <= mRight) /* mLeft와 mRight가 교차하지 않을 때 경우까지 반복한다. */
	{
		while (mArr[mLeft] < pivot) { ++mLeft; } /* pivot 보다 큰 값을 찾는 경우 */
		while (mArr[mRight] > pivot) { --mRight; } /* pivot 보다 큰 값을 찾는 경우 */

		if (mLeft <= mRight) /* mLeft 보다 mRight가 값이 크거나 같은 경우 */
		{
			SWAP(mArr[mLeft], mArr[mRight], mTemp); /* mLeft와 mRight 값을 교환한다. */
			++mLeft, --mRight; /* mLeft 증가, mRight 감소 */
		}
	}

	if (left < mRight) { QuickSort(mArr, left, mRight); }
	if (mLeft < right) { QuickSort(mArr, mLeft, right); }
}

---

📄 [정렬] Qucik Sort Swift Source Code

func QuickSort(array: inout [Int], left: Int, right: Int) {
    
    var mLeft = left, mRight = right
    let pivot: Int = array[(left + right) / 2]
    
    while mLeft <= mRight {
        while array[mLeft] < pivot  { mLeft     = mLeft + 1 }
        while array[mRight] > pivot { mRight    = mRight - 1 }
        
        if mLeft <= mRight {
            array.swapAt(mLeft, mRight)
            mLeft = mLeft + 1
            mRight = mRight - 1
        }
    }
    
    if left < mRight { QuickSort(array: &array, left: left, right: mRight) }
    if mLeft < right { QuickSort(array: &array, left: mLeft, right: right) }
}

---

🚀 REFERENCE

퀵 정렬

퀵 정렬 - 위키백과, 우리 모두의 백과사전