1. 병합 정렬 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법을 말한다. 병합 정렬도 퀵 정렬 처럼 분할정복 알고리즘을 이용하는 방법이며, 속도 또한 퀵 정렬과 같이 $$ O(N\times log_2{N}) $$ 의 성능을 보인다. 병합 정렬이 퀵 정렬과 속도는 같지만, 퀵 정렬은 최악의 경우 $$ O(N^2) $$ 의 속도를 가지지만, 병합 정렬은 최악의 경우에도 $$ O(N\times log_2{N}) $$ 의 속도를 가지는 매우 안정적인 정렬이라고 할 수 있다. 2. 동작 순서 병합 정렬의 동작 순서는 매우 간단하다. 2개씩 나누어서 분할 한 후 (재귀 함수를 이용) 결합을 하면 되는데, 주의할 점은 결합을 함과 동시에 정렬 작업을 해주어야 한다. 3. ..

1. 퀵 정렬 "퀵"이라는 말 그대로 정말 정말 정말 빠른 정렬이다. 퀵 정렬은 특별한 경우를 제외하고는 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 따라서 퀵 정렬의 시간 복잡도는 $$ O(N\times log_2{N}) $$ 이다. 여태 포스팅했던 선택 정렬, 버블 정렬, 삽입 정렬의 시간 복잡도는 $$ O(N^2) $$ 이다. 고등학교 수학을 배운 사람이라면 $$ N^2 > N \times log_2{N} $$ 이 성립된다는 것을 알 수 있다. 하지만, 빅오 표기법에서 log₂N과 N²의 차이는 어느정도일까? 차이는 어마무시하다고 말할 수 있다. $$ N=2^{10} $$ 일 때를 예로 들어보자. 2를 10번 곱하면 1024이다. 하지만 컴퓨터에서는 1024라고 하지 않고 통상 1000이라고..

1. 삽입 정렬 삽입 정렬은 선택 정렬, 버블 정렬과 함께 시간복잡도 $$ O(n^2) $$ 을 가진다. 하지만 삽입 정렬은 선택정렬, 버블 정렬과 같은 시간복잡도를 가지지만, 두 정렬보다는 빠른 속도를 가진다. 그 이유는 선택, 버블 정렬의 경우에는 일일히 원소 값을 비교하는 탐색 과정을 거치지만, 삽입 정렬의 경우, 필요할 때만 위치를 바꾸는 방식을 이용하기 때문이다. 「자바로 배우는 쉬운 자료구조, 한빛 미디어」 책에서는 S(정렬 되어있는 부분집합), U(정렬되지 않은 부분집합)으로 나누어서 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하는 방식을 이용한다고 설명하지만, 결국 의미는 같다. 음, 그러니까 그냥 필요할 때만 위치를 바꾼다. 라..

1. 버블 정렬 버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 첫 번째 원소부터 마지막 원소까지 반복하여 가장 큰 원소가 마지막 자리로 오게 정렬 방식이다. 버블 정렬은 탐색 방법이 선택정렬(이전 포스트 글)과 반대라고 생각하면 된다. 선택 정렬은 처음 요소를 1씩 늘려 탐색하는 방법이라고 한다면, 버블 정렬은 마지막 요소를 1씩 빼서 탐색하는 방법이라고 생각하면 된다. 2. 동작 순서 동작 순서도 크게 어려울 건 없다. 선택정렬(이전 포스트 글)에서 썼던 예시 입력 값을 그대로 써서 설명하도록 하겠다. 우리는 이제 위의 입력값 [5, 10, 1, 2, 6]을 버블 정렬을 이용하여 오름차순으로 정렬하려고 한다. 먼저 첫 요소인 5부터 끝 요소인 6까지 탐색을 실시하여 현재 요소 ..

1. 선택 정렬 선택정렬은 정렬 알고리즘의 하나이다. 동작 순서는 별거 없다. 이 한마디만 기억하면 된다. 최소 값을 맨 앞으로 보내라 2. 동작 순서 이것이 무슨 말입니까...? 생각이 든다면, 간단한 예를 들어보도록 하겠다. 선택 정렬의 동작순서를 설명을 하기 위해 다음의 리스트 값으로 예를 들어보도록 하겠다. 우리는 선택정렬을 이용해서 이 리스트 값을 오름차순으로 정렬하려고 한다. 먼저, 첫 번째 요소 5에서부터 리스트 끝인 6까지 탐색해서 최솟값을 찾도록 한다. 최솟 값은 1이 나온다. 찾은 최솟 값 1을 맨 앞 요소와 스와핑한다. 그리고 두 번째 요소 10에서부터 리스트 끝인 6까지 탐색해서 최솟 값을 찾도록 한다. 최솟 값은 2가 나온다. 그 후 찾은 최솟 값을 10과 스와핑하여 맨 앞으로 보..