intro

술을 너무 많이 마셨다 \_=
근데 이상하게 평소와 다르게 왤케 잘 들어갔지????
속이 안 좋다.

그래도 거의 6 개월만에 본 건가 올만에 써니 친구들 보고

어제 토요일 스터디 잘하시는 분들도 많고 동기부여가 많이 되는 것 같다.
토요일 아침 10 시라니 !!! 좋다 좋다 :D ~~~

퀵소트

mergeSort 처 분할정복 전략을 사용하는 재귀 알고리즘입니다.

mergeSort 는 분할에는 거의 아무 것도 하지 않고 merge 할 때 중요한 작업이 이루어지는 반면에 /
quicksort 는 반대로 분할 단계에서 모든 것이 이루어지고 합칠 때는 아무것도 하지 않는다.

quickSort 는
이미 정렬 되어 있는 경우 O(n^2) 별로 좋지 않지만
평균 수행시간은 nlongn 상수항이 좋아서
실생활에 빠른 정렬은 병합정렬보다 성능이 좋다!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

array[0...n-1] array[p...r]
array

1. 파티션하기 pivot선정해서 왼/오 나누기
[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]으로 이루어져 있다면

일반적으로 가장 오른쪽을 피봇으로 선정한다.

6을 기준으로 나누기
const left = []
const right = []
for(let i =0; i<length-1; i++){
  if(arr[i]<= arr[arr.length-1]) left.push(arr[i])
  else right.push(arr[i])
}

[2,3,5]6[9,7,11,12,14,10]