C언어로 구현한 정렬 알고리즘

swap

void swap(int *a, int *b) {
	int temp; 
	temp = *a; 
	*a = *b; 
	*b = temp;
}

 

1. Bubble sort

void bubbleSort(int arr[], int n) {
	for (int i = n-1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[j+1]) {
				swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}

 

2. Insertion sort

void insertionSort(int arr[], int n) {
	int val;
	for (int i = 1; i < n; i++) {
		val = arr[i];
		int j;
		for (j = i; j > 0; j--) {
			if (val < arr[j-1]) {
				arr[j] = arr[j - 1];
			}
			else {
				break;
			}
		}
		arr[j] = val;
	}
}

3. Selection sort

void selectionSort(int arr[], int n) {
	int min_idx;
	for (int i = 0; i < n - 1; i++) {
		min_idx = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[min_idx]) {
				min_idx = j;
			}
		}
		swap(&arr[i], &arr[min_idx]);
	}
}

4. Shell sort

void insertionSort2(int arr[], int first, int last, int h) {
	int val, pos;
	for (int i = first + h; i <= last; i += h) {
		val = arr[i];
		for (pos = i; pos > first; pos -= h) {
			if (val < arr[pos - h]) {
				arr[pos] = arr[pos - h];
			}
			else {
				break;
			}
		}
		arr[pos] = val;
	}
}

void shellSort(int arr[], int n) {
	for (int h = n / 2; h > 0; h = h / 2) {
		for (int i = 0; i < h; i++) {
			insertionSort2(arr, i, n - 1, h);
		}
	}
}

5. Quick sort

int partition(int arr[], int begin, int end) {
	int pivot = begin;
	int L = begin;
	int R = end;
	while (L < R) {
		while (arr[L] <= arr[pivot] && L < end) {
			L++;
		}
		while (arr[R] > arr[pivot]) {
			R--;
		}
		if (L < R) {
			swap(&arr[L], &arr[R]);
		}
	}
	swap(&arr[pivot], &arr[R]);
	return R;
}

void quickSort(int arr[], int begin, int end) {
	int pivot;
	if (begin < end) {
		pivot = partition(arr, begin, end);
		quickSort(arr, begin, pivot - 1);
		quickSort(arr, pivot + 1, end);
	}
}

6. Merge sort

void merge(int arr[], int begin, int end) {
	int mid = (begin + end) / 2;
	int size = end - begin + 1;
	int *temp = (int*)malloc(sizeof(int) * size);

	int i = begin, j = mid + 1, k = 0;

	while (i <= mid && j <= end) {
		temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	}
	if (i <= mid) {
		while (i <= mid) {
			temp[k++] = arr[i++];
		}
	}
	else {
		while (j <= end) {
			temp[k++] = arr[j++];
		}
	}
	for (i = 0; i < size; i++) {
		arr[i + begin] = temp[i];
	}

	free(temp);
}

void mergeSort(int arr[], int begin, int end) {
	if (begin < end) {
		int mid = (begin + end) / 2;
		mergeSort(arr, begin, mid);
		mergeSort(arr, mid + 1, end);
		merge(arr, begin, end);
	}
}