코코야이야기

합병 정렬 (Merge Sort) - 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함 - 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임 - 두 부분배열의 크기가 동일하도록 분할함 성능 특성 - 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨 - 순차적 방식에 의해 데이터를 접근함 - 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능 - N 에 비례하는 추가 기억장소가 필요함 - 안정적이지만 제자리 정렬은 아님 - 최악의 경우 시간 복잡도 O(N logN) - 입력 배열에 민감하지 않음 수행 과정 퀵 정렬과 비교 퀵 정렬 : 정복-분할(conquer-and-divide) - 순환 호출이 이루어지기 전에 대부분의 작업이 수..

중간 값 분할 - 분할 원소를 선택할 때 왼쪽, 가운데, 오른쪽 원소 중 값이 중간인 원소를 선택 - 왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 a[l], 가장 큰 값을 a[r], 중간 값을 a[r-1]에 넣고, a[l+1], …, a[r-2]에 대해 분할 알고리즘을 수행 특징 - 최악의 경우가 발생하는 확률을 낮추어 줌 - 경계 키(sentinel key)를 사용할 필요가 없음 - 전체 수행 시간을 약 5% 감소시킴 소스 코드 #include #include #include using namespace std; const int N = 10000000; const int TRUE = 1; const int FALSE = 0; int a[N+1]; inline void swap(int a[..

작은 부분화일 부분화일의 크기가 일정 크기 이하로 작아지면 삽입 정렬 수행 “if (r > l)” - “if (r - l a[i+1]) Sorted = FALSE; if (!Sorted) break; } if (Sorted) cout

스택을 이용한 순환제거 소스 코드 #include #include #include using namespace std; const int N = 10000000; int a[N+1]; const int TRUE = 1; const int FALSE = 0; inline void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } void CheckTime(int a[], int n) { int i, Sorted; Sorted = TRUE; for (i = 1; i a[i+1]) Sorted = FALSE; if (!Sorted) break; } if (Sorted) cout r-i) { st...

퀵 정렬 (Quick Sort) - 1960년 C.A.R. Hoare에 의해 개발 - 분할 정복(divide and conquer) 기법을 사용한 정렬 방법의 하나 - 현재 가장 광범위하게 쓰이는 정렬 알고리즘 - 퀵 정렬의 성능을 개선하려는 시도가 있었지만 큰 성과를 거두지 못함 특징 - 평균적으로 아주 좋은 성능을 가짐 - 약간의 작은 스택만 있으면 별도의 메모리를 요구하지 않음 - 불안정적인 제자리 알고리즘 - N 개의 원소를 정렬하는데 평균적으로 N logN 의 연산속도를 가짐 기본 알고리즘 1. 배열 a[l : r] a[r]을 피봇(pivot)으로 선정 2. 피봇을 기준으로 a[]의 원소들을 두 개의 파티션(partition)으로 분할 - 분할 후 피봇은 a[i]에 들어가게 되는데, 이곳은 정렬..

쉘 정렬 (Shell Sort) - 삽입 정렬을 간단하게 변형 - 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 - h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 - 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 특징 - 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교 횟수는 N 3/2 을 넘지 않음 - 제자리 정렬 - 멀리 떨어진 원소끼리 교환할 때 동일한 원소가 어디로 갈지 알 수 없으므로 불안정적 수행 과정

칵테일 쉐이커 정렬 (Cocktail Shaker Sort) - Donald Knuth가 처음 제안 - 버블 정렬을 수정하여 매번 반복할 때마다 방향을 바꿔가며 원소의 위치를 결정하는 기법. - 한 번은 가장 큰 원소가 결정되고, 그 다음에는 가장 작은 원소가 결정되고, 또 그 다음에는 2번째로 큰 원소가 결정되고... 소스 코드 1. #include #include using namespace std; const int N = 10000; const int TRUE = 1; const int FALSE = 0; inline void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } void printList(int a[]) { i..

삽입정렬 (Insert Sort) - 카드 놀이를 할 때 손에 들고 있는 카드를 정렬하는 것과 유사함 - 오른쪽으로 움직이며 차례로 원소를 적절한 위치에 삽입하고 나머지 원소는 하나씩 오른쪽으로 이동시킴 특징 - 레코드를 계속 이동시켜야 하므로 레코드의 크기가 큰 경우에 불리 - 거의 정렬이 된 화일인 경우 유리 - 안정적인 제자리 정렬 - 더미(dummy) 키가 필요함 삽입과정 수행과정 성능 특성 - 시간 복잡도 O(N 2) - 거의 정렬된 화일의 경우 효율적임

버블정렬 (Bubble Sort) - 마치 거품이 물 위로 올라가는 것 같이 큰 값이 뒤로 가며, 결국 루프를 한번 반복할 때 마다 가장 큰 값을 가진 원소가 가장 뒤쪽으로 이동 특징 - 레코드를 계속 교환하므로 레코드의 크기가 큰 경우 좋지 않음 - 거의 정렬이 된 화일일 경우 좋음 - 안정적인 제자리 정렬 수행과정 성능 특성 - N 개의 원소 각각에 대해 N-1 번의 비교 - 전체 비교 횟수 N(N-1)/2 - 전체 시간 복잡도 O(N2)

선택정렬 (Selection Sort) - 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하고.. 이러한 방식으로 전체가 정렬될 때까지 계속함 특징 - 레코드가 실제로 교환되는 것은 많아야 한번 뿐이므로 작은 키와 매우 큰 레코드를 가지는 화일을 정렬하는데 적합 - 실행 시간은 입력 자료의 순서에 민감하지 않음 - 제자리 정렬 - 현재 값과 가장 작은 값을 교환할 때 현재 값이 어디로 갈지 알 수없으므로 불안정 수행과정 성능 특성 - n개의 원소 각각에 대해 n-1 번 비교 - 전체 비교 횟수 n(n-1)/2 - 전체 시간 복잡도 O(n^2) - 큰 레코드와 작은 키를 가지는 화일의 경우 효율적 소스 코드 #include #include #incl..