[자료구조 및 알고리즘] 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을 하게 된다.
  • 구매평가(0)
  • 구매문의(0)
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.

      찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

      • 파일확장자 [알고리즘, C,C++,자료구조]heap sort 0페이지
        ++){ cout<<v[i]<<endl; } } /* HEAP SORT ... 알고리즘 */ void heapsort(string v[],int n ... 구성하는 알고리즘*/ void siftdown(string v[],int i
      • 파일확장자 [자료구조] Insertion Sort / Merge Sort 알고리즘 구현 1페이지
        Settings\안병준\바탕 화면\Rinijun\Sort.cpp ... _) ..FILE:Sort.cpp // Sort.cpp: implementation ... " #include "Rinijun.h" #include "Sort.h" #ifdef
      • 파일확장자 [자료구조]C C++로 작성한 각각의 sort알고리즘 구현과 시간측정(1/1000s), 성능비교 10페이지
        알고리즘 비교 4. 직접 측정한 sorting결과 비교 (성능 비교) 5 ... 수치화 하여 비교하고자 하는 것입니다. 각각의 sorting 알고리즘 ... 알고리즘에 넣어줍니다. 각각의 알고리즘sorting시간을 알아보기
      • 파일확장자 [프로그래밍 c언어자료구조]SORT 정렬알고리즘의 최종판 6페이지
        ..FILE:insert_sort.c /* DESC : INSERT ... SORTING INTERFACE MADE : DATE : 2003. 11 ... .h> #define MAX 10 void insert_sort(void
      • 워드파일 [자료구조알고리즘] [자료구조알고리즘] Treaps 23페이지
        : *** *** - CLRS book의 296~298쪽에 있는 (a), (b), (c), (d ... RIGHT-ROTATE(T, x)이다. 이것은 CLRS book의 278쪽에 ... , x)와 RIGHT-ROTATE(T, x)이다. 이것은 CLRS
      • 파일확장자 [자료구조] Quick Sort 1페이지
        ..FILE:result_quicksorting.jpg ..FILE:prjQuickSort.dsp # Microsoft Developer Studio Project File - Name="prjQuickSort" - Package Owner=<4> # Microsoft..
      • 워드파일 [자료구조] 힙 정렬( Heap Sort ) 4페이지
        공학부 이름 : 000 학번 : 00000000 개요 자료구조 중 ... 하나인 Heap을 이용한 Sorting알고리즘을 구현하여라. 소스 ... Data Structure Heap Sort - 00대학교 / 컴퓨터
      더보기
      상세하단 배너
      우수 콘텐츠 서비스 품질인증 획득
      최근 본 자료더보기
      상세우측 배너
      추천도서yes24
      다음
      [자료구조 및 알고리즘] Quick/Heap/Insertion/Stooge Sort
      페이지
      만족도 조사

      페이지 사용에 불편하신 점이 있으십니까?

      의견 보내기