1.버블 정렬
앞에서 부터 하나씩 비교해 가장 큰값을 k회차에 n-k번 비교하는 정렬
->swap이 너무 잦음
시간복잡도:
공간복잡도 :
stable sort이다.
2.선택 정렬
배열 중 최소값을 선택해 앞자리부터 비교해주는 정렬
->버블 정렬에 비해 swap이 적게일어나 속도 약간더 빠름
unsatable sort이다.
시간복잡도:
공간복잡도: $O(n)
3.삽입정렬
두번째 값부터 잡고 앞의 값들과 비교해 작거나 같은값 나올때 해당자리에 삽입하는 정렬
정렬이 되어있다면 O(n)으로 빠른 정렬방법
stable sort이다.
최악 시간복잡도:
공간복잡도:
4.퀵정렬
대표적인 분할 정복 알고리즘
피벗을 선택해서 피벗 기준으로 큰숫자 작은숫자 교환하면서 정렬하는 방식
unstable sort이다.
-> 피벗선택을 가운데 값으로 해 이미 정렬되어 있는 배열도 유사
으로 처리가능
최악의 경우 을 가진다.
임의접근이므로 linkedlist에서는 비효율적이다.(인덱스로 접근하므로)
5.병합정렬
미리 쪼갠후 merge하면서 정렬하는 방식
Linked List의 정렬에 효율적이다(순차접근이므로)
stablesort이다.
평균 시간복잡도:
공간복잡도: O(N)
/**
* 병합정렬
* 분할정복을 이용해 각 구간을 나누고 재귀로 돌아오는 과정에서 정렬을 하며 돌아온다.
* 정렬할 배열과 재귀에서 돌아올때 구간을 정렬한 값을 저장하는 배열 두개를 만든다.
* 시간복잡도 : O(nlogn) 항상 nlogn을 가진다.
* stablesort
* @param arr
*/
public static void mergeSort(int[] arr,int left, int right) {
int[] tmp = new int[arr.length];
if(left<right) {//범위안에 1개의 값이 있을때까지 분할 해줌
//분할
int mid = (left+right)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
//병합
int sp = left;//구간1 pointer
int mp= mid+1;//구간2 pointer
//반반나눠서 포인터를 하나씩 올려줌
int pointer = left;//전체구간 pointer
while(sp<=mid||mp<=right) {// 두 포인터 모두 tmp배열에 저장 할때 까지
if(sp>mid||(mp<=right&&arr[sp]>arr[mp])){//sp,mp가 arr범위 넘어가는 것을 방지하기 위하여 sp를 mid와 직접 비교하는 로직을 추가해줌
//arr[sp]==arr[mp]일때 sp값을 먼저 추가 해줌 -> stablesort
tmp[pointer++]=arr[mp++];
}else {
tmp[pointer++]=arr[sp++];
}
}
//left 에서 right까지 정렬완료했으니 구간 정렬된 값을 arr에 다시 넣어줌
for(int idx=left;idx<=right;idx++) {
arr[idx]=tmp[idx];
}
}
}6.힙정렬
가장 크거나 가장 작은 값, 최대 k만큼 떨어진 요소 정렬할때 좋음
->삽입 정렬보다 개선된 결과 보여줌
평균 시간복잡도:
공간복잡도: O(N)
7. 기수정렬
자리수 별로 정렬을 수행, 가장 작은 자리수 부터 정렬하여 가장 큰 자리수 까지 정렬을 반복
자리수마다 큐를 만들어 앞에서 부터 자리수 값 검증을해줌
시간복잡도 :
공간복잡도 :
d가 작을때는 O(n)에 가까운 성능이며 대부분의 경우 O(nlogn)보다 빠르게 동작
/**
* 기수 정렬
* 자리수 별로 정렬을 수행, 가장 작은 자리수 부터 정렬하여 가장 큰 자리수 까지 정렬을 반복
* 자리수마다 큐를 만들어 앞에서 부터 자리수 값 검증을해줌
*
* 시간복잡도 : O(d∗(n+k)) d: 최대 자릿수 k : 몇진수인지(보통은 10)
* 공간복잡도 : O(n+d)
*
* d가 작을때는 O(n)에 가까운 성능이며 대부분의 경우 O(nlogn)보다 빠르게 동작
* @param arr
*/
public static void radixSort(int[] arr) {
Queue<Integer>[] radix= new ArrayDeque[10];
//que 초기화
for(int idx =0; idx<10;idx++) {
radix[idx] = new ArrayDeque<Integer>();
}
//최대값 찾기
int max= 0;
for(int num:arr) {
max=Math.max(num, max);
}
int digit = String.valueOf(max).length();//최대 자릿수 만큼 반복
for(int power = 1;power<=digit;power++) {
//큐에넣기
for(int num: arr) {
int idx = num%(int)Math.pow(10, power);
idx = idx/(int)Math.pow(10, power-1);
//idx = power 자릿수
radix[idx].add(num);
}
int pointer = 0;
//큐에서 뺴기
for(int idx=0;idx<10;idx++) {
while(!radix[idx].isEmpty()) {
arr[pointer++]=radix[idx].poll();
}
}
}
}8. 계수정렬
최대값k를 구해 k+1크기의 count 배열을 생성하고 배열에 각 정수의 빈도수를 저장, 누적합으로 계산하여 index를 설정해준다. 이때 뒤에서 부터 배열에 값을 넣어줄건데, 각 count값이 해당 숫자의 index가 된다.(배열은 0 부터니 index+1이 되는셈)
같은 숫자가 여러개 일 수 있으므로 count--를 해준다.
시간복잡도 :
공간복잡도 :
/**
* 계수정렬
* 정수로 구성된 배열만 가능한 정렬방식
* 최대값k를 구해 k+1크기의 count 배열을 생성하고 배열에 각 정수의 빈도수를 저장
* 누적합으로 계산하여 index를 설정해준다.
* 이때 뒤에서 부터 배열에 값을 넣어줄건데 각 숫자의 count값이 해당 숫자의 index가 된다.
* 값을 넣어주면서 위치를 찾아주고 하나씩 count-- 해줌 (같다면 기존 위치 보존하기위해 stable sort)
*
* 시간복잡도 : O(n+k)
* 공간복잡도 : O(n+k)
* @param arr
*/
public static void countingSort(int[] arr) {
int[] tmp = new int[arr.length];
//최대값 찾기
int max= 0;
for(int num:arr) {
max=Math.max(num, max);
}
int[] count = new int[max+1];
//count 배열 만들기
for(int num:arr) {
count[num]++;
}
//count배열 부분합으로 해당 숫자(idx)저장 위치 기록
for(int idx = 1 ;idx<count.length;idx++) {
count[idx]+=count[idx-1];
}
//배열 뒤에서 부터 해당 arr위치에 넣고 count배열을 -1해줌
for(int idx = arr.length-1;idx>=0;idx--) {
tmp[count[arr[idx]]-1]=arr[idx];//1번부터 count에 순서가 매겨져 있으므로 -1로 0번부터 맞춰줌
count[arr[idx]]--;
}
//tmp기존 배열에 옮겨줌
for(int idx=0;idx<arr.length;idx++) {
arr[idx]=tmp[idx];
}
}*stable sort란
정렬 후에도 값은 값끼리의 위치가 유지되는 정렬(클래스의 특정 변수로 정렬할때 중요)
