글 목차
728x90
정렬 알고리즘을 구현해 봤다
버블, 셀렉, 삽입, 퀵, 병합, 힙
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int [] data = {3,5,2,1,7,9};
// 버블정렬(data);
// 선택정렬(data);
// 삽입정렬(data);
// 퀵정렬(data);
// 합병정렬(data);
}
/**
* 버블 정렬을 구현해 봐요
* <div>
* 구현이 단순하나 O(N^2)로 비효율 적이에요
* <br>
* 안정정렬 이에요 (같은 값의 데이터의 순서는 유지되요)
* </div>
* @Author Okane
* @Param data 정렬을 수행 할 배열이에요
* @Return 정렬을 수행한 배열을 뱉어요
*/
static void 버블정렬(int [] data) {
System.out.println("버블소트에요!");
for (int i = 0; i < data.length; i++) { // i는 소트 알고리즘의 회전수를 의미해요
for (int j = 1; j < data.length; j++) {
if (data[j-1] > data[j]) { // data를 한바퀴 돌면서 인접한 두 수의 크기를 비교해 스왑해 줘요
int a = data[j-1], b = data[j];
data[j-1] = b; data[j] = a;
}
}
}
System.out.println(Arrays.toString(data));
}
/**
* <b>선택 정렬을 구현해 봐요</b>
* <div>
* 구현이 단순하나 O(N^2)로 비효율 적이에요
* <br>
* 불안정정렬 이에요(같은 값의 데이터의 순서가 유지되는 것이 보장되지 않아요)
* </div>
* @Author Okane
* @Param data 정렬을 수행 할 배열이에요
* @Return 정렬을 수행한 배열을 뱉어요
*/
static void 선택정렬(int [] data) {
System.out.println("선택정렬이에요!");
for (int i = 0; i < data.length; i++) { // i는 해당 사이클에서 최소값을 넣을 index를 의미해요
int min_index = -1;
int min_value = Integer.MAX_VALUE;
for (int j = i; j < data.length; j++) { // 해당 사이클에서 최소값을 찾아요
if (min_value >= data[j]) {
min_index = j;
min_value = data[j];
}
}
int temp = data[i];
data[i] = min_value;
data[min_index] = temp; // 골라진 최소값을 해당 사이클의 가장앞과 스왑해요
}
System.out.println(Arrays.toString(data));
}
/**
* <b>삽입 정렬을 구현해 봐요</b>
* <div>
* 버블 소트와 비슷한 원리
* <br>
* 평균적과 최악은 O(n^2)로 비효율 적이나 최선의 경우(즉 데이터가 많이 정렬이 되있는 상태라면) O(n)로 효율적이에요
* <br>
* 안정정렬이에요
* </div>
* @Author Okane
* @Param data 정렬을 수행 할 배열이에요
* @Return 정렬을 수행한 배열을 뱉어요
*/
static void 삽입정렬(int [] data) {
System.out.println("삽입정렬이에요!");
for (int i = 1; i < data.length; i++) { // i는 해당 사이클에서 정렬할 index값이에요
for (int j = i-1; j >= 0; j--) {
if (data[j] > data[j+1]) {
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
continue;
}
break;
}
}
System.out.println(Arrays.toString(data));
}
/**
* <b>퀵 정렬을 구현해 봐요</b>
* <div>
* 분할 정복을 사용하여 정렬을 구현하는 알고리즘이에요
* <br>
* 평균적으로 O(nlogn)으로 굉장히 속도가 빨라요
* <br>
* 불안정정렬이에요
* </div>
* @Author Okane
* @Param data 정렬을 수행 할 배열이에요
* @Return 정렬을 수행한 배열을 뱉어요
*/
static void 퀵정렬(int [] data) {
System.out.println("퀵 정렬이에요!");
System.out.println(Arrays.toString(퀵정렬_도우미(data)));
}
static int [] 퀵정렬_도우미(int [] data) {
if (data.length <= 1) return data; // 만약 피벗을 구할 필요가 없을 정도로 데이터가 짧다면 리턴해요
int pivot = data[0]; // 기준을 정해요
ArrayList<Integer> left = new ArrayList<>(), right = new ArrayList<>(); // 기준보다 적은건 left, 큰건 right에 넣어요
for (int i = 1; i < data.length; i++) {
if (data[i] <= pivot) left.add(data[i]);
else right.add(data[i]);
}
int [] left_array = new int [left.size()]; // 배열로 타입변환
for (int i = 0; i < left.size(); i++) {
left_array[i] = left.get(i);
}
left_array = 퀵정렬_도우미(left_array); // 분할된 배열을 다시 헬퍼로 보내요
int [] right_array = new int [right.size()]; // 배열로 타입변환
for (int i = 0; i < right.size(); i++) {
right_array[i] = right.get(i);
}
right_array = 퀵정렬_도우미(right_array); // 분할된 배열을 다시 헬퍼로 보내요
int [] answer = new int [data.length]; // 답을 적을 배열을 선언해요
for (int i = 0; i < left_array.length; i++) { // 기준을 기준으로 왼쪽을 채워요
answer[i] = left_array[i];
}
answer[left_array.length] = pivot; // 기준을 채워요
for (int i = left_array.length+1, j = 0; i < data.length; i++, j++) { // 기준을 기준으로 오른쪽을 채워요
answer[i] = right_array[j];
}
return answer; // 리턴!
}
/**
* <b>퀵 정렬을 구현해 봐요</b>
* <div>
* 분할 정복을 사용하여 정렬을 구현하는 알고리즘이에요
* <br>
* 평균적으로 O(nlogn)으로 굉장히 속도가 빨라요, 최악의 경우에도 nlogn의 성능을 내요
* <br>
* 안정정렬이에요
* </div>
* @Author Okane
* @Param data 정렬을 수행 할 배열이에요
* @Return 정렬을 수행한 배열을 뱉어요
*/
static void 합병정렬(int [] data) {
System.out.println("합병 정렬이에요");
합병정렬_분할(data, 0, data.length-1);
System.out.println(Arrays.toString(data));
}
static void 합병정렬_분할(int [] data, int left, int right) {
if (left >= right) return;
int mid = (right + left) / 2;
합병정렬_분할(data, left, mid);
합병정렬_분할(data, mid+1, right);
합병정렬_병합(data, left, mid, right);
}
static void 합병정렬_병합(int [] data, int left, int mid, int right) {
int left_helper = left;
int right_helper = mid+1;
int index_helper = 0;
int [] sorted = new int [right - left + 1];
while (left_helper <= mid || right_helper <= right) {
if (left_helper > mid) {
sorted[index_helper++] = data[right_helper++];
continue;
}
else if (right_helper > right) {
sorted[index_helper++] = data[left_helper++];
continue;
}
if (data[left_helper] <= data[right_helper]) sorted[index_helper++] = data[left_helper++];
else sorted[index_helper++] = data[right_helper++];
}
for (int i = left, j = 0; i <= right; i++, j++) {
data[i] = sorted[j];
}
}
}
728x90