Developer Cafe

기준 인덱스 다음 원소값을 임시 변수에 저장해 그 값을 왼쪽 원소들과 차례로 비교해 임시 변수의 값이 왼쪽 원소값보다 작다면 앞으로 시프트시키며 정렬한다. 패스스루1 인덱스 1의 값 2는 임시변수에 저장 4 2 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 2 4 7 1 3 패스스루2 인덱스 2의 값 7은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 (임시변수값이 더 크다 고로 그대로 저장) 2 4 7 1 3 패스스루3 인덱스 3의 값 1은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 4 7 3 패스스루4 인덱스 4의 값 3은 임시변수에 저장 1 2 4 7 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 3 4 7 삽입정..

인덱스 0부터 패스스루하는데 각 시점의 최솟값을 구해 그 최소값과 같은 원소값고 시작 인덱스 원소값만 바꾼다. 최솟값(2) 최솟값(2) 최솟값(1) 최솟값(1) 2 6 1 4 1 6 2 4 이후 인덱스 0은 값이 정해졌으니 인덱스 1부터 다시 반복한다. 선택 정렬일때는 (N-1) + (N-2)... + 1 = 번의 비교가 나타난다. 비교단계는 버블정렬과 같다. 하지만, 교환은 패스스루 한번당 한번만 나타난다. 즉, N - 1 의 교환단계가 발생한다. N개의 원소 버블 정렬에서 최대 단계 수 선택 정렬에서 최대 단계 수 5 20 14(10 + 4) 10 90 54(45 + 9) 20 380 199(180 + 19) 40 1560 819(780 + 39) 80 6320 3239(3160 + 79) 선택정렬은..

정렬 알고리즘 중 기본인 버블 정렬의 사용법 1. 배열 내에서 연속된 두 항목을 가르킨다. 2 1 3 5 2. 두 항목의 순서가 바뀌었으면(왼쪽값이 오른쪽값보다 크면) 항목을 바꾼다 1 2 3 5 3. 포인터를 한칸 이동하여 반복한다. 1 2 3 5 1 ~3 을 반복하는 것을 패스스루 라고 한다. 패스스루가 끝나면 마지막 원소 즉, 5를 빼고 다시 패스스루를 반복한다. (총 행의 수 - 1 ) 의 패스스루를 반복한다. 위의 예시에선 3번의 패스스루가 일어난다. 위에 예시에선 결국 (N-1) + (N-2)...+ 1번의 비교를 수행한다. 위의 예시에선 3+2+1=6번의 비교가 일어난다. 여기에 더해 만약 모든 수가 역순일경우엔 총 6번의 교환이 더 일어나게 된다. 총 12단계의 작업이 일어난다. 원소 N개..

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 원소수에 따라 단계가 비례하며 증가한다면 O(N) 빅 오 엔 으로 표기한다. 이를 선형 시간 이라고도 부른다. 원소수가 어떻든 단계가 1이면 O(1)빅 오 일(상수 시간 이라고도 부른다), 단계가 4이면 O(4) 으로 표기한다. 이진 검색에선 O(log N)오 로그 앤으로 표기한다. 즉, 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다. ex) O(log 4)란 사실 O(log 2^4) 라는 뜻이다. 결국 최종적으로 2로 2단계란 뜻이다. 가장 효율적인 순서론 O(1) > O(log N) > O(N) 이다. 원소개수(N) O(N) O(log N) 8 8 3 16 16 4 32 32 5..