정렬 알고리즘5 병합 정렬 (Merge Sort) 알고리즘을 공부하는 학생들이나 취준생들은 이 정렬알고리즘이 꼭 필요할 때가 있다. 많고 많은 정렬 알고리즘 중에 하나를 선택해야한다면 이 병합 정렬을 공부해서 익혀두길 권장한다. 병합 정렬은 안정 정렬에 속하고, 분할 정복(devide & conquer) 알고리즘 중 하나이다. 구현 방법은 아래와 같다. 1. 배열의 길이가 한개가 될때까지 배열을 분할한다. 2. 각 부분의 배열을 재귀적으로 정렬한다. 3. 하나의 리스트가 될때까지 정렬한다. 음 위의 구현방법이 이해가 잘 안되면 아래그림을 보면 이해가 쑤욱 될것이다. 병합정렬의 가장 큰 장점은 입력데이터가 무슨 데이터이든 상관없이 일관되게 O(nlog₂n) 의 복잡도를 가진다는 것이다. 구현 방법은 아래와 같다. public class MergeSort .. 2021. 7. 6. 퀵 소트 (Quick Sort) 오늘은 Quick Sort를 구현해 보려 한다. 퀵 소트는 기준이 되는 값(pivot)을 하나 잡고 , 기준 값 보다 작거나 같은 값을 가지고 있는 자료는 앞쪽으로 보내고, 큰 값을 가지고 있는 자료는 뒤쪽으로 보내 기준 값을 기준으로 분할해서 정렬을 진행하는 방법을 의미한다. 정렬 방식은 아래와 같다. 1. 기준 값(pivot)을 정한다. 2. pivot 앞에는 pivot 보다 작은 값이 오고, pivot 뒤에는 큰값이 오도록 배열을 둘로 분할한다. 3. 분할된 두 개의 배열에 대하여 재귀함수를 통하여 정렬하는 과정을 반복한다. 위처럼 이렇게 정렬이 된다. 시간복잡도는 평균적인 경우에는 O(nlogn) 이지만 최악의 경우는 O(N²) 이다. 최악의 경우는 피봇을 최소값이나 최대값을 선택할때이다. ( 즉.. 2021. 7. 5. 버블 정렬 (Bubble Sort) 버블 정렬은 인접해 있는 두 배열 요소를 차례대로 검사하여 정렬하는 방식이다. 정렬은 아래와 같이 진행된다. 1. 시작은 배열의 첫번째 요소와 두번째 요소로 시작된다. 인접한 두 요소를 비교하여 정렬한다. 2. 배열의 다음 인접한 요소를 비교하여 정렬한다. (두번째 세번째) 3. 배열의 끝까지 비교를 반복하면 맨끝에는 정렬이 완료된 요소가 온다. 4. 마지막에 정렬된 요소를 제외하고 1~3 과정을 반복한다. 예제 코드 public class BubbleSort { public static void main(String[] args) { int[] data = {3,5,-5,1,4,0}; int[] result = bubbleSort(data); for(int num : result) { System.ou.. 2021. 7. 5. 삽입 정렬 (Insertion Sort) 오늘은 삽입 정렬 정리를 한번 해보겠다. 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교를 해서, 자기 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘이다. 정렬 방식은 아래와 같다. 1. 배열의 첫번째 요소는 정렬된 상태라 가정한다. 2. 배열의 두번째 요소부터 앞에 정렬된 요소들과 차례로 비교하여 교환한다. 3. 최종적으로 해당 요소는 자신의 자리에 맞는 위치에 삽입 된다. 4. 1~3 과정을 반복한다. 삽입 정렬은 데이터가 많아지면 많아질 수록 성능이 저하 된다. 시간 복잡도는 O(N²) 을 따른다. 예제 소스 코드 public class InsertSort { public static void main(String[] args) { int[] data = {3.. 2021. 7. 4. 선택 정렬 ( select sort) 오늘부터 간단하게 정렬 알고리즘을 정리해두려고 한다. 첫번째는 알고리즘 수업을 들을 때 맨 처음 배우는 선택 정렬 알고리즘이다. 이 알고리즘은 아래의 방식을 따라 수행된다. 1. 아직 정렬 안된 리스트 중 가장 앞의 원소를 최소값 or 최댓값으로 설정 2. 가장 앞에 원소를 제외한 나머지 원소를 차례로 비교하여 최솟값 or 최댓값을 찾아감 3. 리스트를 끝까지 비교하여 찾은 최소값을 가장 앞의 원소와 교환 4. 정렬이 다될때까지 1~3 반복 선택 정렬의 경우 데이터를 교환하는 횟수는 적지만 결국 비교하는 횟수가 많아서 대용량 데이터에서는 비효율적이다. 시간 복잡도는 O(N²) 을 따른다. 예제 소스 코드 class SelectSort { public static void main(String[] args.. 2021. 7. 4. 이전 1 다음
