정렬 알고리즘

퀵 소트란? 퀵 소트는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 퀵 소트는 정렬 알고리즘 중 가장 빠르다고 하여 붙여진 이름이다. pivot을 선택하여 비교하며 정렬을 수행하는데 pivot으로 선택한 수가 가장 작거나 가장 크다면 최악의 경우로 정렬 수행 시간이 가장 오래 걸린다. 하지만 가장 오래 걸리더라도 O(n^2)의 시간 복잡도를 가지며 이 최악의 경우만 제외한다면 평균적으로 O(nlogn)의 시간 복잡도를 가진다. 퀵 소트은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 1. 리스트에서 임의의 수를 pivot으로 정한다. 2. pivot앞에는 pivot보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 ..

버블 소트란? 버블 소트는 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 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..