Developer_Neo

앞서 있었던 퀵정렬은 피벗 값에 따라서 편향되게 분할 될 가능성이 있다는 것이다 그래서 최악의 경우 O(N^2)의 시간 복잡도를 가진다. 하지만 지금 배울 병합정렬은 편향되게 분할 될 가능성이 없다. 정확히 반 반씩 나누기 때문에 최악의 경우에도 O(N*logN)의 시간복잡도를 보장한다. Divdie and Conquer방식이라고도 배우는데 먼저 기존에 있는 배열들을 작게 작게 각각 하나씩 가질때 까지 나눈다는 것이다 그리고 merge할때 정렬해가면서 합친다는 것이다. 정렬을 할때 다른 배열을 생성하여 그 배열에 정렬해서 넣는것이다 방법은 나뉘어진 배열 2개에 대해 합치게 되는데 이때 각각 배열의 첫번째 인덱스의 값들을 비교해서 작은 것부터 생성한 배열에 넣는것이다. 위의 그림처럼 말이다 코드를 살펴보자..

퀵 정렬(Quick Sort) - 선택, 버블, 삽입정렬 알고리즘은 Worst case인 경우에 모두 시간 복잡도를 O(N^2)을 가지게 되는데 보통 데이터 갯수가 무수히 많다고 가정하는 상황에서는 사용하기 어려운 정렬들이다. - 퀵 정렬은 분할 정복 알고리즘으로 특정한 배열이 있을때 그 배열을 반복적으로 분할 배열의 원소들을 나누어서 계산한다. 빠른 알고리즘이다. - 사용 방법 특정한 값을 기준으로 큰 숫자 집합과 작은 숫자 집합으로 나눈다. Pivot이라는 명칭으로 원소를 정하게 되는데 이 Pivot을 기준으로 비교해서 Pivot이 가운데에 오게 왼쪽 오른쪽으로 나누게 되는 것이다. 더 좋은 방법은 배열을 정렬할때 Pivot을 처음 중간 끝을 기준으로 3개를 골라서 이 3개를 비교해서 중간값을 이용해..

삽입 정렬(Insertion Sort) - 선택, 버블 정렬은 무조건 위치를 바꾸지만 이것은 필요할때만 위치를 바꾼다 - 즉 삽입정렬은 이미 정렬되어있다고 가정하는데 정렬할때의 좌측은 이미 정렬이 되어있어 내가 선택한 값과 비교를 통해 알맞은 위치에 삽입을 한다는 것이다. (비교하는 꼴은 내가 선택한 값과 정렬이 되어있는 것의 오른쪽 부터 비교해 값이 더 크다면 삽입할위치를 계속찾는것이다. 이때 내가 선택한 값에 정렬이 되어있던 것의 작은 값을 차례대로 넣는 과정을 거친다.) public class Insertion_Sort { public static void sort(int []a){ for(int i=1;i=0&&target

버블 정렬(Bubble Sort) - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 (효율성이 가장 떨어진다.) - 서로 비교해서 큰 값을 뒤로 보내는 것이다. (오름차순으로) - 버블하면 비눗방울이 떠오르는데 비눗방울은 작으니 작은 원으로 감싸져 있는 인접한 두 원소를 검사하여 정렬한다고 생각하자. 이런과정을 데이터 갯수만큼해야되는데 조건이 배열의 마지막인덱스는 정렬된 값이라서 나중에 정렬할때 제외하는게 좋다. 이때 데이터갯수가 n개라고 하면 위의 단계를 n-1번만 하면 된다 왜냐하면 마지막으로 배열의 인덱스 0에 남은 것은 앞의 것이 정해짐에 따라 같이 정해지기 때문이다. public class Bubble_Sort { public static void bubble_sort(int []a) { f..

선택 정렬(Selection Sort) - 가장 작은 것을 선택해 제일 앞으로 보내는 것. public class Selection_Sort { public static void selection_sort(int[] a) { selection_sort(a, a.length); } private static void selection_sort(int[] a, int size) { for(int i = 0; i

학교에서 이미 배웠지만 잘 사용하지 않으면 까먹어 블로그에 정리하게 되었다. 알고리즘은 분석을 통해 좋고 나쁨을 평가할 수 있다. 알고리즘은 개발 전체과정에 사용된다. 알고리즘 문제는 종합적인 개발 역량을 평가하기에 좋은 용도이다. 출처 : 동빈나 유투버 : https://www.youtube.com/watchv=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz