[알고리즘] 퀵정렬(Quick sort)

---

1. 퀵정렬이란?

데이터들 중 한 숫자를 기준점(pivot)으로 정하고, 기준점보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 분류하여 정렬합니다. 재귀용법을 이용해 작은 단위까지 쪼개어 정렬한 후 합치는 방식입니다.

 

---

2. 퀵정렬의 구현

병합정렬을 배우고 나니 퀵정렬은 조금 더 쉬웠습니다.

public List<int> quickSort(List<int> list)
{
    if (list.Count <= 1) return list;
    int pivot = list[0];
    List<int> left_List = new List<int>();
    List<int> right_List = new List<int>();
    for (int i = 1; i < list.Count; i++)
    {
        if (pivot >= list[i]) left_List.Add(list[i]);
        else right_List.Add(list[i]);
    }

    left_List = quickSort(left_List);
    right_List = quickSort(right_List);

    left_List.Add(pivot);
    left_List.AddRange(right_List);
    return left_List;
}

 

GitHub