정렬 - 삽입정렬

삽입 정렬

삽입 정렬은 기준점을 점점 뒤로 이동시키면서 해당 기준점 이전의 앞 데이터가 정렬되도록 유지하는 정렬 방식이다.

generateRandomArray, printArray, swap

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성

printArray(myArray, arrayLength); // 정렬 전 배열 출력

for (int i = 0; i < arrayLength; i++) { // 배열의 첫 번재 요소부터 뒤쪽으로 탐색하는데,
    int tempValue = myArray[i]; // 임시 값의 초기화는 현재 위치의 배열 값
    int searchIndex = i - 1; // 탐색할 인덱스, 초기화는 탐색을 시작할, 현재 위치 - 1
    for (; searchIndex >= 0 && myArray[searchIndex] > tempValue; searchIndex--) {
        // 탐색을 앞쪽으로 한칸씩 진행하는데, 만일 앞쪽 값의 크기가 임시 값보다 작으면 진행할 필요 없음
        myArray[searchIndex + 1] = myArray[searchIndex]; // 값을 한 칸 오른쪽으로 복사한다.
    }
    myArray[searchIndex + 1] = tempValue; // 마지막으로 탐색된 위치에 임시 값을 넣는다.
}

printArray(myArray, arrayLength); // 정렬 후 배열 출력

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

탐색을 앞쪽으로 진행하면서, 값을 한 칸씩 오른쪽으로 복사해나가고 마지막에 임시 값을 채워넣는 방식을 가진다.

이러한 삽입 정렬 또한 최악의 경우 N(N-1)/2 에 따라 *O(N²) 의 복잡도**를 가지게 된다.