합병 정렬(Merge Sort) 의 개념 요약 분할 정복 알고리즘 중 하나이다. 분할 정복(divide and conquer) 방법 - 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 구체적인 개념 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의..

버블 정렬(bubble sort) 의 개념 요약 서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하며 정렬해나가는 알고리즘이다. 구체적인 개념 버블 정렬은 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 교환하면서 정렬한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 예제 → 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 오름차순으로 정렬해 보..