알고리즘 정렬(Sort)과 실행시간

소개

알고리즘 정렬(Sort)과 실행시간

목차

1. 정렬이란?

2. 정렬 알고리즘의 종류와 구현
(1) 삽입 정렬
(2) 거품 정렬
(3) 병합 정렬

3. 각 정렬 함수의 시간 측정 결과
(1) 이미 정렬된 파일의 경우 실행 시간의 비교
(2) 난수 배열에 대한 실행 시간의 비교
(3) 반쯤 정렬된 배열에 대한 실행 시간의 비교
(4) 역순 배열을 정렬하는데 걸리는 실행 시간의 비교
(5) 마지막으로 각 정렬 알고리즘의 평균 실행시간에 대해 정리해 보자.

본문내용

1. 정렬이란?
정렬(sort)이란 컴퓨터 기억 공간내에 순서없이 배열된 자료들 중에서 특정 항목을 키(key)로 하여 키 값에 따라 오름 차순(ascending order) 혹은 내림 차순(descending order)으로 레코드를 재배열하는 것을 말한다.
정렬은 전산학 분야에서 중요한 개념으로 인식되고 있으며, 컴퓨터 내에서 자료들을 처리하는데 소요되는 시간의 대부분은 자료를 탐색하거나 정렬하는데 소요되므로 정보의 탐색을 용이하게 하기 위하여 자료들을 분류(sort)된 상태로 유지해야 한다.
정렬은 수행하는 장소에 따라 구분하면 내부정렬과 외부정렬로 나눌 수 있다. 내부 정렬은 메모리의 빠른 비교와 교환을 이용하기 때문에 속도가 빠르다는 장점이 있으나, 모든 자료를 메인 메모리로 옮겨 놓아야 한다는 부담이 있어 대량의 자료를 처리하기에는 부적합하다. 반면, 외부 정렬은 외부 저장장치에 직접 정렬을 행하기 때문에 속도는 느리지만 메인 메모리를 자료들이 차지하지 않아서 시스템에 무리를 주지 않는다.
정렬은 주어진 상황에 따라 최적의 알고리즘을 선택해야 한다. 다양한 알고리즘이 존재하는데, 최고의 성능을 내기 위해 언제 어떠한 알고리즘을 사용해야 하는지를 결정하는 것이 중요하다. 이를 위해 사용하는 컴퓨터의 시스템 특성, 정렬할 자료의 양, 초기 자료의 양, 키 값의 분포, 작업공간의 크기, 키의 비교 횟수, 자료의 이동 횟수 등이 정렬 알고리즘을 선택할 때 고려해야 할 사항들이 된다.

2. 정렬 알고리즘의 종류와 구현
(1) 삽입 정렬
① 삽입 정렬이란?
삽입 정렬은 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작의 반복에 의해서 정렬하는 방법이다. 이 알고리즘은 간단한 방법에 속하며, 선택 정렬과 함께 가장 많이 사용되는 정렬 방법 중 하나이다.
삽입 정렬은 많은 비교와 적은 교환이 이루어지는 선택 정렬과 다르게 적은 비교와 많은 교환을 한다는 특징을 가진다. 이는 큰 레코드를 정렬시 삽입 정렬은 부적절하지만, 작은 레코드의 배열에 사용하면 좋은 성능을 기대할 수 있다는 것을 뜻한다.

참고자료

· 없음