정렬 알고리즘 6종 구현 및 비교 분석(선택정렬/버블정렬/삽입정렬/힙정렬/합병정렬/퀵정렬)

소개글

정렬 알고리즘 6종(선택정렬, 버블정렬, 삽입정렬, 힙정렬, 합병정렬, 퀵정렬)에 대해 알고리즘을 구현하고 해당 정렬방법과 시간복잡도 등의 특징을 비교하며 설명합니다.
이 구현 내용을 바탕으로 데이터를 실제 정렬한 실험결과를 분석하고 느낀점을 작성하였습니다.

목차

1. 정렬 알고리즘이란

2. 정렬 알고리즘 종류별 특징
2-1. 선택 정렬 (Selection Sort)
2-2. 버블 정렬 (Bubble Sort)
2-3. 삽입 정렬 (Insertion Sort)
2-4. 힙 정렬 (Heap Sort)
2-5. 합병 정렬(Merge Sort)
2-6. 퀵 정렬 (Quick Sort)

3. 정렬 알고리즘 실험 분석결과

4. 정렬 알고리즘 실험 느낀점

본문내용

1. 정렬 알고리즘이란
: 임의의 자료를 일정한 규칙이나 기준에 따라 배열하는 기법.
주어진 자료를 어떤 기준에 의하여 크기 순서로 배열하는 것으로 자료 분석 방법 중에서 가장 보편적인 방법이며 컴퓨터를 이용하는 많은 응용분야에서 사용되고 있다. 정렬은 보통 자료의 크기순으로 나열하며, 필요에 따라 사용자의 기준에 따라 나열하게 된다. 수많은 정렬 알고리즘은 비교할 대상을 선정하고 순서를 정하는 방법이 다를 뿐 본질적으로는 자료와 키 값을 비교해보고 순서를 바꿀 필요가 있는 자료들을 정렬이 완료 될 때까지 반복하여 비교하는 것이다. 효율이 좋은 정렬 알고리즘(sorting algorithm)을 개발하거나 이용하는 것이 시간과 비용을 절약하는 방법이다.

2. 정렬 알고리즘 종류별 특징
2-1. 선택 정렬 (Selection Sort)
: 기준 위치에 맞는 원소를 선택하여 자리를 교환하여 정렬하는 기초 알고리즘이다.
void Sort::SelectionSort()
{
int i, j;
int currentMax, currentMaxIndex;

for (i = n - 1; i >= 1; i--) {
currentMax = y[0];
currentMaxIndex = 0;

for (j = 1; j <= i; j++) {
if (currentMax < y[j]) {
currentMax = y[j];
currentMaxIndex = j;
}
}
if (currentMaxIndex != i) {
y[currentMaxIndex] = y[i];
y[i] = currentMax;
}
}
}

● 정렬 방법
마지막에 위치한 원소를 나머지 키와 비교하여 그 중 제일 큰 값을 맨 마지막 자리에 놓는다. 비교하는 동안 현재 가장 큰 값보다 더 큰 값이 발견되면 항상 마지막 값과 그 값을 서로 교환한다. 이러한 과정이 완료되면 가장 큰 값이 마지막에 위치하게 된다. 다음에는 맨 마지막의 제일 큰 수를 제외한 두 번째로 큰 값을 찾고 이를 마지막에서 두 번째 위치에 놓는다. 이 과정을 반복하면 선택정렬이 완성된다.

참고 자료

없음