[HackerRank] Insertion Sort - Part 1

www.hackerrank.com/challenges/insertionsort1/problem

Insertion Sort - Part 1 | HackerRank

Algorithms > Sorting

 

배열의 크기와 배열이 주어지면, 해당 배열을 오름차순으로 정렬한다.

단, return 값은 없으며 정렬 과정을 출력해야 한다.

 

 

코드

void insertionSort1(int n, int arr_count, int* arr) { //n: 배열의 크기
    int temp = arr[n - 1];	//비교할 값을 temp에 저장 (배열의 가장 오른쪽 숫자)
    for (int i = n - 1; i >= 0; i--){
        if (arr[i - 1] > temp){		//왼쪽 값이 temp보다 큰 경우
            arr[i] = arr[i - 1];	//왼쪽 값을 현재 인덱스에 저장
            for (int j = 0; j < n; j++)	//배열 출력
                printf("%d ", arr[j]);
        }
        else {			//왼쪽 값이 temp보다 작거나 같은 경우
            arr[i] = temp;	//temp 값을 현재 인덱스에 저장
            temp = arr[i - 1];	//왼쪽 값을 temp에 저장
            for (int j = 0; j < n; j++)	//배열 출력
                printf("%d ", arr[j]);
            break;
        }
        printf("\n");
    }
}

 

설명

배열의 맨 오른쪽부터 정렬을 시작한다.

처음에 맨 오른쪽 값을 temp에 저장하고, 왼쪽으로 하나씩 비교해간다. (i: 5, arr: 2 4 6 8 3, temp: 3)

만약 왼쪽 값이 temp 보다 크면, 현재 인덱스를 왼쪽 값으로 바꾼다.

(i: 4, arr: 2 4 6 8 8, temp: 3), (i: 3, arr: 2 4 6 6 8, temp: 3), (i: 2, arr: 2 4 4 6 8, temp: 3)

만약 왼쪽 값이 temp 보다 작거나 같으면, 현재 인덱스를 temp로 바꾸고 왼쪽 값을 temp에 저장한 다음 break한다.

(i: 1, arr: 2 3 4 6 8, temp: 2)