[자료구조 및 알고리즘] 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을 하게 된다.
*원하는 자료를 검색 해 보세요.
  • 알고리즘[버블정렬(Bubble Sort), 선택정렬(Selection Sort), 삽입정렬(Insertion Sort), 그예] 6페이지
    문제1. Bubble Sort - 버블정렬(bubble sort)이란? 이름 그대로 거품정렬. 거품처럼 무거운 것은 가라앉고 가벼운 것은 떠오르는 식으로 정렬하는 방법. 느리긴 하지만 정렬 알고리즘의 가장 간단한 개념이어서 정렬하는 기술의 탐구에 있어서 아주 좋은 시작..
  • [프로그래밍. 자료구조] sorting 소스파일 7페이지
    1. insertion sort #include in_sort( int *list ) { int i, j, k ; int next ; for( i = 1 ; i < 9 ; i++ ) { next = list[i] ; for( j = i-1 ; j >=..
  • [자료구조]Sort (Quick, Heap, Merge, Insertion) 8페이지
    ..FILE:merge sort/merge_sort.c #include #define MAX_SIZE 10 #define SWAP(x,y,t)((t)=(x), (x)=(y), (y)=(t)) typedef struct{ int key; }element;..
  • [정렬]Sort의 개념. 11페이지
    1. Sort 개요 ⑴ Sort의 목적 Sort(정렬)란 불규칙한 자료를 일정 기준에 따라 순서적으로 나열하는 것을 말한다 Sort의 목적은 검색(search)시 속도를 빨리하며 여러 파일에서 자료들의 일치를 검사(verify)할 때 유리하며 또 최적화(Optimiza..
  • [프로그래밍 c언어자료구조]SORT 정렬알고리즘의 최종판 6페이지
    ..FILE:insert_sort.c /* DESC : INSERT SORTING INTERFACE MADE : DATE : 2003. 11. 28 */ #include #include #include #includ..
  • [정렬 알고리즘] SORT 알고리즘 7페이지
    //sorting 알고리즘.. kim ki hoon.. #include #include #include #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t)) #define MAX_SIZE..
  • 각종 정렬 성능분석(insert sort, quick sort, heap sort, merge sort) 9페이지
    1. 수행시간 비교 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 Insertion 218 937 2093 3609 5750 8296 11750 15718 18828 23703 quick 0 0 0 15 1..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [자료구조 및 알고리즘] Quick/Heap/Insertion/Stooge Sort