Sorting.h : 다양한 정렬을 포함한 헤더

| 정렬 방법의 성능 비교

알고리즘	최선	평균	최선
삽입 정렬
선택 정렬
버블 정렬
셸 정렬
퀵 정렬
힙 정렬
합병 정렬
기수 정렬

| 정렬 알고리즘별 실험 결과 ( 정수 : 60,000개 )

알고리즘	실행 시간( 단위 : sec)
삽입 정렬	7.348
선택 정렬	10.842
버블 정렬	22.894
셸 정렬	0.056
힙 정렬	0.034
합병 정렬	0.026
퀵 정렬	0.014

---

#pragma once

#ifndef ___Sorting

#define ___Sorting

// Sorting.h : 다양한 정렬을 포함한 헤더

#include "cstdio"

#include "cstdlib"

#include "CircularQueue.h"

#define MAX_SIZE 1024

#define BUCKETS 10

#define DIGITS 4

// 랜덤 함수를 이용하여 int 배열을 0~max-1 의 값으로 무작위로 채우는 함수

static void initRandom(int list[], int n, int max = 100) {

for (int i = 0; i < n; i++)

list[i] = rand() % max;

}

// 배열을 화면에 보기 좋게 출력하는 함수. 디폴트 매개변수 사용

static void printArray(int arr[], int n, const char *str = "Array") {

printf("%s = ", str);

for (int i = 0; i < n; i++)

printf("%3d", arr[i]);

printf("\n");

}

// 두 정수를 교환하는 함수 : inline 함수. 매개변수로 레퍼런스형 사용.

inline void swap(int& x, int& y) {

int t = x;

x = y;

y = t;

}

// 선택정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void selectionSort(int A[], int n) {

for (int i = 0; i < n - 1; i++) { // n-1번만 반복

int least = i;

for (int j = i + 1; j < n; j++) //최솟값 탐색

if (A[j] < A[least]) least = j;

swap(A[i], A[least]);

}

}

// 삽입정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 - 안정 정렬

void insertionSort(int A[], int n){

for (int i = 1; i < n; i++) {

int key = A[i];

int j;

for (j = i - 1; j >= 0 && A[j] > key; j--)

A[j + 1] = A[j]; // 레코드의 오른쪽으로 이동

A[j + 1] = key;

}

}

inline int ascend(int x, int y) { return y - x; } //오름차순 비교함수

inline int descend(int x, int y) { return x - y; } //오름차순 비교함수

// 함수 포인터를 매개변수로 받는 삽입정렬 함수

void insertionSortFn(int A[], int n, int(*f)(int, int)){

for (int i = 1; i < n; i++) {

int key = A[i];

int j;

for (j = i - 1; j >= 0 && f(A[j], key) < 0; j--)

A[j + 1] = A[j];

A[j + 1] = key;

}

}

// 버블 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void bubbleSort(int A[], int n) {

for (int i = n - 1; i > 0; i--) {

for (int j = 0; j < i; j++)

//앞뒤의 레코드를 비교한 후 교체

if (A[j] > A[j + 1])

swap(A[j], A[j + 1]);

}

}

// gap 만큼 떨어진 요소들을 삽입 정렬. 정렬의 범위는 first 에서 last

static void sortGapInsertion(int A[], int first, int last, int gap) {

int i, j, key;

for (i = first + gap; i <= last; i = i + gap) {

key = A[i];

for (j = i - gap; j >= first && key < A[j]; j = j - gap)

A[j + gap] = A[j];

A[j + gap] = key;

}

}

// 셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void shellSort(int A[], int n) {

for (int gap = n / 2; gap > 0; gap = gap / 2) {

printArray(A, n, "ShellSort"); // 처리과정을 보기 위한 코드

if ((gap % 2) == 0) gap++;

for (int i = 0; i < gap; i++) // 부분 리스트의 개수는 gap

sortGapInsertion(A, i, n - 1, gap);

}

}

static void merge(int A[], int left, int mid, int right) {

int i, j, k = left, l; // k는 정렬될 리스트에 대한 인덱스

static int sorted[MAX_SIZE];

// 분할 정렬된 A의 합병

for (i = left, j = mid + 1; i <= mid && j <= right;)

sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];

// 한쪽에 남아 있는 레코드의 일괄 복사

if (i > mid)

for (l = j; l <= right; l++, k++)

sorted[k] = A[l];

else

for (l = i; l <= mid; l++, k++)

sorted[k] = A[l];

// 배열 sorted[]의 리스트를 배열 A[]로 재복사

for (l = left; l <= right; l++)

A[l] = sorted[l];

}

// 합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void mergeSort(int A[], int left, int right) {

if (left < right) {

int mid = (left + right) / 2; // 리스트의 균등 분할

mergeSort(A, left, mid); // 부분 리스트 정렬

mergeSort(A, mid + 1, right); // 부분 리스트 정렬

merge(A, left, mid, right); // 합병

}

}

// 배열의 세 값중 중간값의 인덱스를 반환하는 함수

static int medianIndex(int A[],int left, int mid, int right) {

if (A[left] > A[mid]) {

if (A[mid] > A[right]) return mid;

else if (A[left] > A[right]) return right;

else return left;

}

else {

if (A[left] > A[right]) return left;

else if (A[mid] > A[right]) return right;

else return mid;

}

}

// 퀵 정렬에서 partition() 함수

static int partition(int A[], int left, int right) {

int low = left;

int high = right + 1;

int min = medianIndex(A, left, (left + right) / 2, right); //중간값의 인덱스 선택

swap(A[left], A[min]); // 중간값의 인덱스를 왼쪽 데이터와 교환

int pivot = A[left]; // 피벗 설정

do {

do { // 왼쪽 리스트에서 피벗보다 클 레코드 선택

low++;

} while (low <= right && A[low] < pivot);

do {

high--; // 오른쪽 리스트에서 피벗보다 큰 레코드 선택

} while (high >= left && A[high] > pivot);

if (low < high) // 선택된 두 레코드 교환

swap(A[low], A[high]);

} while (low < high); // 인덱스 low, right 가 엇갈리지 않는 한 반복

swap(A[left], A[high]); // 인덱스 high 가 가리키는 레코드와 피벗 교환

return high;

}

// 퀵 정렬 알고리즘을 이용해 배열의 left ~ right 항목들을 오름차순으로 정렬하는 함수

void quickSort(int A[], int left, int right) {

if (left < right) { // 정렬 범위가 2개 이상인 경우

int  pivot = partition(A, left, right); // 좌우로 분할

quickSort(A, left, pivot - 1); // 왼쪽 부분리스트를 퀵 정렬

quickSort(A, pivot + 1, right); // 오른쪽 부분리스트를 퀵 정렬

}

}

// 두 수를 비교해 오름차순으로 정렬되도록 하는 함수

int compareAs(const void *arg1, const void *arg2) {

return (*(double *)arg1 > *(double *)arg2) ? 1 :

(*(double *)arg1 < *(double *)arg2) ? -1 : 0;

}

// 두 수를 비교해 내림차순으로 정렬되도록 하는 함수

int compareDe(const void *arg1, const void *arg2) {

return (*(double *)arg1 < *(double *)arg2) ? 1 :

(*(double *)arg1 > *(double *)arg2) ? -1 : 0;

}

// 기수 정렬 프로그램

void radixSort(int list[], int n) {

CircularQueue queues[BUCKETS];

int factor = 1;

for (int d = 0; d < DIGITS; d++) {

for (int i = 0; i < n; i++) // 데이터들은 자릿수에 따라 큐에 삽입

queues[(list[i] / factor) % 10].enqueue(list[i]);

int i;

for (int b = i =0; b < BUCKETS; b++) // 버킷에서 꺼내어 list로 합친다.

while (!queues[b].isEmpty())

list[i++] = queues[b].dequeue();

factor *= 10; // 그 다음 자릿수로 간다.

printArray(list, n, "RadixSort");

}

}

#endif // !___Sorting