quick sort

quicksort

= 분할 정복 알고리즘. (그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 것)

1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치하고 뒤에는 피벗보다 큰아이들을 둔다

2. 피벗 앞부분에 대해 quicksort를 한다

3. 피벗 뒷 부분에 대해 quicksort를 한다

(맨 마지막에는 q=마지막 요소 전꺼, r=마지막 요소가 될 꺼고, 그담에는 p=q+1이되는데, 그럼 첫요소여야되는게 맨 마지막인덱스보다 같거나 커지니까 끝나도록함 !! p(맨처음이)>=r(맨마지막)보다 같거나 커지면 종료합니다 (걍 맨처음(p)가 r보다 작아야 실행합니다 ㄱ )

 

• partition !

= pivot으로 한 요소를 고르고, (거의 젤 마지막애로 설정함) (같거나?)작은건 왼쪽, (같거나?) 큰건 오른쪽으로 옮기는 작업, 피벗 인덱스를 리턴함

- 원래 잇던 배열을 -> 새 배열에 넣는작업임 ! (원래 배열에서 인덱스 옮겨가면서 하는게 xx)

- 피벗 앞 뒤는 정렬되지 않음 ^^

-> 과정

1. small과 large라는 변수를 각각 0으로 설정합니다 (=각 큰애들, 작은애들중 마지막 인덱스를 나타내는 값이 될 것입니다)
2. 맨첨 인덱스부터 피벗보다 큰지 작은지 검사합니다
3. 작으면 small인덱스는 +1이 됩니다
4. 크면 large인덱스는 +1이 됩니다
5. 만약 large뒤에 작은친구가 오게 되면 small+1(첫번째 라지)와 large+1(지금 온 작은거)를 swap함!! (SWAP(small+1, large+1))
6. 다하면 (large가 마지막 인덱스이면/small이 마지막 인덱스이면) small+1인덱스가 pivot입니다 ! (그렇게 되어있음) ->pivot=small+1하고 이거리턴하면 됩니다

performance

- partition

: 걍 피벗설정하고 그거랑 배열 전체 비교함 - n번연산하겟지 머

-> Θ(n)

-> 이제는 전체 러닝타임 T(n)을 구해야함

이때 피벗이 가운데에 있어서 partition연산이 balanced일때와, 아닐 때로 나뉨

 

- balanced partitioning vs unbalanced partitioning !

1. balanced partitioning

: 파티션하면 n/2(아래로내림. 가우스)인 친구와 [n/2]-1 ([]=>위로올림)인 두친구로 나뉘게 된다

-> T(n)<= 2T(n/2) + Θ(n) (대충 절반인친구하는데걸리는시간

(앞) + 절반 뒤 친구하는데걸리는 시간 + 맨처음에걸리는 시간Θ(n) =>T(n) !!)

->Θ(nlgn)

2. unbalanced partitioning 

-> 이미 정렬되어있을 경우에는 죄다 small뿐임!! 앞만있고 뒤는 없음 (앞에 n-1인부분만 다시 퀵소트돌리기+뒤는 돌릴게 없음+맨첨 파티셔닝 Θ(n))

-> T(n)=T(n-1)+Θ(n)+T(1) (<-쟤는 걍 0개 퀵소트하는거상수니까 저러캐써놈..)

-> Θ(n^2)

 

-worst-case

-> Θ(n^2) 얘가 워스트 케이스인가? 

]일반적일때를 봐서 그게 워스트케이스인지 확인해본다 ! (T(n)<cn^2 임을 증명. 확인)