JS 노트 퀵정렬

퀵정렬
.
시간복잡도
Best : o(n**2) Worst : o(nlog2n)
.
Pivot(기준)값을 정해서 기준값을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 2개의 그룹으로 나누어 마지막에 병합하여 정렬한다.

let 입력값 = [1, 3, 4, 2, 14, 9, 10, 12]

function 퀵정렬(입력배열){
  let 입력배열의길이 = 입력배열.length
  if(입력배열 <= 1){
    return 입력배열
  }

  let Pivot = [입력배열.shift()]
  let 그룹하나 = []
  let 그룹둘 = []

  for(let i in 입력배열){
    if(입력배열[i]<Pivot){
      그룹하나.push(입력배열[i])
    }else{
      그룹둘.push(입력배열[i])
    }
  }
  return 퀵정렬(그룹하나).concat(Pivot, 퀵정렬(그룹둘))
}


console.log(퀵정렬(입력값))

해설:
재귀함수사용
입력값의 길이가 1보다 작거나 1이면 입력배열을 그대로 return
.
기준값을 배열의 첫번째로 정함.
Pivot 값을 입력배열의 1번째 값을 shift() 해준다.
.
for in 문으로 입력배열[i]를 할 경우 그 i가 위치한 인덱스의 값을 반환해줌.
.
입력배열[i]번재의 값이 기준값 보다 작으면 left에 push 해주고
그렇지 않다면 right에 push 해줌.
.
마지막에 재귀함수로 그룹하나의 값과 Pivot 값, 그룹둘을 합쳐줌.

concat MDN
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/concat

기존배열을 변화하지 않고
그대로 두 배열을 합침.