[HackerRank] Insertion Sort - Part 2

www.hackerrank.com/challenges/insertionsort1/problem

Insertion Sort - Part 1 | HackerRank

Algorithms > Sorting

 

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

한번 정렬이 이루어질 때마다 배열을 출력해야 한다.

 

 

코드

void insertionSort2(int n, int arr_count, int* arr) {
    int temp;
    for(int i = 1; i < n; i++) {	//정렬
        for(int j = 0; j < i; j++) {
            temp = arr[i];
            if(arr[j] > arr[i]) {
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        for (int k = 0; k < n; k++)	//배열 출력
            printf("%d ", arr[k]);
        printf("\n");
    }
}

 

설명

배열의 1번째 인덱스부터 왼쪽 값과 비교하며 정렬을 시작한다.

두번째 for 루프에서는 정렬된 값들(현재 인덱스보다 왼쪽에 있는 값들)과만 비교하기 위해 j<i를 조건으로 설정했다.

우선 비교하려고 하는 arr[i] 값을 temp에 저장한다.

만약 arr[i]보다 왼쪽에 있는 값(arr[j])이 arr[i]보다 크다면, arr[j]와 arr[i]의 위치를 서로 바꾼다.

한번 정렬이 끝났으니 마지막 for문을 사용해 배열을 출력한다.