1. Quick Sort 이는 merge sort와 다르게 추가 배열을 만들지 않아도 된다. quick sort의 알고리즘은 아래와 같다. 1. 배열에서 어느 한 값을 pivot으로 설정한다. 2. pivot을 기준으로 왼쪽은 pivot보다 작게 오른쪽은 pivot보다 큰 숫자가 들어가도록한다. 3. pivot을 기준으로 왼쪽과 오른쪽을 나눠서 재귀를 실행시킨다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]