목록in-place (1)

코린이의 소소한 공부노트

Quick Sort (partition exchange sort)

1. Problem - n개의 key를 오름차순으로 정렬해보자 - 퀵 정렬은 특정 값(pivot)을 기준으로 그 값보다 작은 것과 큰 것으로 나눠서 정렬한다. 2. Input 1) 양수 n 2) 배열 S 1-indexed 3. Output 1) 오름차순으로 정렬된 S 4. PseudoCode void quicksort(index low, index high){ index pivotpoint; if(low 작은 값(1)의 인덱스 -> 작은 값과 pivot의 위치를 바꾼다. -> 1 {2} 6 3 5 4 // -> pivot이었던 2의 위치는 확정됐고, 2의 위치를 기준으로 왼쪽은 2보다 작은 값, 오른쪽은 큰 값이 된다. // 2를 기준으로 나눠진 왼쪽과 오른쪽에 대해서도 퀵 정렬을 똑같이 진행한다. //..
Back-End/Algorithm 2023. 3. 2. 23:39
이전 Prev 1 Next 다음