📒 갈무리 - 퀵정렬(Quick Sort)

📌 퀵정렬이란?

- 피봇을 기준으로 작거나 같은 값의 데이터는 앞으로, 큰 값의 데이터는 뒤로 이동시켜, 작은 값과 큰 값을 분리해가며 정렬하는 방법이다.(분할정복)

 

📌 직접 구현해 보자...

// C#
    public void QuickSrot(int[] data, int start, int end)
        {
            if (start >= end)  // 원소가 1개인 경우
            {
                return;
            }
            int key = start; // 키는 첫번째 원소
            
            // 인덱스
            int i = start + 1;
            int j = end;
            int temp;

            while (i <= j) // 엇갈릴 때까지 반복
            {
                while (data[i] <= data[key]) // 피봇 값보다 큰 값을 만날 때까지
                {
                    i++;
                }
                // 피봇 값보다 작은 값을 만날 때까지 && start를 넘어가서 찾지 못하게
                while (data[j] >= data[key] && j > start) 
                {
                    j--;
                }
                if (i > j) // 현재 엇갈린 상태면 키 값과 교체
                {
                    temp = data[j];
                    data[j] = data[key];
                    data[key] = temp;
                }
                else
                {
                    temp = data[j];
                    data[j] = data[i];
                    data[i] = temp;
                }
            }
            QuickSrot(data, start, j - 1);
            QuickSrot(data, j + 1, end);
        }
        // 가독성을 위해 각 기능마다 함수로 분리하면 좋지만, 지금은 편의상 간단하게 구현함

 

📌 퀵정렬의 특징

- 다른 정렬 알고리즘에 비해 속도가 빠르다.

- 이미 정렬된 리스트에 대해서는 수행시간이 더 오래 걸린다.

- 평균 속도는 O(N*LogN)이다.

- 피봇값을 설정하는 것에 따라서 최악의 경우에는 O(N²)의 시간이다.

- 수행 절차에 있어서 분할이 되어가며 수행이 되면 속도가 빠르게 동작할 수 있지만 그렇지 못하면 비효율적으로 동작될 수 있다.

 

💡 TIP

정렬할 데이터의 특성에 따라서 적절한 알고리즘이 사용하는 것이 중요하다.