분할 정복 기법을 사용합니다. 그 상태로 문제를 해결하지 못할 때 작게 쪼개어 해결하는 거죠.

[4,1,7,6,5,8,2,3] 어떠한 한 숫자를 고릅니다. 기준으로 5를 골랐습니다. 5를 가장 오른쪽으로 보냅니다.

[4,1,7,6,3,8,2,5] 이제 왼쪽에는 기준보다 작은 수가, 오른쪽에는 기준보다 큰 수가 나오도록 조정하여 보겠습니다.

[4,1,7,6,3,8,2,5] 5를 제외한 가장 왼쪽과 오른쪽 수를 조작합니다. 이제부터 규칙은 다음과 같습니다. 집중해서 읽어주세요. 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다. 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히 있습니다. 이렇게 넘어가다가 왼쪽은 기준보다 크고, 오른쪽은 기준보다 작으면 서로 바꿔줍니다.

[4,1,7,6,3,8,2,5] 왼쪽 4는 기준보다 작기 때문에 다음 수로 넘어가고, 오른쪽 2은 기준보다 작기 때문에 가만히 있습니다.

[4,1,7,6,3,8,2,5] 왼쪽 1도 다음 수로 넘어가고, 오른쪽 2는 계속 가만히 있습니다.

[4,1,7,6,3,8,2,5] 왼쪽 7는 기준보다 크고, 오른쪽 2은 기준보다 작기 때문에 서로 바꿔줍니다.

[4,1,2,**6,**3,8,7,5] 왼쪽 6은 기준보다 크기 때문에 가만히 있고, 오른쪽 8은 기준보다 크기 때문에 다음 수로 넘어갑니다.

[4,1,2,6,3,8,7,5] 왼쪽 6은 기준보다 크고, 오른쪽 3은 기준보다 작기 때문에 서로 바꿔줍니다.[4,1,2,3,6,8,7,5] 이제 더 이상 비교할 수가 없네요. 왼쪽과 오른쪽 수가 만났습니다.[4,1,2,3,6,8,7,5] 그러면 만난 수인 6과 기준인 5를 바꿔줍니다.[4,1,2,3,5,8,7,6] 이제 5를 기준으로 왼쪽에는 5보다 작은 수가, 오른쪽에는 5보다 큰 수들만 남았습니다.

아직 정렬이 완료되지 않았기 때문에 끝이 아닙니다. 

이제 5를 기준으로 왼쪽([4,1,2,3]), 오른쪽 배열([8,7,6])로 나누어 재귀적으로 퀵 정렬을 해줍니다. 

이렇게 계속 하면 정렬이 완료됩니다.

const unorganizedArray = [4, 1, 7, 6, 3, 8, 2, 5];

function partition(array, left, right, pivotIndex) {

    while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어갑니다.

        if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면 서로 바꿔줍니다

    // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 i입니다.

function quickSort(array, left, right) { // 재귀하는 부분

    if (!right) right = array.length - 1;

    let pivotIndex = right; // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.

    pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.

        quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀

        quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀

평균 O(NlogN) →평균 O(logN) 상수 부분의 시간 복잡도는 무시

O(N) → O(1) 상수 이므로 공간 복잡도 무시

https://www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4

퀵 정렬

Body Parser란?

Express JS란?

Request, Response

Resposne - send(), json(), end()

컨트롤러, 라우터

HTML ELEMENT

데이터 타입

멀티 컬럼 인덱스(Multi-Column Index)

실행계획을 통한 SQL 튜닝

인덱스

Package.json

Tick

Cookie, Session

HTTP

링크

링크

퀵 정렬