오늘은 삽입정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다.
오름차순으로 정렬하기 위해서는 정렬할 값과 정렬된 배열의 끝(가장 큰 수)부터 차례대로 비교해가면서 알맞은 자리에 삽입하면 됩니다.
정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다.
처음에는 인덱스가 0인 부분만 정렬된 상태이고 그 뒤의 숫자는 정렬되지 않은 즉, 정렬할 값이라고 생각하면 됩니다.
배열 위의 화살표는 현재 삽입정렬을 할 숫자이고, 배열 밑의 화살표는 삽입정렬 수행 시 비교하는 숫자들과 연결한 것입니다.
현재 삽입정렬를 할 숫자를 key라고 부르겠습니다.
반복문을 돌면서 정렬된 부분(보라색 부분)의 숫자가 key값보다 크면 뒤로 한칸씩 밀어주고,
만약 정렬된 부분(보라색 부분)의 숫자가 key값보다 작거나, 배열의 맨 앞부분(인덱스가 0)까지 왔다면 반복문을 탈출합니다. 탈출하는 시점이 key의 알맞은 자리입니다.
그 후, 알맞은 자리에 key를 삽입하면 됩니다.
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void insertionSort(int* arr) {
int temp;
for (int i = 1; i < 5; i++) {
temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
void main() {
int num[5] = { 4,2,1,5,3 };
insertionSort(num);
for (int i = 0; i < 5; i++) {
printf("%d\n", num[i]);
}
}
[알고리즘] 해쉬 테이블(hash table) - 오버플로 체인(overflow chaining) (0) | 2022.06.16 |
---|---|
[알고리즘] 넓이 우선 탐색 (BFS) (1) | 2021.12.27 |
[알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) (0) | 2021.12.21 |
[알고리즘] 계수정렬(counting sort) (0) | 2021.12.20 |
[알고리즘] 선택정렬 (Selection Sort) (0) | 2021.12.13 |
댓글 영역