[Java / 알고리즘] 정렬 알고리즘

정렬 알고리즘

데이터를 특정한 기준에 따라 순서대로 정렬하는 알고리즘

특징

시간 복잡도 : 일부 알고리즘은 작은 데이터 집합에 대해 빠르지만, 큰 데이터 집합에 대해 느릴 수 있다. 알고리즘의 시간 복잡도를 고려하여 적절한 정렬 알고리즘을 선택해야 한다.
안정성 :안정적인 정렬 알고리즘은 동일한 값의 순서가 바뀌지 않는 특징을 가지고 있다. 이는 동일한 값을 가진 요소들의 순서가 변하지 않도록 보장된다.
추가 메모리 사용 : 몇몇 정렬 알고리즘은 추가적인 메모리 공간을 필요로 한다. 정렬 알고리즘을 선택할 때 고려해야 할 요소 중 하나이다. 메모리 효율적인 알고리즘을 선호해야 한다.
알고리즘 복잡성 : 정렬 알고리즘의 복잡성은 알고리즘의 이해와 구현의 어려움을 의미한다. 몇몇 알고리즘은 간단하고 이해하기 쉽지만, 다른 알고리즘은 복잡하고 이해하기 어렵다.

종류

이미지 출처 : https://adjh54.tistory.com/334

알고리즘 종류	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	보조 메모리	안정성
버블 정렬(Bubble Sort)	n	n²	n²	1	O
삽입 정렬(Insertion Sort)	n	n²	n²	1	O
선택 정렬(Selection Sort)	n²	n²	n²	1	X
합병 정렬(Merge Sort)	nlogn	nlogn	nlogn	n	O
힙 정렬(Heap Sort)	nlogn	nlogn	nlogn	1	X
퀵 정렬(Quick Sort)	nlogn	nlogn	n²	logn	X
기수 정렬(Radix Sort)	dn	dn	dn	n+k	O
계수 정렬(Counting Sort)	n+k	n+k	n+k	n+k	O
셸 정렬(Shell Sort)	nlogn	gap에 따라 다름	n²	1	X

💡d : 정렬 대상 데이터 최대 자릿수, k : 정렬 대상 데이터 중 최댓값

버블 정렬

• 인접한 데이터를 비교하며 자리 바꾸는 형식

동작 과정

