1. 개념 |
버블 정렬과 같이 단순 비교문을 이용하여 정렬하고자 하는 값를 옴겨 놓는 방식은 비슷하나
키( Key )에 해당하는 값을 정하고 앞쪽의 하나씩 비교 대상 값과 비교하여 위치를 옴겨 놓는 방식
- key 값은 배열의 두번째 인덱스 값부터 시작하며 1회당 인덱스를 1씩 증가시켜 배열의 끝까지 도달합니다.
- 비교 대상 ( compare ) 값은 key 인덱스보다 -1 낮은 인덱스부터 시작하며 1회당 -1씩 감소 시켜 배열의 처음까지 도달합니다.
- 비교 조건(오름차순, 내림차순)에 해당한다면 값을 교환 변경 합니다.
key의 시작 인덱스 : 1
comare의 시작 인덱스 : 0
위의 사진과 조건에 해당할때만 값의 복사가 일어나서 버블 정렬과 다르게 시간을 단축시키는 요소가 생깁니다.
2. C# 코드 |
using System; namespace ConsoleApp1 { class Program { static void Main(string[] args) { int[] nArr = new int[]{ 1, 4, 3, 5, 9, 6, 2, 7, 8, 10 }; // nKey : 키 값 // nCompareIndex : 비교 값이 되는 인덱스 // nCount : 값의 교환 횟수 int nKey, nCompareIndex, nCount; nCount = 0; // 코드의 이해를 돕기위해 반복문의 인자 값을 이용목적으로 변수이름을 사용 // 시작 키 인덱스 : 1 for (int KeyIndex = 1; KeyIndex < nArr.Length; KeyIndex++) { nKey = nArr[KeyIndex]; // 시작 비교 인덱스 : 0 // nArr[nCompareIndex] > nKey : 오름차순 // nArr[nCompareIndex] < nKey : 내림차순 for (nCompareIndex = KeyIndex - 1; nCompareIndex >= 0 && nArr[nCompareIndex] > nKey; nCompareIndex--) { nArr[nCompareIndex + 1] = nArr[nCompareIndex]; nCount++; } nArr[nCompareIndex + 1] = nKey; } Console.WriteLine("Count : {0}", nCount); for (int i = 0; i < nArr.Length; i++) Console.Write(nArr[i] + "\t"); } } }
결과
Count : 9 |
3. 장단점 |
장점
- 비교적 쉬운 코드로 구현 가능
- 데이터의 크기가 작을 수록 복잡한 코드로 구현된 정렬보다 빠를수 있음
- 같은 구현 난이도의 버블 정렬보다 정렬 속도의 이점을 가지고 있음
단점
- 데이터의 크기가 커질수록 효율이 떨어짐
- 최악의 경우 비교 횟수와 교환 횟수가 버블정렬과 같이 n의 2승만큼 커질수 있음
정렬 알고리즘 테스트
종류 | 최소 | 최대 | 정렬시간 (10만개 테스트) |
퀵 정렬 | n log n | n2 | 32 ms |
삽입 정렬 | n | n2 | 8142 ms |
선택 정렬 | n2 | n2 | 13499 ms |
버블 정렬 | n2 | n2 | 53488 ms |
단적인 측면에서는 버블 정렬보다는 빠르지만 근본적인 효율에서는 비효율적인 방법 입니다.
4. 관련글 |
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 퀵 정렬 (Quick Sort ) (1) | 2018.11.13 |
---|---|
[알고리즘] 선택 정렬 ( Selection Sort ) (0) | 2018.11.12 |
[알고리즘] 버블 정렬 (Bubble Sort) (0) | 2018.11.07 |