-
[Algorithms] 정렬 알고리즘의 종류와 시간복잡도, 사용처 (+ Java 구현코드)Computer Basis/Algorithms 2021. 11. 8. 22:50
* 구현코드는 제일 아래에 있습니다.
* 개념정리는 없습니다 😞 위키 백과가 최고에요,,,
# 정렬알고리즘의 종류와 시간복잡도
Sort Best Avg Worst Details Selection Sort
(선택정렬)$$O(n^2)$$ $$O(n^2)$$ $$O(n^2)$$ Bubble Sort
(버블정렬)$$O(n^2)$$ $$O(n^2)$$ $$O(n^2)$$ Insertion Sort
(삽입정렬)$$O(n)$$ $$O(n^2)$$ $$O(n^2)$$ 어느정도 정렬된 데이터에 Best! Quick Sort
(퀵정렬)$$O(nlog_{2}n)$$ $$O(nlog_{2}n)$$ $$O(n^2)$$ 대부분 표준라이브러리에서 채택됨 Merge Sort
(병합정렬)$$O(nlog_{2}n)$$ $$O(nlog_{2}n)$$ $$O(nlog_{2}n)$$ * 공간복잡도 O(n) Heap Sort
(힙정렬)$$O(nlog_{2}n)$$ $$O(nlog_{2}n)$$ $$O(nlog_{2}n)$$ Counting Sort
(계수정렬)$$O(n+k)$$ $$O(n+k)$$ $$O(n+k)$$ * k = 데이터의 너비
* 공간복잡도 O(k)Radix Sort
(기수정렬)$$O(n)$$ $$O(nd)$$ $$O(nd)$$ * d = 데이터 최대 자릿수
* 공간복잡도 O(n+k)
* k = 도메인 크기
* 숫자일경우 k=10
# 사용처
1. Insertion Sort
- 이미 한번 sorting을 하고, 데이터를 추가로 받은경우 (최고의 효율)
2. Quick Sort
- Python 의 list.sort() , Java 의 Arrays.sort() 등 프로그래밍언어에서 기본적으로 지원되는 내장 정렬함수는 대부분 quick sort 이다.
- 평균적으로 성능이 좋기때문. 다만 이미정렬된 데이터에 quick sort를 실행하면 O(N^2)을 경험한다. 프로그래밍 대회에서는 대부분 테스트케이스에 퀵소트를 막기위한 테스트케이스가 있으므로, 다른 정렬알고리즘을 사용한다.
3. Merge Sort
- 추가적인 배열을 선언하므로, 다량의 데이터를 정렬할때 공간복잡도 문제로 인해 잘 쓰이지 않음
4. Heap Sort
- Merge Sort 와 다르게, 메모리공간을 차지하진 않으나, 평균적인 속도는 Quick Sort가 빠르므로 잘 쓰이지 않음
- 하지만 정렬이 목적이 아닌, 가장 크거나 작은값 몇개를 필요로 할때는 heapify로 빠르게 구할 수 있음
5. Counting Sort
- 메모리만 많다면 가장 빠른 정렬 알고리즘, O(N)에 끝나며, 공간복잡도는 O(N)보다 작다.
- 메모리가 적더라도, 정렬할 데이터의 크기범위가 작다면 가장 효율이 좋을 것이다.
- [N은 1억인데, 0< data <10 일 경우] : 시간복잡도 O(1억), 공간복잡도 O(10)
6. Radix Sort
- 이진문자열과 정수정렬에 가장 널리 적용된다.
- 부동소수점 실수와 같은 데이터에는 정렬을 적용할 수 없다.
- 최상의 경우에도 Merge Sort 와 같은 공간복잡도를 가진다.
# 구현 코드
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class sort { static void printArr(int[] arr){ for(int i=0;i<arr.length;i++){ System.out.printf("%2d ",arr[i]); } System.out.println(); } static void SWAP(int[] arr,int i, int j){ if(i==j || i>arr.length-1 || j>arr.length-1) return; int temp = arr[i]; arr[i]=arr[j]; arr[j]=temp; } static int[] selectionSort(int[] orginArr){ int[] arr=orginArr.clone(); //가장 작은걸 앞으로 보낸다. for(int i=0; i<arr.length; i++){ int min = 9999; int idx = i; for(int j=i;j<arr.length; j++){ if(min>arr[j]){ min=arr[j]; idx=j; } } SWAP(arr,i,idx); } return arr; } static int[] bubbleSort(int[] originArr){ int[] arr = originArr.clone(); // 두개를 비교해서 자리를바꾼다. 결과적으로 큰값을 오른쪽으로 보내버린다. for(int i=0;i<arr.length;i++){ for(int j=0; j< arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ SWAP(arr,j,j+1); } } } return arr; } static int[] insertionSort(int[] originArr){ int[] arr = originArr.clone(); // 기준 idx 왼쪽을 바라보며 적절한 위치를 찾아 끼워넣는다. for(int i=0;i<arr.length; i++){ for(int j=i;j>0;j--){ if(arr[j-1] > arr[j]){ SWAP(arr,j-1,j); } } } return arr; } //pivot 을 그냥 index 0 으로 static void basicQuickSort(int[] arr, int start, int end){ if(start>=end) return; int pivot = start; int left = pivot+1; int right = end; //왼쪽에서 오른쪽으로 진행 : pivot 보다 큰값 찾기 //오른쪽에서 왼쪽으로 진행 : pivot 보다 작은값 찾기 //그 값들을 swap //if left>right => swap(right,pivot) //엇갈렸다면 right와 pivot 을 교체 후, pivot 이 있는 자리를 기준으로 나눠서 같은 로직 진행 while(left<=right){ // idx 엇갈리면 break while(arr[left] <= arr[pivot]){ left++; if(left>end) break; } while((arr[right] >= arr[pivot]) && right>start){ right--; } if(left>right){ // idx 엇갈렸다면 swap(right,pivot) SWAP(arr, pivot, right); }else{ SWAP(arr, left,right); } } //엇갈리면 right 자리에 pivot이 들어가게되고, //pivot 기준으로 왼쪽은 다 pivot보다 작고 //오른쪽은 다 pivot 보다 크다. basicQuickSort(arr, start, right-1); basicQuickSort(arr, right+1, end); } // 쪼개진 아이들을 정렬하며 다시 이어붙인다. static void merge(int[] arr, int start,int mid, int end){ int leftIdx = start; //left array start point int rightIdx = mid+1; //right array start point int insertIdx = 0; int[] temp = new int[end-start+1]; //전역변수로 잡아주는게 좋다. while(leftIdx<=mid && rightIdx<=end){ if(arr[leftIdx]>arr[rightIdx]){ // 오른쪽이 왼쪽보다 작다면 temp[insertIdx++] = arr[rightIdx++]; }else{//왼쪽이 오른쪽보다 작다면 temp[insertIdx++] = arr[leftIdx++]; } } //왼쪽이나 오른쪽이 자기 배열을 다 채워넣었을경우(인덱스 초과) //둘중 남은 친구를 다 털어 넣어줘야함 while(leftIdx<=mid){ //left가 남았으면 temp[insertIdx++] = arr[leftIdx++]; } while(rightIdx<=end){//right가 남았으면 temp[insertIdx++] = arr[rightIdx++]; } //정렬된 배열을 원본에 삽입 for(int elem : temp){ arr[start++]=elem; } } // 나누기! + 이어붙이기(merge()) static void mergeSort(int[] arr, int start, int end){ if(start<end){ // size가 2이상일 때 int mid = (start+end)/2; mergeSort(arr,start,mid); mergeSort(arr,mid+1,end); //size 1부터 합쳐진다 merge(arr,start,mid,end); } } static int[] heapSort(int[] originArr){ int[] arr = originArr.clone(); // heapify int cnt; int totalCnt=0; // this is max heap for(int i=1;i<arr.length;i++){ // logN int childNode=i; cnt=0; do{//logN int rootNode = (childNode-1)/2; //부모노드, [트리의 특징] if(arr[rootNode]<arr[childNode]){ //자식이 부모보다 크다면 SWAP(arr, rootNode, childNode); //부모가 더 커지게 } childNode=rootNode; cnt++; }while(childNode!=0); totalCnt+=cnt; // System.out.println("heapify cnt : "+ cnt); } // System.out.println("heapify total cnt : "+ totalCnt); // 1개의 원소를 빼고 다시 heapify 하기를 n번 => 사실상 n/2 의 시간복잡도 // 최대힙이니 큰 수부터 빠져나온다 for(int i=arr.length-1; i>=0; i--){ SWAP(arr,0,i); // root 를 맨뒤로 보낸다. int rootNode = 0; // 바뀌어버린 노드를 다시 heapify int childNode= 1; cnt=0; do{//heapify childNode = 2*rootNode + 1; //왼쪽자식 if(childNode>arr.length-1) break; //자식중에 더 큰 값을 올려야한다. (맥스힙으로 만들었으니까) if(arr[childNode]<arr[childNode+1] && childNode<i-1){ //오른쪽 자식과 비교 && 위에서 swap한 애는 힙에서 제외 childNode++; } if(arr[rootNode] < arr[childNode] && childNode<i){ //자식중의 큰애가 부모보다 크다면 && 위에서 swap한 애는 힙에서 제외 SWAP(arr, rootNode, childNode); } rootNode = childNode; //모든 자식에 대해 수행 cnt++; }while(childNode<i); // System.out.println("heapify cnt : "+ cnt); // 한번 heapify 할떄 최대 힙의원소갯수/2 만큼 수행 } return arr; } static int[] countingSort(int[] originArr, int variety){ int[] arr = originArr.clone(); int[] count = new int[variety+1]; //1의 갯수는 count[1]에 저장하기위해서 for(int elem : arr){ count[elem]+=1; } int idx=0; for(int i=0;i<count.length;i++){ if(count[i]!=0){ for(int j=0;j<count[i];j++){ arr[idx++]=i; } } } return arr; } static int[] radixSort(int[] originArr, int digit){ //digit : 최대 자리수 int[] arr = originArr.clone(); Queue<Integer>[] queue = new LinkedList[10]; // 자릿수만큼 공간필요 // 데이터를 n개만 연결하니 공간복잡도는 n for(int i=0; i<10; i++){ queue[i] = new LinkedList<>(); } //sort int mod = 10; for(int d=0; d<digit; d++, mod*=10){ //d for(int i=0; i<originArr.length; i++){ //n queue[(arr[i]%mod)/(mod/10)].add(arr[i]); } int idx = 0; for(int i=0;i<queue.length;i++){ //총횟수 n int len = queue[i].size(); for(int j=0;j<len;j++){ arr[idx++]=queue[i].poll(); } } // System.err.println("#중간점검 "); // printArr(arr); } return arr; } public static void main(String[] args) { int[] arr = {30,21,5,63,7,105,100,9,8}; // int[] arr = {3,2,5}; int[] selectionArr = selectionSort(arr); int[] bubbleArr = bubbleSort(arr); int[] insertionArr = insertionSort(arr); // System.out.println("# arr.length "+ (arr.length-1)); int[] quickArr = arr.clone(); basicQuickSort(quickArr, 0, arr.length-1); int[] mergeArr = arr.clone(); mergeSort(mergeArr, 0, mergeArr.length-1); int[] heapArr = heapSort(arr); int[] countArr = countingSort(arr,105); int[] radixArr = radixSort(arr, 3); System.out.println("#Origin Array, size : "+ arr.length); printArr(arr); System.out.println("=============================="); System.out.println("#Selection Sort Result"); printArr(selectionArr); System.out.println("#Bubble Sort Result"); printArr(bubbleArr); System.out.println("#Insertion Sort Result"); printArr(insertionArr); System.out.println("#Basic-QuickSort Sort Result"); printArr(quickArr); System.out.println("#Merge Sort Result"); printArr(mergeArr); System.out.println("#Heap Sort Result"); printArr(heapArr); System.out.println("#Count Sort Result"); printArr(countArr); System.out.println("#Radix Sort Result"); printArr(radixArr); System.out.println("#Origin Array"); printArr(arr); } }
728x90'Computer Basis > Algorithms' 카테고리의 다른 글
[Algorithms] 백준 DP 문제모음 (bottom-up 유형) (0) 2021.11.01 [Algorithms] 백준 DP 문제모음 (Top-down 유형) (0) 2021.10.30 행렬연산을 위한 자료구조, Tensor, Torch 를 자바로 재구현 해보자! (0) 2021.10.14