Sorting - GitDeveloperKim/DreamEach GitHub Wiki
public static void bubble_sort () {
for (int i = 0; i < N-1; i++) {
for (int j = 0; j < N-1; j++) {
if (arr[j] > arr[j+1]) {
swap (j, j+1);
count++;
}
}
}
}
선택정렬 개념 click
삽입정렬 개념 click
- 가장 큰 데이터와 가장 작은 데이터의 차이가 100_0000 이하일때 사용
public static void merge_sort (int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
merge_sort(start, middle);
merge_sort(middle+1, end);
func_merge(start, middle, end);
}
}
public static void func_merge(int start, int middle, int end) {
int left = start; // 왼쪽 배열 참고
int right = middle + 1; // 오른쪽 배열 참고
int idx = left;
arr_merge = new int[N];
while (left <= middle && right <= end) {
if (arr[left] < arr[right]) {
arr_merge[idx++] = arr[left++];
} else {
arr_merge[idx++] = arr[right++];
count += middle + 1 - left;
}
}
if (left <= middle) {
while (left <= middle) {
arr_merge[idx++] = arr[left++];
}
} else {
while (right <= end) {
arr_merge[idx++] = arr[right++];
}
}
for (int i = start; i <= end; i++) {
arr[i] = arr_merge[i];
}
}
// quick sort
static void quickSort(int first, int last)
{
int temp;
if (first < last)
{
int pivot = first;
int i = first;
int j = last;
while (i < j)
{
while (input[i] <= input[pivot] && i < last)
{
i++;
}
while (input[j] > input[pivot])
{
j--;
}
if (i < j)
{
temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
temp = input[pivot];
input[pivot] = input[j];
input[j] = temp;
quickSort(first, j - 1);
quickSort(j + 1, last);
}
}