목차
- QuickSort
- InsertionSort
- RadixSort
- MergeSort
- HeapSort
내용
QuickSort
import java.util.Arrays;
public class QuickSort {
public static int[] quickSort(int[] arr) {
// TODO:
quickSort(arr,0,arr.length-1); //퀵정렬
return arr; //정렬된 배열
}
public static void quickSort(int[]arr, int start, int end){
int part2 = partition(arr,start,end); //bigger의 첫번째 인덱스 값
if(start < part2 - 1) //smaller가 2개 이상
quickSort(arr,start,part2-1);
if(part2 < end) //bigger가 2개이상
quickSort(arr,part2,end);
}
//정렬
public static int partition(int[] arr, int start, int end){
int pivot = arr[(start+end)/2]; //중간 값
//start:맨앞부터 1칸씩 뒤로, end:맨뒤부터 1칸씩 앞으로
while(start <= end){ //start가 end보다 작을 동안
while(arr[start] < pivot) start++; //작은값 pass
while(arr[end] > pivot) end--; //큰값 pass
if(start <= end){ //아직 교차x
//swap
swap(arr,start,end);
//한칸씩
start++;
end--;
}
}
return start; //bigger의 첫번째 인덱스
}
private static void swap(int[] arr, int start, int end){
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
public static void main(String[] args) {
int[] output = quickSort(new int[]{3, 1, 21});
System.out.println(Arrays.toString(output)); // --> [1, 3, 21]
}
}QuickSort는 대표적인 양쪽에서 반대편으로 정렬하는 Sorting입니다.
- 중간에 위치한 임의의 값을 기준으로 왼쪽의 큰 값은 오른쪽으로 오른쪽의 큰 값은 왼쪽으로 교환합니다.
- 정렬된 값의 smaller와 bigger가 2개이상일 시 각각 다시 재귀적으로 sorting을 수행합니다.
왼쪽과 오른쪽에서 동시에 반대방향을 향해 인덱스가 이동하는 점을 유의해야합니다.
InsertionSort
import java.util.Arrays;
public class InsertionSort {
public static int[] insertionSort(int[] arr) {
// TODO:
for(int i = 1; i< arr.length; i++){
//현재 이동할 원소
int now = arr[i];
//한칸 앞부터
int j = i - 1;
//0까지 앞의 원소들이 클 동안
while(j >= 0 && arr[j] > now){
//앞의 원소들을 한칸뒤로 미룸
arr[j+1] = arr[j];
j--;
}
//해당 원소는 현재 원소 삽입
arr[j+1] = now;
}
//배열 반환
return arr;
}
public static void main(String[] args) {
int[] output = insertionSort(new int[]{3, 1, 21});
System.out.println(Arrays.toString(output)); // --> [1, 3, 21]
}
}InsertionSort는 구현이 매우 용이한 Sorting입니다. 현재기준 앞으로 이동하며 값을 비교하는 Sorting입니다.
i번째 인덱스의 요소 값 n보다 크다면 j번째 요소들은 한 칸 뒤로 씩 미룹니다.
now변수에 저장해둔 값을 자기보다 작은 값 뒤에 삽입합니다.
RadixSort
import java.util.Arrays;
public class RadixSort {
public static int[] radixSort(int[] arr){
//최댓값 구하기
int max = Arrays.stream(arr).max().getAsInt();
//자릿수 별로 countingSort
for(int radix = 1; radix <= max; radix *= 10){
arr = countingSort(arr,radix);
}
return arr;
}
private static int[] countingSort(int[] arr, int radix){
//결과를 저장할 배열
int[] result = new int[arr.length];
//해당 자리수의 숫자를 저장할 배열
int[] counting = new int[10];
//숫자의 갯수를 구함
for(int i = 0; i < arr.length; i++){
int num = (arr[i] / radix) % 10;
counting[num]++;
}
//숫자별 마지막 위치를 구함
for(int i = 1; i < counting.length; i++)
counting[i] += counting[i-1];
//stable 하므로 이전에 정렬되었던 순서가 현재 졍렬에도 반영됨 -> 이전 자리수가 현재 자리수에도 반영이 됨
for(int i = arr.length-1;i>=0;i--){
int num = (arr[i]/radix) % 10; //현재 자리수
counting[num]--; //해당 자리수의 위치 -1하면 들어갈 위치
result[counting[num]] = arr[i]; //counting[num]은 해당 자릿수가 들어갈 위치가 저장되어있음
}
return result;
}
public static void main(String[] args) {
int[] output = radixSort(new int[]{3, 1, 21});
System.out.println(Arrays.toString(output)); // --> [1, 3, 21]
}
}RadixSort는 자리수 별로 정렬을 하여 최종적으로 모든 자리수를 정렬하면 값 자체가 정렬되는 Sorting입니다. 자리수 별로 정렬이 stable하여 다음 정렬의 순서에 영향을 줍니다.
stable이란 만약 현재의 정렬에서 동일한 값이 나온다면 이전 정렬 순서를 반영하여 순서를 정하는 상태입니다.
10의 자리가 같다면 같은 값 끼리는 1의자리 순서를 따릅니다. 100의 자리가 같다면 같은 값 끼리는 10의 자리, 1의 자리 순서를 따릅니다.
n번째 자리를 정렬하는 것은 실제로 n-1, n-2, .... , 1 번째 자리를 모두 고려하는 것과 동일합니다.
또 counting이라는 배열을 사용하여 갯수를 구하고 갯수를 활용하여 요소의 마지막 위치를 지정합니다.
1의 마지막 위치는 0의 마지막 위치 + 1의 갯수, 2의 마지막 위치는 1의 마지막 위치 + 2의 갯수, ... ,n의 마지막 위치는 n-1의 마지막 위치 + n의 갯수가 됩니다.
MergeSort
import java.util.Arrays;
public class MergeSort {
public static int[] mergeSort(int[] arr) {
// TODO :
//mergeSort는 2단계로 이루어집니다.
//재귀적으로 1/2로 나누고
//그때마다 sorting을 합니다.
//임시로 저장할 배열을 선언합니다ㅣ.
int[] tmp = new int[arr.length];
//재귀적으로 1/2로 나누고 sorting
mergeSort(arr,tmp,0,arr.length-1);
return arr;
}
private static void mergeSort(int[] arr, int[] tmp, int start, int end){
//시작이 끝보다 작다면
if(start < end){
int mid = (start + end) / 2; //중간 인덱스구함
mergeSort(arr,tmp,start,mid); //앞부분을 다시 재귀적으로
mergeSort(arr,tmp,mid+1,end); //뒷부분을 다시 재귀적으로
merge(arr,tmp,start,mid,end); //sorting
}
}
private static void merge(int[] arr, int[] tmp, int start, int mid, int end){
//arr -> tmp로 복사
for(int i = 0; i < arr.length; i++){
tmp[i] = arr[i];
}
//tmp 앞부분 or tmp 뒷부분 -> arr합한부분
int part1 = start; //tmp 앞부분
int part2 = mid + 1; //tmp 뒷부분
int index = start; //arr 합한부분
//part1과 part2가 남아있을 때 까지
while(part1 <= mid && part2 <= end){
if(tmp[part1] <= tmp[part2]){ //part1이 더 작을 경우
arr[index] = tmp[part1]; //arr에 삽입
part1++; //part1 한 칸 뒤로
}else{ //part2가 더 작을 경우
arr[index] = tmp[part2]; //arr에 삽입
part2++; //part2 한 칸 뒤로
}
index++; //arr 한칸 뒤로
}
//part1이 남을 경우 나머지 부분 삽입
for(int i = 0; i <= mid - part1; i++){
arr[index + i] = tmp[part1 + i];
}
//part2가 남는 경우는 위에 arr의 뒷부분이 이미 part2의 뒷부분으로 정렬되어 있음
}
public static void main(String[] args) {
int[] output = mergeSort(new int[]{3, 1, 21});
System.out.println(Arrays.toString(output)); // --> [1, 3, 21]
}
}MergeSorting은 2단계로 진행 할 수있습니다.
- 1/2로 나누어 앞부분 뒷부분을 재귀 호출합니다.
- 나눈 부분을 다시 합치어 Sorting을 수행합니다.
MergeSorting은 1/2씩 나누어 더 적은 수를 저장하는 배열, 둘 중 더 작은 수를 저장하는 배열 2개가 필요합니다.
tmp배열을 두 파트로 나누고 매번 더 작은 수를 선택하여 arr변수에 저장하였습니다.
참고로 앞부분이 남는다면 나머지 부분을 입력해야 하지만, 뒷부분이 남는것은 이미 정렬되어 저장되어 있기 때문에 그냥 둬도 상관 없습니다.
HeapSort
import java.util.Arrays;
public class HeapSort {
public static int[] heapSort(int[] arr){
//힙 삽입
heap_insert(arr);
//힙 삭제(정렬)
heap_delete(arr);
return arr;
}
private static void heap_insert(int[] arr){
//결과 배열 (0번째는 안쓰므로 +1)
int[] temp = new int[arr.length+1];
//삽입할 위치, 0번 째는 안씀
int index = 1;
//요소 하나씩 삽입
for(int num: arr){
//마지막 노드에 삽입
temp[index] = num;
//부모노드와 비교
int parent = index / 2;
int child = index;
//부모 노드가 0보다 클때 까지
while(parent > 0){
//부모노드가 더 작다면 멈춤
if(temp[parent] <= temp[child]) break;
//부모와 자식을 바꿈
int swap = temp[parent];
temp[parent] = temp[child];
temp[child] = swap;
//부모와 자식은 다음 위치로
child = parent;
parent = parent / 2;
}
index++;
}
System.arraycopy(temp,1,arr,0,arr.length);
}
private static void heap_delete(int[] arr){
//temp배열에 arr 복사, 0번째 인덱스는 사용 x
int[] temp = new int[arr.length + 1];
System.arraycopy(arr,0,temp,1,arr.length);
//요소를 삭제할 위치
int index = temp.length-1;
for(int i = 0; i< arr.length;i++){
//root의 요소 제거(최소값)
arr[i] = temp[1];
//마지막 노드를 루트로 이동
temp[1] = temp[index];
//이동할 위치
int parent = 1;
int child = 2;
//child가 마지막 노드까지
while(child <= index){
//우측 자식 노드가 더 작으면 우측 자식 노드와 비교
if(child < index && temp[child] > temp[child+1]) child++;
//부모 노드가 자식노드보다 작거나 같으면 그만 비교
if(temp[parent] <= temp[child]) break;
//자식 노드와 부모노드 값 swap
int swap = temp[parent];
temp[parent] = temp[child];
temp[child] = swap;
//부모노드와 자식노드 위치 아래로
parent = child;
child = child * 2;
}
//마지막 노드 한칸 앞으로
index--;
}
}
public static void main(String[] args) {
int[] output = heapSort(new int[]{5, 4, 3, 2, 1});
System.out.println(Arrays.toString(output)); // --> [1, 2, 3, 4, 5]
output = heapSort(new int[]{3, 1, 21});
System.out.println(Arrays.toString(output)); // --> [1, 3, 21]
output = heapSort(new int[]{4, 10, 3, 5, 1});
System.out.println(Arrays.toString(output)); // --> [1, 3, 4, 5, 10]
}
}Heap Sort는 binary Heap tree를 활용합니다. Heap Tree를 활용하여 정렬하는 과정입니다.
Min Heap Tree의 root는 트리에서 최솟값 입니다. Max Heap Tree의 root는 트리에서 최댓값 입니다.
트리를 구성하고, 매번 root를 추출하면 정렬된 배열을 획득 가능합니다.
heap_insert는 heap 트리를 구성하였습니다. heap은 완전 이진 트리이므로 배열로 구성이 가능합니다. 삽입은 항상 마지막 노드에 삽입하고, 부모 노드와 비교하며 값이 더 클 때까지 상위 level로 올라가며 부모노드와 swap합니다.
heap_delete는 heap트리의 root가 항상 최댓값이거나 최솟값임을 이용하여 root만 제거합니다. root를 제거후 마지막 노드를 root로 삽입하고 왼쪽 자식노드,오른쪽 자식노드와 비교합니다. 부모 노드가 제일 작으면 멈추고, 왼쪽 자식노드가 제일 작으면 왼쪽 자식노드와 부모를, 오른쪽 자식노드가 제일 작으몬 오른쪽 자식노드와 부모를 swap하고 하위 level로 내려갑니다.
heap tree를 저장한 배열에서 배열의 크기만큼 root 노드만 추출하면? 당연히 정렬된 값들이 나올 것입니다.
GitHub
오늘도 내일도 화이팅!