[자료구조론] 각각의 정렬 알고리즘 분석

소개글

자료구조론의 핵심인 각 정렬에 관해 분석 해놓은 레포트입니다.

각각의 정렬에 대해 임의의 자료를 생성하여 각 정렬의 수행 시간 측정을

C 언어로 구현해 놓았습니다.

quick , merge, insertion, heap Sorting에 관하여 분석해놓은 레포트입니다.

각 정렬에 대한 개념정리 , 시간복잡도, 소요시간 측정, 각정렬에 대한 비교,

최악의 경우 (worst case)와 최상( best case )의 경우에서의 각 정렬의 비교.

마지막 토의 및 결론입니다.

목차

1. 정렬 알고리즘 소개
2. 각 알고리즘의 소요시간
3. 토의 및 결론
4. 참고문헌
5. 수행화면
6. 소스 코드

본문내용

1. 정렬 알고리즘 소개

1) insertion Sort
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
이다. 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.
앞에서부터 차례로 정렬해 나간다. 값을 비교하여 삽입되는값 보다 클 경우 한칸씩 옆으로 옮긴다.
즉 만약 5, 4, 3, 2, 1과 같은 데이터를 정렬할 경우가 worst 케이스가 된다.
■ 평균 시간 복잡도 : O(n²)

2) quick Sort
퀵 정렬(Quicksort)은 리스트 가운데서 하나의 원소를 고른다. 피벗 앞에는 피벗
보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소
들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 그리고 다시 분할된
........................................

참고 자료

· Fundamentals of Data Structures in C
(저. Horowitz, Sahni, and Anderson-Freed, 출. Computer Science Press)
· Fundamentals of Data Structures in C++
(저. Horowitz, Sahni, and Mehta , 출. Computer Science Press)
· C로 쓴 자료구조론
( Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed [공]著; 이석호 譯 )