[알고리즘] 정렬 알고리즘 (1) (퀵 정렬)

1. 퀵 정렬

1) 개념

: 퀵 정렬이란 가장 많이 사용되는 정렬 알고리즘 중 하나로, 평균적으로 O(n log n)의 시간복잡도를 가지면서 빠르고 효율적임. 

또한, 분할 정복 알고리즘(Divide and Conquer)을 기반으로 작동.

① 피벗을 선택

② 피벗을 기준으로 작은 값과 큰 값으로 나눔

③ 왼쪽과 오른쪽 부분을 다시 퀵 정렬로 재귀적으로 정렬

---

 

2) 시간 복잡도

평균 시간복잡도 - O(n log n)

최악 시간복잡도 - O(n^2) (드물게 발생)

▶ 대부분 빠른 정렬 성능을 제공

---

 

3) C#을 사용한 예시

static void Main(string[] args)
{
    int[] arr = new int[] { 3, 5, 6, 8, 1, 2, 4, 7 };
    QuickSort(arr, 0, arr.Length - 1); // 전체 배열 정렬

    foreach (int i in arr)
    {
        Console.Write(i);
    }
}

public static void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivotIndex = Partition(arr, left, right);
        QuickSort(arr, left, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, right);
    }
}

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right]; // pivot을 배열의 마지막 요소로 변경
    int i = left - 1;

    for (int j = left; j < right; j++) // pivot은 right 요소이므로 right-1까지 비교
    {
        if (arr[j] <= pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, right); // pivot을 올바른 위치로 이동
    return i + 1;
}

private static void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}


// 결과 = 12345678

* static으로 선언되는 이유

: 객체 생성없이 직접 호출이 가능해짐으로써 사용하기 간편하고 메모리 사용을 줄이는 효과도 있음 + 코드 간결함 유지

---

 

4) 과정

(1) 숫자 리스트의 맨 우측의 숫자를 피벗으로 삼는다.

(2) 왼쪽과 오른쪽에서 한칸씩 이동한다.

(3) 피벗을 기준으로 피벗보다 큰값과 작은값이 서로 위치를 바꾼다.

(4) 중앙에서 교차할 경우 해당 위치에 피벗을 대입하면 피벗을 기준으로 좌측은 작은수, 우측은 큰수로 정렬된다.

(5) 재귀함수를 통해 해당과정을 반복한다.

(6) 최종적으로 정렬된 리스트를 얻게 된다.

출처 : https://seongju0007.tistory.com/entry/C-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%80%B5%EC%A0%95%EB%A0%AC

 

---

 

5) 주의점

- 정렬되어 있는 리스트에서는 수행시간이 더 오래 걸린다 O(n^2)