[Algorithm] Quick Sort(퀵 정렬) 1. 정의 피벗(기준)을 하나를 정해서 피벗보다 큰 수는 오른쪽 작은수는 왼쪽으로 옮겨가며 정렬하는 기법 불안정 정렬 시간 복잡도 평균 : $O(nlogn)$ 최악 : $O(n^2)$ 2. 동작 과정 피벗을 하나 정한다. 양 끝에 포인터를 각각 두고 포인터를 움직인다. 2 - 1. 왼쪽 포인터는 피벗 보다 큰 값이 나올때까지 오른쪽으로 움직인다. 2 - 2. 오른쪽 포인터는 피벗 보다 작은 값이 나올때까지 왼쪽으로 움직인다. 2 - 3. 값을 찾으면 서로 교환한다. 2 - 4. (2 - 1) ~ (2 - 3)을 반복한다. 포인터가 서로 교차하면 2개의 구간이 생기는데, 각각의 구간 별로 1번부터 반복한다. 3. 장단점 장점 병합 정렬과는 달리 추가적인 ..
알고리즘
[Algorithm] Merge Sort(병합 정렬) 1. 정의 데이터 배열의 원소를 반으로 나누고, 합쳐서 정렬하는 알고리즘 분할 정복을 사용 시간 복잡도 최선 : $O(nlogn)$ 평균 : $O(nlogn)$ 최악 : $O(nlogn)$ 2. 동작 과정 배열의 원소가 2개가 남을 때까지 이등분 한다. 2개의 원소를 반으로 나누어 각각 비교하여 정렬된 배열을 얻는다. 나머지 배열들을 병합하면서 정렬한다. 3. 장단점 장점 순차적인 비교로 정렬 일정한 속도 안정 정렬 LinkedList 정렬할 때 퀵 정렬 보다 효율이 좋음 LinkedList는 순차 접근을 해야하는데 퀵 정렬은 임의 접근이기 때문 단점 추가적인 공간이 필요 4. 코드 public void mergeSort(int[] arr, int l..
[Algorithm] Insertion Sort(삽입 정렬) 1. 정의 2번째 원소부터 시작하여 그 앞의 원소들과 대소비교하여 삽입할 위치를 결정하여 삽입 Selection Sort와 유사하지만, 좀 더 효율적인 알고리즘 시간복잡도 최선 : $O(n)$ → 모두 다 정렬되어 있을 경우 평균 : $O(n^2)$ 최악 : $O(n^2)$ 2. 동작 과정(오름차순) 2번째 인덱스 값을 tmp에 저장 tmp 앞에 있는 원소들과 비교하여 가장 알맞은 자리(arr[i] < arr[tmp] < arr[i + 1])에 삽입 → 삽입하는 자리는 뒤로 한칸씩 밀린다. 1번으로 돌아가 반복 3. 장단점 장점 알고리즘이 단순 정렬되어 있을 경우 매우 효율적 제자리 정렬 안정 정렬 단점 평균과 최악의 시간복잡도가 $O(n^2)..
[Algorithm] Selection Sort(선택 정렬) 1. 정의 배열에서 자리를 선택한 후 특정 값을 찾아 교환하면서 정렬하는 방법 오름차순일 경우 뒷 부분에서 가장 작은 값을 찾아서 교환한다. 시간복잡도 최선 : $O(n^2)$ 평균 : $O(n^2)$ 최악 : $O(n^2)$ 2. 동작 과정(오름차순) 주어진 배열 중에 최소값을 찾는다. 찾은 값을 첫번째 원소와 교환한다. → 첫번째 원소는 정렬되어 있는 상태가 됨 정렬된 원소를 제외하고 가장 최소값을 찾아 정렬이 안된 첫번째 원소와 교환한다. 반복 3. 장단점 장점 자료 이동 횟수가 미리 결정 됨 제자리 정렬 단점 안정성을 만족하지 않음 → 상대적 위치가 바뀜 같은 원소가 중복되어 있으면 중복된 원소의 순서를 보장하지 않음 효율성이 떨어짐 4..
[Algorithm] Bubble Sort (거품 정렬) 1. 정의 서로 인접한 두 원소의 대소를 비교하고, 더 큰 원소를 뒤로 보내서 정렬하는 알고리즘 시간 복잡도 최선 : $O(n^2)$ 평균 : $O(n^2)$ 최악 : $O(n^2)$ 2. 동작 과정 첫 번째 원소와 두 번째 원소의 대소를 비교하여 첫 번째 원소가 더 크다면 두 원소의 위치를 바꾼다. 두 번째 원소와 세 번째 원소의 대소를 비교하여 두 번째 원소가 더 크다면 두 원소의 위치를 바꾼다. ... n - 1. (n - 1) 번째 원소와 n 번째 원소의 대소를 비교하여 (n - 1) 번째 원소가 더 크다면 두원소의 위치를 바꾼다. → 이런식으로 탐색 시작 범위를 하나씩 증가시키며 정렬을 진행한다. 3. 장단점 장점 구현이 매우 간단, ..
