Study Log

개요 병합정렬 알고리즘은 배열을 하나의 원소가 될 때까지 분할하여 정렬 후 정렬된 부분 배열을 병합, 병합된 부분 배열끼리 다시 정렬 후 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘이다. 위의 자료와 같이 분할하고 병합하는 과정이 똑같이 반복되기 때문에 재귀함수로 구현이 가능하다. 코드 void Merge_Sort(int A[], int p, int r) { if (p < r) { int q = (p + r) / 2; Merge_Sort(A, p, q);// 분할 Merge_Sort(A, q + 1, r);// 분할 Merge(A, p, q, r);// 정렬 } } 위의 코드는 배열을 분할하고 정렬하는 함수를 재귀적으로 수행하는 Merge_Sort 함수이다. 여기서 p와 r은 정렬할 배열의 각..

개요 선택정렬 알고리즘은 정렬되지 않은 부분배열에서 가장 작은 원소를 찾아 알맞은 위치에 삽입하고 이를 반복하여 배열 전체를 정렬하는 알고리즘이다. 위의 자료에서 정렬된 부분배열은 빨간색, 정렬되지 않은 부분배열은 검은색으로 표시했다. 정렬되지 않은 부분배열을 순회해 가장 작은 key 값을 찾아, 알맞은 위치의 원소와 위치를 바꾼다. 이를 반복하면 전체 배열을 정렬할 수 있다. 코드 void Selection_Sort(int arr[], int size){ int key, index; for(int i=0;i

개요 삽입정렬 알고리즘은 배열의 모든 인덱스를 확인하며 차례차례 자신의 적절한 위치를 찾아 정렬하는 알고리즘이다. 위의 자료에서 정렬된 부분은 분홍색, 정렬하고자 하는 키 값은 회색으로 표시했다. 여기서 키 값은 앞의 정렬된 분홍색 부분배열의 적절한 위치에 삽입된다. 이후, 키 값은 다음 인덱스로 넘어가고 이것을 반복해 배열 전체를 돌게되면 정렬이 되는 매커니즘이다. 코드 void Insertion_Sort(int arr[], int size){ for(int j=1;j -1 && arr[i] > key){ arr[i+1] = arr[i]; i -= 1; } arr[i+1] = key; } } 함수의 매개변수로는 배열과 배열의 크기를 받는다. 배열의 0번째 인덱스는 굳이 살펴볼 필요가 없기 때문에 1번째..