[C언어]SORT & SEARCH

소개글

C언어 수강시 제출했던 레포트 입니다
SORT와 SEARCH에 대해 조사하였고
마지막에 그에 대한 프로그램을 만들어 첨부하였습니다.
글씨 포인트 10으로 35페이지 입니다.

목차

♣정렬(Sort)♣
1. 정렬의 분류
2. 선택 정렬
3. 버블 정렬
4. 삽입정렬
5. 셸 정렬
6. 합병정렬
7. 쾌속 정렬
8. 외부 정렬
9. 버켓 정렬과 셈 정렬
10. 기수 정렬

♣탐색(Search)♣
1. 키, 레코드, 탐색
2. 이진탐색(Binary Search)
3. 보간탐색(補間探索, Interpolation Search)
4. 이진 탐색트리
5. 기수탐색(基數探索, Radix Search)

♣ Programig ♣

본문내용

1. 정렬의 분류
정렬(Sorting)의 대상은 레코드(Record, Structure)들이다. 레코드 내부의 여러 필드 중 정렬의 기준이 되는 것은 키 필드(Key Field)다. 레코드는 하나 이상의 키 필드를 가질 수 있다. 이들 중 정렬의 기준이 되는 필드를 정렬 키(Sort Key)필드라고 한다. 정렬은 오름차순(Ascending Order)과 내림차순(Descending Order)으로 나뉜다. 오름차순은 2, 5, 7, 11...처럼 키 값이 증가하는 순서로 정렬하는 것이고 내림차순은 11, 7, 5, 2...처럼 키 값이 감소하는 순서로 레코드를 정렬하는 것이다. 내림차순은 오름차순의 논리를 뒤집기만 하면된다.

정렬을 내부 정렬(Internal Sorting)과 외부 정렬(External Sorting)로 구분할 수도 있다. 정렬할 레코드 모두를 한꺼번에 메인 메모리 내부에 올려놓고 정렬하는 방법을 내부 정렬이라 한다. 반면, 외부 정렬은 정렬할 레코드를 한꺼번에 메인 메모리로 올릴 수 없을 때 사용하는 방법이다. 즉, 정렬할 레코드들에 비해 메인 메모리가 작을 때 가해지는 정렬이다. 외부 정렬에서는 일단 정렬할 레코드들을 외부 기억장치에 놓아둔 상태에서, 메인 메모리가 정렬할 수 있는 양 만큼씩만 갖다가 정렬하고 그 결과를 다시 외부 기억장치에 저장해야한다. 레코드가 메인 메모리와 보조 기억장치를 들락날락하면서(Swapping) 조금씩 정렬 되어가는 방법이다.

정렬을 안정 정렬(Stable Sorting)과 불안정 정렬(Unstable Sorting)로 구분하기도 한다.
[표 1-1]은 학생 신상 레코드에 관한 기록이다. 이 목록은 학년을 키 필드로 해서 이미 오름차순으로 정렬이 완료된 결과이다.

참고 자료

- C++ 자료구조론 [교보문고, Horowitz, Ellis]
- C ․C++로 배우는 자료 구조론 [한빛미디어, 주우석]
- C로 배우는 자료구조와 알고리즘 [기전연구사, 신동완/신동준]
- Naver 지식 in