MW LAB

1234567891011121314151617181920212223public class CountingSort { public static void main(String args[]){ int arr[] = Common.makeArr(10, 10); Common.showArr(arr); Common.showArr(sort(arr,11)); // k=11 => 1~10 까지의 정수 } public static int[] sort(int[] arr,int K){ int N = arr.length; int[] C = new int[K]; // 원소의 빈도수를 저장할 배열 int[] B = new int[N]; // 결과를 저장할 배열 for(int i = 0 ; i * 공간 복잡도 => * K 와 N 의 크..

# 키의 비교에 기반한 한고리즘들* 키에 대한 사전 정보를 가정하지 않고, 키의 비교에 의해서만 정렬하는 알고리즘(ex. 선택,삽입,쉘 정렬...) * # 선형 정렬 알고리즘 * 키에 대한 추가적인 제약 조건(정보)을 가정 ex) 키 값의 범위, 키의 기수(자리 수) 등.. -> 계수정렬 (Counting Sort) / 버킷정렬 (Bucket Sort) / 기수 정렬 (Radix Sort)

12345678910111213141516171819 public static void sort(int[] arr){ int N = arr.length; int h = 1; // h 개 만큼 점프하면서 비교 while(h=1){ for(int i=h; i=h && arr[j]

12345678910 public static void sort(int[] arr){ for(int i = 1 ; i arr j =i ; arr[j] 와 arr[j-1] 를 비교 for(int j = i ; j > 0 && arr[j]>arr[j-1]; j--){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } 1) 2번 째 인덱스[ j ] 원소 부터 뒤에서 앞으로 가며 비교대상 인덱스[ j-1 ] 의 원소 와 비교2) 현재 인덱스 [ j ] 원소가 비교대상[ j-1 ] 원소 보다 작으면 스왑2-1) 현재 인덱스 [ j ] 원소가 비교대상[ j-1 ] 원소 보다 크면 반복문의 탈출 BestCase 의 시간복잡도는 정렬이 되어 있을 때 바로앞의 ..

123456789101112131415 public static void sort(int[] arr){ for(int i = 0 ; i