[자료구조 및 알고리즘] Quick/Heap/Insertion/Stooge Sort
- 최초 등록일
- 2002.12.24
- 최종 저작일
- 2002.12
- 10페이지/
MS 워드
- 가격 1,000원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
소개글
자료구조 및 알고리즘
서울대학교 전기공학부
심규석 교수님 강좌
2002년도 2학기
정답이 아닐 수 있으니 참고만 하시고
프로그래밍은 스스로 하시길 ^^
목차
1. 프로그래밍하여 제출하였음.
2. Plot graph with random number data sets.
3. Argue that, if n=length[A], then STOOGE-SORT(A, 1, length[A]) correctly sort the input array A[1…n]
4. Give a recurrence for the worst case running time of STOOGE-SORT and a tight asymptotic (theta-notation) bound on the worst-case running time.
5. Compare the worst-case running time of STOOGE-SORT with that of every the other algorithms in the above.
본문내용
3. Argue that, if n=length[A], then STOOGE-SORT(A, 1, length[A]) correctly sort the input array A[1…n]
수학적 귀납법을 이용하여 증명할 수 있다.
n<3인 경우를 base case로 하면, 크기 0이나 1의 배열은 논할 필요가 없고, 크기 2인 경우에는 i=0, j=1이므로 pseudo code의 2번째 줄에서 A[i]>A[j]인 경우 교환이 일어난다. 따라서 n<3인 경우에 STOOGE-SORT는 잘 동작한다.
이제 수학적 귀납법을 이용하여, 크기 n<N일 경우에 STOOGE-SORT가 잘 동작한다고 가정했을 때, n<N+2인 경우에도 STOOGE-SORT가 잘 동작한다는 것을 보이면 된다. n>2인 경우에 STOOGE-SORT은 6번째-8번째 행에 걸쳐서 3번의 recursive call을 하게 된다.
참고 자료
없음