장삼의 착한코딩

Merge Sort는 수열을 하나의 수가 될 때까지 분할을 한 후 다시 병합하는 정렬 방식이다.Merge Sort는 크게 2가지의 과정을 거친다.첫 번째 과정인 분할 과정에서는 수열을 분할(divide)하는 과정이다. Merge Sort에서는 size가 n인 배열이 있으면, [1 ~ n/2]의 배열과, [n/2 +1 ~ n] 으로 나누는 과정을 재귀를 통해 size가 1이 될 때까지 반복을 한다. - Merge Sort의 원리추가하여 설명을 하면, 처음 size가 7인 배열을 정렬을 할 경우, 1~4, 5~7의 원소를 갖는 배열로 나눈다. 나눌 때 배열이 홀수 이므로, 앞의 배열은 4개, 뒤의 배열은 3개로 나누게 된다. 분열을 한 후 재귀 함수를 통해 각각의 배열을 다시 1~2, 3~4, 5~6, 7의..

Insertion sort는 앞부분에 이미 정렬된 배열과 비교를 하여 자신의 위치를 찾아 삽입 함으로서 앞부분부터 정렬을 하는 알고리즘이다. Key 값을 기준으로 key의 앞부분은 항상 정렬이 되어있다는 특징이 있다. - Insertion Sort의 원리 1. key 값을 기준으로 key의 앞은 정렬이 된 상태이다. i번째 요소를 정렬을 하기 위해서 i번째 배열의 값을 key로 저장을 한다. 2. key값을 기준으로 i-1부터 검사를 하며 key 값보다 값이 클 경우 값을 한 칸씩 오른쪽으로 이동 시킨다.3. 그림과 같이 key 값보다 작거나 같은 값이 나올 때까지 2번 과정을 반복한다.4. 3번 과정에서 key값이 들어갈 위치를 찾으면 key값을 위치에 삽입한다. - Insertion Sort의 동작 ..