알고리즘/정렬

버블 소트란? 버블 소트는 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 위에서와 같이 인접한 원소와 하나하나 비교하며 정렬을 수행한다. 배열의 끝까지 정렬을 완료하면 다시 처음으로 돌아가 같은 작업을 반복하여 수행한다. 다음은 JAVA로 작성된 버블 소트의 코드이다. public class bubbleSort { public static void main(String[] args) { int arr[] = {1,3,6,2,8,2,5,9}; //정렬중 임시 저장 int temp; //출력(정렬전) System.out.print("정렬전..

병합 정렬이란? 재귀를 이용한 정렬방법으로 원래의 배열을 분할한 뒤 정렬하며 병합하는 방식으로 정렬을 수행하는 방법을 말한다. 분할 정복의 개념을 도입한 방법이며, 부분 배열 array [a.... b]를 다음과 같이 정렬한다. 1. 만일 a=b이면 아무것도 하지 않는다. 부분 배열이 원소 한 개로 이루어져 있으며, 이는 이미 정렬되어 있기 때문이다. 2. 가운데 원소의 위치를 k = (a+b)/2 ※이때, a+b가 2로 나누어 떨어지지 않는다면 (a+b)/2보다 크지 않은 정수중 가장 큰 수가 k가 된다. 3. 재귀적으로 부분 배열 array [a.... k]를 정렬한다. 4. 재귀적으로 부분 배열 arrat [k+1..... b]를 정렬한다. 5. 정렬된 부분 배열 array [a... k]와 arr..