Sorting

합병 정렬(Merge Sort)이란? 분할 정복 알고리즘(=Divide and conquer algorithm 즉, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘입니다.)의 하나로 O(n log n)의 시간 복잡도를 가지고 있습니다. 합병 정렬의 작동 알고리즘은 아래와 같습니다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 이해가 잘 안간다면 아래 애니메이션을 통해 작동 원리를 쉽게 이해할 수 있습니다. ...

삽입 정렬(Insertion Sort)이란? 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 삽입 정렬의 시간 복잡도는 O(n2)이며 안정 정렬입니다. 또한 배열이 길어질수록 효율이 매우 떨어지지만 구현이 간단하다는 장점이 있습니다. 삽입 정렬의 예 삽입 정렬의 애니메이션 -Simpsons contributor- 삽입 정렬 알고리즘을 구현하기 전에 의사코드(Pseudocode)로 먼저 이해를 하고 코드를 작성하는 것이 더 쉽게 작성할 수 있을 것입니다. Pseudocode : 1 2 3 4 5 6 7 8 9 //InsertionSort pseudo code InsertionSort(A,n) // sort A[1...n] for j <- 2 to n do key <- A[j] i <- j-1 while i>0 and A[i]>key do A[i+1] <- A[i] i <- i-1 A[i+1] <- key CCode: ...