[자료구조 및 알고리즘] Quick/Heap/Insertion/Stooge Sort

등록일 2002.12.24 MS 워드 (doc) | 9페이지 | 가격 500원

소개글

자료구조 및 알고리즘
서울대학교 전기공학부
심규석 교수님 강좌
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을 하게 된다.
*원하는 자료를 검색 해 보세요.
  • [자료구조 및 알고리즘] [자료구조 및 알고리즘] Treaps 23 페이지
    수학적 귀납법으로 접근해 보자. 먼저 우리는 node가 0개인 treap과 1개인 treap은 unique하다는 사실을 직관적으로 안다. 이제 distinct한 key와 priotity를 가진 node k개의 treap이 un..
  • 퀵솔트 자료구조보고서 1 페이지
    자료구조 설계 문제1.할 것 pivot을 전체 배열의 가운데에 위치한 값으로 선택하는 방법 Pivot을 가운데 값으로 설정한다면 두 개로 나뉜 부분리스트가 같은 크기로 나누어지기 때문에 더 효율적인 알고리즘을 구현할 수..
  • [데이터 구조]C로 쓴 자료구조론 30 페이지
    #include <stdio.h>//여기서부터 아래 세번째줄까지는 헤더파일 #include <stdlib.h> #include <math.h>//여기까지 #define MAX_SIZE 101//MAX_SIZE란 값을 10..
  • 교재집필 자료구조 파트 입니다 52 페이지
    1. 자료구조의 개요 1.1 자료(data)와 정보(information)와의 관계 자료구조가 무엇인지 알기 위해 먼저 `자료`의 개념을 알아보도록 하자. 자료(data)란 현실 세계로부터 단순한 관찰, 측정 등을 통하여 ..
  • 자료구조와 알고리즘을 이용한 사전프로그램 10 페이지
    1. 프로젝트 변경 사항 ① 사전 데이터 자료구조의 변경 먼저, 프로젝트 계획서에 계획이 되어 있던 자료구조는, CString 변수 2개를 저장 할 수 있는 리스트를 이용한 구현이었습니다. 그렇지만 이 방법을 이용해서는 이..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서