---
id: "imported/ps/algorithm/sort/quick"
title: "Quick Sort"
description: "Quick Sort 관련 기록."
kind: "record"
published: "2023-08-07T00:00:00.000Z"
tags: []
url: "https://www.readiz.com/notes/algorithm/sort/quick/"
markdownUrl: "https://www.readiz.com/notes/algorithm/sort/quick/index.md"
---

# Quick Sort

## Quick Sort

```cpp
void qSort(int s, int e) {
    if (s >= e) return;
    int l = s, r = e;
    auto pivot = data[(l+r)/2];

    while(l < r) {
        while(pivot < data[r]) --r;
        while(data[l] < pivot) ++l;
        if (l >= r) break;

        auto tmp = data[l];
        data[l] = data[r];
        data[r] = tmp;

        ++l, --r;
    }
    
    qSort(s, r);
    qSort(l, e);
}
```

## Time Complexity

- Average: $O(N\log N)$
- Worst: $O(N^2)$