비교 정렬
증명
다음과 같은 사진의 결정트리가 있다고 하자.
결정트리는 이진트리로 구성되어 있으며 리프(순열)의 갯수는 n!이다
jayyhkwon의 개발공부로그
이진 트리에서 리프의 갯수는 2^h를 넘을 수 없으므로
n! <= 2^h
양변에 이진로그를 취하면
h>=log(n!)
h=Ω(nlogn)
해당 링크를 참고하면 log(n!) = Ω(nlogn) 임을 알 수 있다.
계수정렬
CountingSort
//pseudocode
CountingSort(A,B,k){
//C[0..k]를 새로운 배열로 한다
for(i=0 to k)
C[i]=0;
//C[i]는 이제 i와 같은 원소의 개수를 나타낸다.
for(j=1 to A.length)
C[A[j]]=C[A[j]] + 1;
//C[i]는 이제 값이 i보다 작거나 같은 원소의 갯수를 나타낸다.
for(i=1 to k)
C[i]=C[i]+C[i-1];
for(j=A.length downto 1){
B[C[A[j]]]=A[j];
C[A[j]]=C[A[j]]-1;
}
}
Java로 계수정렬 구현
테스트 코드
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
class CountingSortTest {
private Integer[] input;
private Integer[] output;
@BeforeEach
public void setUp(){
input = new Integer[]{2,5,3,0,2,3,0,3};
output = new Integer[]{0,0,2,2,3,3,3,5};
}
@Test
public void test(){
Integer[] result = CountingSort.sort(input);
assertArrayEquals(result,output);
}
}
알고리즘
import java.util.Arrays;
import java.util.Collections;
public class CountingSort {
public static Integer[] sort(Integer[] input) {
int max = Collections.max(Arrays.asList(input));
Integer[] result = new Integer[input.length];
Integer[] countArray = new Integer[max+1];
Arrays.fill(countArray,0);
// countArray[i]는 i와 같은 원소의 개수를 나타낸다.
for(int i=0; i<input.length; i++){
countArray[input[i]] = countArray[input[i]] + 1;
}
//countArray[i]는 이제 i보다 작거나 같은 원소의 개수를 나타낸다.
for(int i=1; i<=max; i++){
countArray[i] = countArray[i] + countArray[i-1];
}
for(int i=input.length-1; i>=0; i--){
result[countArray[input[i]]-1] = input[i];
countArray[input[i]] = countArray[input[i]] - 1;
}
return result;
}
}
계수정렬 vs 퀵정렬
퀵정렬의 경우 평균적으로 O(nlogn)의 시간복잡도를 가지나, 일반적인 정렬 상황에서 가장 선호되는 알고리즘이다.
입력이 int인 배열이라면 최악의 시간복잡도 O(n+k)인 계수정렬을 우선 고려해볼 수 있겠다는 생각이 들었다. 하지만 스택오버플로우에서 특정조건이 아닌 이상 퀵 정렬이 선호되는 이유에 대해 찾을 수 있었다.
계수정렬은 countArray를 사용하므로 max값이 크다면 배열의 크기가 커져 배열 생성이 많은 비용이 발생한다.
만약 largest, smallest 원소 차이가 크다면 countArray에 의미없는 작업을 수행 할 수있다.
// smallest = 1, largest = 99999이면 2~99998은 의미없는 루프를 돌게된다.
for(int i=1; i<=max; i++){
countArray[i] = countArray[i] + countArray[i-1];
}
계수정렬은 숫자가 아닌 경우 적용할 수 없다
ref. 계수정렬 vs 퀵정렬
대략적인 네트워크 계층구조
소켓이란
프로토콜 스택은 이 소켓에 저장된 정보를 참조하면서 동작한다.
TCP/IP 통신 과정
요청하기 전에 DNS서버의 IP주소를 알아야 하므로 사진의 ‘gethostbyname’을 호출하여 DNS 서버정보를 먼저 알아낸다. (UDP 프로토콜을 이용한다)
① 준비
② 접속
소켓을 만든 직후에는 아무 것도 기록되어 있지 않으므로 통신 상대가 누구인지 모른다.
서버의 IP주소나 포트번호를 프로토콜 스택에 알리는 동작이 필요하다.
접속 동작의 첫 번째 동작은 통신 상대와 제어 정보[2]를 주고받아 소켓에 필요한 정보를 기록하고 데이터 송∙수신이 가능한 상태로 만드는 것이다. 패킷에 제어정보를 추가하면 그 제어정보가 헤더가 된다.
두 번째 동작은 데이터 송∙수신 동작을 실행할때 데이터를 일시적으로 저장하는 ‘버퍼 메모리’ 영역을 확보하는 것이다.
대화를 주고받는 과정을 간단히 살펴보면
[1] 패킷
네트워크에서 데이터는 수십 바이트에서 수천 바이트 정도의 작은 덩어리로 분할되어 운반된다.
이렇게 분할된 데이터의 덩어리를 ‘패킷’이라고 부른다.
[2] 제어 정보
데이터 송∙수신 동작을 제어하기 위한 정보로, IP 주소나 포트번호가 대표적인 예이다.
클라이언트와 서버가 서로 연락을 절충하기 위해 주고 받는 제어정보(헤더)[사진1]와
소켓에 기록하여 프로토콜 스택의 동작을 제어하기 위한 정보가 있다.
[사진1]
[3] SYN
네트워크
퀵정렬
합병 정렬과 마찬가지로 퀵 정렬또한 분할 정복을 기반으로 정렬하지만 차이점이 있다.
퀵 정렬을 위해서는 2가지 연산이 필요하다
- Partition
- QuckSort
Partition
기준값(pivot)의 인덱스를 반환하는 연산 –> 퀵 정렬의 핵심
pseudocode는 기준값(pivot)을 배열의 마지막 값을 사용한다.
//pseudocode
Partition(A, p, r){
x = A[r]; // pivot
i = p-1;
for j=p to r-1
if(A[j] <= x){
i++;
exchange A[i] with A[j]
}
exchange A[i+1] with A[r]
return i+1;
}
모든 배열 인덱스 k는 다음과 같은 조건을 만족한다.
k=r 이면 A[k] =x 이다
QuickSort
//pseudocode
QuickSort(A,p,r){
if(p<r){
q = partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
퀵 정렬 시간 복잡도
퀵 정렬은 partition() 연산이 핵심이라는 말을 글을 시작하며 말했다.
partion()에 따라 시간복잡도는 다음과 같이 달라진다.
최선의 경우 시간복잡도는 O(nlogn)
Java로 퀵정렬 구현
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
class QuickSortTest {
private int[] input;
private int[] output;
@BeforeEach
public void setUp(){
input = new int[]{13,19,9,5,12,8,7,4,21,2,11};
output = new int[]{2,4,5,7,8,9,11,12,13,19,21};
}
@Test
public void test(){
QuickSort.quickSort(input,0,input.length-1);
assertArrayEquals(input,output);
}
}
public class QuickSort {
public static void quickSort(int[] src, int from, int to){
if(from < to){
int mid = partition(src,from,to);
quickSort(src,from,mid-1);
quickSort(src,mid+1,to);
}
}
private static int partition(int[] src, int from, int to) {
int pivot = src[to];
int i = from -1;
for(int j=from; j<to ;j++){
if(src[j] < pivot){
i++;
swap(src,i,j);
}
}
swap(src,++i,to);
return i;
}
private static void swap(int[] src, int i, int j) {
int tmp = src[i];
src[i] = src[j];
src[j] = tmp;
}
}
합병정렬 vs 퀵정렬
같은 분할정복 기법을 사용하는 합병정렬과 퀵정렬을 비교해보자
최악의 경우를 비교해보자면 합병정렬 = O(nlogn), 퀵정렬 = O(n^2) 으로 퀵정렬이 불리해보인다.
하지만 그럼에도 불구하고 퀵정렬을 많이 사용하는 데는 이유가 있다.
추가배열을 사용하지 않는점
ref 유투브
ref Introduction to algorithms
ref 합병정렬 vs 퀵정렬
ref.wiki