정렬
고급정렬 - QuickSort (퀵정렬)
2022.04.07정렬 과정 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide): 임의의 피벗을 지정하여 피벗보다 큰 원소와 작은거나 같은 원소, 두 부분 리스트로 나눈다. 결합(combine): 작은 리스트 - 피벗 - 큰 리스트로 결합한다. 정복(conquer): 두 부분 리스트를 재귀적으로 퀵 정렬을 이용해 정렬한다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 역시나 분할과 정복 방식이다. 구현 코드 package net...
고급정렬 - MergeSort (합병정렬)
2022.03.31정렬 과정 흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 이 과정에서 재귀 함수를 활용한다. 분할 후 분할된 2개의 조각에 다시 합병정렬을 실행한다. 분할과 정복. 구현 코드 package net.jetalab.excercise.mergesort..