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

 

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer)에 바탕을 둔 정렬 방식이다. 퀵 정렬은 기준 요소(Pivot) 선정 및 분할의 반복하는 방식으로 동작한다.

시간복잡도는 평균적으로 O(NlogN)이다.

 

---

퀵 정렬

 

1. Pivot 설정

• pivot > arr[low]일 동안 low를 오른쪽으로 이동
• pivot < arr[high]일 동안 high를 왼쪽으로 이동

2. low < high라면, arr[low]와 arr[high] 데이터 교체

3. high <= low면 빠져나오고, pivot과 arr[high] 교체

 

 

 

 

 

---

 

H3 중제목

본문내용넣기

 

int Partition(vector<int>& v, int left, int right)
{
    int pivot = v[left];
    int low = left + 1;
    int high = right;
 
    while (low <= high)
    {
        while (low <= right && pivot >= v[low])      // 조건문 순서 주의
            low++;
 
        while (high >= left + 1 && pivot <= v[high]) // 조건문 순서 주의
            high--;
 
        if (low < high)
            swap(v[low], v[high]);
    }
 
    swap(v[left], v[high]);
 
    return high;
}

 

void QuickSort(vector<int>& v, int left, int right)
{
    if (left > right)
        return;
    int pivot = Partition(v, left, right);
    QuickSort(v, left, pivot -1);    // 재귀 호출
    QuickSort(v, pivot + 1, right);  // 재귀 호출
}

 

int main()
{
    vector<int> v;
 
    srand(time(0));
 
    for (int i = 0; i < 50; i++)
    {
        int randValue = rand() % 100;
        v.push_back(randValue);
    }
 
    QuickSort(v, 0, v.size() - 1);
 
    for (int i = 0; i < 50; i++)
    {
        cout << v[i] << " ";
    }
}

 

---

 

H3 중제목

본문내용넣기

 

 

 

 

 

---

 

마무리

마무리