[자료구조 및 알고리즘] 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)이란? 이름 그대로 거품정렬. 거품처럼 무거운 것은 가라앉고 가벼운 것은 떠오르는 식으로 정렬하는 방법. 느리긴 하지만 정렬 알고리즘의 가장 간단한 개념이어서 정렬하는 기술의 탐구에 있어서 아주 좋은 시작..
  • [정렬]Sort의 개념. 11페이지
    1. Sort 개요 ⑴ Sort의 목적 Sort(정렬)란 불규칙한 자료를 일정 기준에 따라 순서적으로 나열하는 것을 말한다 Sort의 목적은 검색(search)시 속도를 빨리하며 여러 파일에서 자료들의 일치를 검사(verify)할 때 유리하며 또 최적화(Optimi..
  • [프로그래밍. 자료구조] sorting 소스파일 7페이지
    자료구조에서 배우는 sorting에 대해 C로 짠 소스코드입니다.실행결과도 같이 올려있어요..
  • [알고리즘]Selection Sort,Insertion Sort,Merge Sort,quick Sort, Quick Sort 종합분석 47페이지
    1)Source code (5개 sorting program + random# 생성 progrlam + 전 과정 실행 main pgm)1-1)Selection Sortvoid selectionsort(int n, int S[]) //선택 정렬{int temp;int i..
  • [정렬 알고리즘] SORT 알고리즘 7페이지
    #include < stdio.h >#include < time.h >#include < stdlib.h >#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))#define MAX_SIZE 20#define MAX_DIGIT 2typedef..
  • [프로그래밍 c언어자료구조]SORT 정렬알고리즘의 최종판 6페이지
    #include #include #include #include #define MAX 10void select_sort(void * data, int n, int element, int(*comp..
  • [자료구조]Sort (Quick, Heap, Merge, Insertion) 8페이지
    #include#define MAX_SIZE 10#define SWAP(x,y,t)((t)=(x), (x)=(y), (y)=(t))typedef struct{int key;}element;element list[];int m;void adjust(ele..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서