해나의 컴공생존기

1. Quick Sort Quick Sort의 알고리즘을 한번 보겠다. 1. 배열에서 하나를 pivot으로 설정한다. 2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다. 3. i와 j가 만날때까지 아래의 과정을 반복한다. 3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다. 3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다. 3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다. 5. 처음부터 j까지, j 다음부터 끝까..

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]