C++ 정렬

소개글

선택정렬, 삽입정렬, 버블정렬에 대하여 설명하였습니다.

목차

1. 선택정렬(Selection Sort)
2. 삽입정렬(Insertion Sort)
3. 버블정렬(Bubble Sort )

본문내용

일반적으로 정렬[整列, sort]은 주어진 자료를 어떤 기준에 의하여 크기 순서로 배열하는 것으로 자료분석 방법 중에서 가장 보편적인 방법이며 컴퓨터를 이용하는 많은 응용분야에서 사용되고 있다. 상용 업무의 상당부분을 차지하므로 효율이 좋은 정렬 알고리즘(sorting algorithm)을 개발하거나 이용하는 것이 시간과 비용을 절약하는 방법이다.
몇 가지 정렬 알고리즘(sorting algorithm)의 종류와 설명을 간단히 하자면 아래와 같다.

정렬 알고리즘(sorting algorithm)의 종류

1. 선택정렬(Seletion Sort)
- 임의의 최소값을 정한 후 순차적으로 비교하여 더 작은 값이 나오면 바꾸고 다시 임의의 초기값을 다른 임의의 초기값으로 교환한다.

2. 삽입정렬(Insertion Sort)
- 이미 정렬된 배열일 경우 매우빠름.
- 첫 번째 배열과 다음 배열을 비교하여 작은값을 앞으로 이동.

3. 거품정렬(Bubble Sort)
- 인접한 배열을 비교하여 교환.

4. 쉘 정렬(Shell Sort)
- H만큼의 간경으로 떨어진 레코드를 삽입 정렬.
- 멀리있는 요소를 교환하여 정렬.

5. 분포수 세기(Distribution Counting)
- 같은 키가 많이 있는 배열에 한해 적용.




- 단계별 삽입정렬의 구현
4 1 28 34 6 5 45 18
이와 같은 data가 있을 때 4는 정렬된 것이고 1부터 18은 정렬이 안된 것이다.
1st pass
4까지는 정렬된 것이므로 1을 기억하고 자리를 비운다. 4가 1보다 크므로 1을 뺀 자리를 4를 밀어서 채우고 남은 자리에 1을 삽입한다.
→ 1 4 28 34 6 5 45 18
2nd pass
1, 4,까지 정렬된 것이므로 28을 기억하고 자리를 비운다. 4는 28보다 작으므로, 뒤로 이동되지 않고(더 이상 앞으로 진행해서 28과 비교할 필요없다. 그 앞의 것들은 모두 4보다 같거나 작다) 28이 그대로 빈자리에 들어간다.
→ 1 4 28 34 6 5 45 18
3rd pass
1, 4 28까지 정렬된 것이므로 34를 기억하고 자리를 비운다. 28은 34보다 작으므로, 뒤로 이동되지 않고(더 이상 앞으로 진행해서 34와 비교할 필요없다. 그 앞의 것들은 모두 28보다 같거나 작다) 34가 그대로 빈자리에 들어간다.
→ 1 4 28 34 6 5 45 18
4th pass

참고 자료

없음