목록알고리즘 Note (9)
-
- Unstable Sort - 최악의 경우 O(N^2) // 평균적으로 O(nlogn)이지만 보장할 수 없다. - 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. --> 분할 정복 적용 피봇을 보통 첫번째 원소로 잡고, Index가 1부터 n-1 을 탐색 왼쪽에서 오른쪽으로(i=1 -> i++) 탐색하며 피봇보다 큰 값을 확인함과 동시에 오른쪽에서 왼쪽으로(j=n-1 -> j--) 탐색하며 피봇보다 작은 값을 확인한다. i와 j 가 엇갈리지 않는다면 i와 j에 해당하는 값을 바꾼다. 만약 엇갈린다면 지금 피봇값과 j 값을 바꾼다. j 인덱스에 위치한 피봇값..
- 대표적인 "분할정복" 방법을 채택한 알고리즘 - 퀵 정렬의 보완된 버전 -> 퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2) -> 하지만 일반적인 경우에서 퀵정렬보다는 느리다. 합병 정렬은 "배열을 생성하는" 시간이 있기 때문이다. 정렬하고자 하는 배열의 길이가 길면 길수록 차이가 난다. - Stable Sorting - 최선/최악/평균 시간 복잡도 : O(nlogn) 자세한 내용은 https://blog.naver.com/ndb796/221227934987 7. 병합 정렬(Merge Sort) 지난 시간까지 시간 복잡도 O(N ^ 2)인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘을 공부했습니다. 이어... blog.naver.com 여기서 복습하는 것으..
- 삽입 정렬을 보완한 정렬 알고리즘 - 삽입 정렬의 단점은 비효율적으로 값의 교환 횟수가 많아질 수 있다는 점이다. ex) 10개의 배열 요소 중, 8번째 값을 정렬된(왼쪽) 리스트에 삽입할 위치를 찾기 위해 그만큼 비교 연산을 해야함. - 쉘 정렬은 이러한 삽입 정렬의 단점을 보완하여 정렬할 배열을 여러개의 부분 배열로 나누어 나누어진 배열에 대해 삽입 정렬을 수행한다. 따라서 서로 멀리 떨어진 요소들간의 비교 연산또한 효율적으로 할 수 있다. - 쉘 정렬은 중간 크기의 목록에 효율적. 병합, 힙, 퀵 정렬보다는 현저히 느리지만 속도가 우선시 되지 않는 5천개 정도의 요소를 가진 목록에는 좋을 수 있음 - 셸 정렬에서는 요소들이 멀리 떨어진 위치로 이동할 수 있다는 장점이 있다. 이런 것이 가능한 이..
- 매 반복마다 뒤쪽의 정렬되지 않은 요소들의 목록에서 요소를 삭제하고 삭제한 요소를 앞쪽의 이미 정렬된 목록 내 알맞은 자리에 삽입. - 입력 데이터에서 삭제될 요소는 정렬되지 않은 목록에서 무작위로 선택(보통 앞에서 차례대로) - 0번과 1번 인덱스는 정렬이 되어 있다고 가정(반복되면서 알아서 정렬됨) - 시간 복잡도 Worst: O(n^2) Best: O(n) Average: O(n^2) - 공간 복잡도: O(1) - 삽입 정렬은 미리 데이터가 어느 정도 정렬 되어 있거나 입력 데이터가 적을 경우 사용. --> 병합 정렬 or 퀵 정렬과 같은 분할 정복 알고리즘의 base case로 사용되기도 함 void insertion_sort(int arr[], int size_arr) { for (int i..
- 선택 정렬은 작은 양의 데이터에 유용. - 구현이 쉽고 제자리 정렬(추가 저장 공간이 필요 없음) --> bubble sort나 insertion sort 등도 마찬가지. 그냥 temp 변수 선언으로 치환 할 뿐. 알고리즘 1. 목록에서 최소값을 찾는다. 2. 찾은 최소값을 맨 앞의 값(혹은 현재 위치의 값)과 교체 3. 배열의 전체 요소가 정렬될 때까지 이 과정을 반복. - 시간 복잡도 Worst: O(n^2) Best: O(n) Average: O(n^2) - 공간 복잡도: O(1) void selection_sort(int arr[], int size_arr) { for (int i = 0; i < size_arr; i++) { int min = i; for (int j = i + 1; j < ..
- 일반적으로 버블 정렬보다 삽입 정렬의 복잡도가 더 좋다고 함. - 유일한 장점/사용 이유? 는 입력 목록이 이미 정렬되어 있는지를 탐지할 수 있다는 점 - 시간 복잡도 Worst: O(n^2) Best: O(n) --> 이미 정렬되어 있는 경우. Average: O(n^2) - 공간 복잡도: O(1) - 개선된 Bubble 정렬 코드 --> Swap 하는 부분에 flag 변수를 넣어서 한 바퀴 도는 동안 flag 변수가 바뀌지 않았다면 이미 정렬이 완료된 것이기에 Loop를 끝낸다. void bubble_sort_advanced(int data[], int n) { int i, j; int temp; int flag = 1; for (i = n - 1; flag&&i >= 1; i--) { flag ..
Stable/Unstable 정렬 --> 비교 대상의 Key가 여러개 값을 가질때 혹은 같은 값을 가지는 데이터가 여러개 있을 때, 정렬후에 기존의 순서를 유지하는지에 따라 Stable과 Unstable로 나뉜다. 비교 Key가 한 개일때는 나누는 것이 굳이 의미 없지만 여러개일 경우(구조체 함수 데이터) 특정한 데이터를 기준으로 Sorting할 경우 Stable/Unstable 정렬의 종류를 고려하여 적용해야 한다. 예를들어 Dave A Alice B Ken A Eric B Carol A 위와 같은 데이터를 정렬하려면 두 가지를 기준으로 정렬할 수 있다. 여기서 중복되는 데이터가 있는데 정렬 전 원래의 순서를 기억할것이냐 말것이냐에 따라 Stable과 Unstable 알고리즘을 선택해야 한다. Stab..