아무 말

간단한 설명 병합 정렬은 존 폰 노이만에 의해 고안된 알고리즘이다. 병합 정렬은 분할정복 기법을 이용하며 다음과 같이 작동한다. 분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다. 계속해서 분할을 하다 보면 원소의 수가 하나가 되고 이는 원소가 하나임으로 이미 정렬된 수열이다. 이 하나의 원소로 이루어진 부분수열로 부터 각 부분수열을 병합해가면서 정렬하는 알고리즘이 바로 병합 정렬이다. 알고리즘의 설계 알고리즘의 설계를 위해 트리를 하나 생각해보자. 이 트리의 각 정점에는 두 개의 자식노드가 있고(물론 한개의 자식만 가질수도 있다.) 맨 아래쪽의..

삽입 정렬은 수를 정렬된 상태로 삽입함으로서 정렬하는 방법이다. A라는 배열이 있을 때 {A[1]}을 초기에 정렬된 배열이라고 하고 이 배열의 처음부터 끝까지를 확인하면서 A[i]보다 큰 수가 나오면 그 자리에 A[i]를 삽입한다. 이때 원래 자리에 있던 수를 비롯한 A[i]보다 큰 수들은 한 칸씩 뒤로 밀리게 된다. 또한 이 정렬된 배열을 따로 만들지는 않으며, A의 앞부분에 나타낸다. INSERTION-SORT(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i]>key A[i+1]=A[i] i=i-1 A[i+1]=key 위는 배열 A에 대한 삽입 정렬의 의사코드이다. A.length는 수의 개수이고 key는 현재 정렬해야하는 수를 의미한다. 삽입정렬에..