public static void bubbleSort(int[] arr) {
	for(int i=1; i<arr.length; i++) {
    	for(int j=0; j<i; j++) {
        	if(arr[j]>arr[j+1]) {
            	int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

삽입 정렬

• 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식

동작 과정

public static void insertionSort(int[] arr) {
	for(int i=1; i<arr.length; i++) {
    	for(int j=i; j>0; j--) {
        	if(arr[j]<arr[j-1]) {
            	int tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            } else break;
        }
    }
}

선택 정렬

• 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식

동작 과정

public static void selectionSort(int[] arr) {
	for(int i=0; i<arr.length-1; i++) {
    	int min = i;
    	for(int j=i+1; j<arr.length; j++) {
        	if(arr[j]<arr[min]) {
            	min = j;
            }
            int tmp = arr[j];
            arr[j] = arr[min];
            arr[min] = tmp;
        }
    }
    
	for(int i=arr.length-1; i>0; i--) {
    	int max = i;
    	for(int j=i-1; j>=0; j--) {
        	if(arr[j]>arr[max]) {
            	max = j;
            }
            int tmp = arr[j];
            arr[j] = arr[max];
            arr[max] = tmp;
        }
    }
}

합병 정렬

• 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식

동작 방식

public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
	if(left<right) {
    	int mid = (left+right)/2;
        mergeSort(arr, tmp, left, ,mid);
        mergeSort(arr, tmp, mid+1, right);
        merge(arr, tmp, left, right, mid);
    }
}

public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
	int p = left;
    int q = mid+1;
    int idx = p;
    
    while(p<=mid || q<=right) {
    	if(p<=mid && q<=right) {
        	if(arr[p]<=arr[q]) {
            	tmp[idx++] = arr[p++];
            } else {
            	tmp[idx++] = arr[q++];
            }
        } else if(p<=mid && q>right) {
        	tmp[idx++] = arr[p++];
        } else {
        	tmp[idx++] = arr[q++];
        }
    }
    
    for(int i=left; i<=right; i++) {
    	arr[i] = tmp[i];
    }
}

public static void main(String[] args) {
	int[] arr = {6, 2, 7, 9, 4, 5, 8};
    int[] tmp = new int[arr.length];
    mergeSort(arr, tmp, 0, arr.length-1);
}

힙 정렬

• 힙 자료구조 형태의 정렬 방식
• 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행

public static void heapSort(int[] arr) {
	for(int i=arr.length/2-1; i>=0; i--) {
    	heapify(arr, i, arr.length);
    }
    
    for(int i=arr.length-1; i>0; i--) {
    	swap(arr, 0, i);
        heapify(arr, 0, i);
    }
}

public static void heapify(int[] arr, int parentIdx, int size) {
	int leftIdx = 2*parentIdx + 1;
    int rightIdx = 2*parentIdx + 2;
    int madIdx = parentIdx;
    
    if(leftIdx<size && arr[maxIdx]<arr[leftIdx]) {
    	maxIdx = leftIdx;
    }
    
    if(rigthIdx<size && arr[maxIdx]<arr[rigthIdx]) {
    	maxIdx = rigthIdx;
    }
    
    if(parentIdx!=maxIdx) {
    	swap(arr, maxIdx, parentIdx);
        heapify(arr, maxIdx, size);
    }
}

public void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void main(String[] args) {
	int[] arr = {6, 2, 7, 9, 4, 5, 8};
    heapSort(arr);
}

퀵 정렬

• 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

동작 방식

public static void quickSort(int[] arr, int left, int right) {
	if(left >= right) return;
    
    int pivot = partition(arr, left, right);
    
    quickSort(arr, left, pivot-1);
    quickSort(arr, pivot+1, right);
}

public static int partition(int[] arr, int left, int right) {
	int pivot = arr[left];
    int i = left;
    int j = right;
    
    while(i<j) {
    	while(arr[j]>pivot && i<j) {
        	j--;
        }
        
        while(arr[j]<=pivot && i<j) {
        	i--;
        }
        swap(arr, i, j);
    }
    swap(arr, left, i);
    
    return i;
}

public void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void main(String[] args) {
	int[] arr = {6, 2, 7, 9, 4, 5, 8};
    quickSort(arr, 0, arr.length-1);
}

기수 정렬

• 낮은 자리 수부터 정렬하는 방식
• 각 원소간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요

동작 방식

public static void radixSort(int[] arr) {
	ArrayList<Queue<Integer>> list = new ArrayList<>();
    for(int i=0; i<10; i++) {
    	list.add(new LinkedList<>);
    }
    
    int idx=0;
    int div=1;
    int maxLen = getMaxLen(arr);
    
    for(int i=0; i<maxLen; i++) {
    	for(int j=0; j<arr.length; j++) {
    		list.get((arr[j]/div)%10).offer(arr[j]);
    	}	
        
        for(int i=0; i<10; i++) {
            Queue<Integer> q = list.get(j);
            
            while(!q.isEmpty()) {
            	arr[idx++] = q.poll();
            }
        }
        
        idx = 0;
        div *= 10;
    }
}

public static int getMaxLen(int[] arr) {
	int maxLen = 0;
    for(int i=0; i<arr.length; i++) {
    	int len = (int) Math.log10(arr[i])+1;
        if(maxLen<len) {
        	maxLen = len;
        }
    }
    return maxLen;
}

계수 정렬

• 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리 필요

동작 방식

public static void countingSort(int[] arr) {
	int max = Arrays.stream(arr).max().getAsInt();
    int[] cntArr = new int[max+1];
    
    for(int i=0; i<arr.length; i++) {
    	cntArr[arr[i]]++;
    }
    
    int idx = 0;
    for(int i=0; i<cntArr.length; i++) {
    	while(cntArr[i]>0) {
        	arr[idx++] += i;
            cntArr[i] -= 1;
        }
    }
    
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int item : arr) {
    	map.put(item, map.getOrDefault(item, 0)+1);
    }
    
    int idx2 = 0;
    ArrayList<Integer> list = new ArrayList<>(map.keySet());
    Collections.sort(list);
    
    for(int i=0; i<list.size(); i++) {
    	int cnt = map.get(list.get(i));
        while(cnt>0) {
        	arr[idx2++] = list.get(i);
            cnt--;
        }
    }
}

셸 정렬

• 삽입 정렬의 약점 보완한 정렬 방식
• 삽입 정렬의 약점
  • 오름차순, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환 필요
• 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교

동작 방식

public static void shellSort(int[] arr) {
	int gap = arr.length/2;
    
    for(int g=gap; g>0; g/=2) {
    	for(int i=g; i<arr.length; i++) {
        	int tmp = arr[i];
            
            int j=0;
            for(j=i-g; j>=0; j-=g) {
            	if(arr[j]>tmp) {
                	arr[j+g] = arr[j];
                } else {
                	break;
                }
            }
            arr[j+g] = tmp;
        }
    }
}