Simple in Complex with Simple

1. 개요

 병합 정렬 - 분할 정복의 대표적인 예.

 분할 정복이므로 재귀적 방식으로 코딩.

 병합 정렬은 퀵 정렬의 보안적인 형태. (안정성이 퀵 정렬보다 뛰어남)

 안정성이란 간단하게 큰 부피에서 작은 부피 일로 진행되는지, 작은 부피에서 큰 부피 일로 진행되는지 차이.

 퀵 정렬은 큰 부피에서 작은 부피 일로 진행. (각 재귀 호출 이전에 작업하므로 이전 재귀 오버헤드가 쌓임)

 병합 정렬은 작은 부피에서 큰 부피 일로 진행. (각 재귀 호출이 끝나면 그 오버헤드는 종료)

 병합 정렬은 입력 데이터의 사전 정렬에 영향을 받지 않음. (최종적으로 한 하나의 데이터 단위로 나누기에.)

 병합 정렬은 연결리스트 사용 가능. (연결리스트 기반 데이터 정렬은 병합 정렬 사용)

 보통 O(nlogn)의 시간이 걸리지만 더 정확히는 최악의 경우 O(nlog^2n)이 걸림.

 알고리즘 순서

 (1) 데이터리스트를 반으로 나눈다. 최종적으로 데이터리스트 크기가 1일때까지 나눈다.

 (2) 반으로 나뉜 두 데이터리스트를 비교하여 합병한다.

 (3) 위의 과정이 반복된다.

 (합병 알고리즘은 단순 크기 비교일 뿐이지 어렵지 않다. 정말 중요한건 위의 과정을 재귀로 어떻게 나눌것인지이다.)

2. 코드

2-1) 메인

2-2) 병합 정렬 알고리즘

2-3) 출력

3. 해설

 앞의 3가지 정렬 Bubble, Selection, Insertion 정렬과 비교할 수 없는 속도를 보인다.

 앞의 O(n^2) 속도를 가진 3가지 정렬이 크기 10만 데이터 정렬 속도가 병합 정렬이 크기 1억 정렬 속도와 같다.

 크기가 1000미만이면 어떤 정렬을 사용해도 상관없다. 하지만 그 이상일 경우 O(nlogn) 정렬이 좋다.

 기억해야할 것.

 1) 병합 정렬을 위한 Index범위를 정확하게 넣어야한다. 1이라도 차이날 경우 알고리즘은 실패한다.

 2) 결국은 큰 토대는 MergeSort() 코드다. Merge()는 단순 반복 비교 연산일 뿐이다.

1. 개요

 앞 선 버블 정렬과 선택 정렬과 똑같이 O(n^2) 수행 속도를 가지지만 특정 경우에서 효과적인 정렬이 있다. 바로 삽입 정렬

이다. 삽입 정렬의 기본 아이디어는 최소 최대를 찾아 양 끝으로 보내는게 아니라 루프를 돌며 자기 자신의 자리를 찾아가자

이다. 장점은 이렇다. 코드가 간단하다. 안정성이 좋다.(루프 중간에 멈춰도 아직 검사안한 기존 데이터 순서가 보장) 그리고

데이터가 이미 어느 정도 정렬이 되어있을 경우 효과적이다. 위의 장점들로 인해 삽입 정렬은 분할 정복 기법으로 재귀적인

방법을 사용하는 퀵(Quick) 정렬이나 병합(Merge) 정렬의 높은 재귀적 오버헤드에 대한 base case로 사용된다.

2. 코드

2-1) 메인

2-2) 삽입 정렬 알고리즘

2-3) 출력

3. 해설

 드디어 정렬에서 O(n^2)을 가지는 기초 정렬 알고리즘 대표적인 3개를 정리했다. 먼저 위의 출력을 정리하면 이렇다.

미리 정렬된 데이터일 경우 삽입 정렬의 속도는 무척 빠르다. 하지만 미리 정렬되지 않은 데이터라면 삽입 정렬의 속도

가 다른 정렬보다 빠르다고 말하기 어렵다.

이것을 정리하면 이렇다.

 1) 버블 정렬은 최악의 경우와 평균적 경우 모두 O(n^2/2)의 반복과 O(n^2/2)의 치환을 수행한다.

 2) 선택 정렬은 O(n^2/2)의 비교와 O(n)의 치환이 일어난다.

 3) 삽입 정렬은 평균적인 경우 O(n^2/4)의 비교와 O(n^2/8)의 치환이 일어나며 최악의 경우 이 2배가 된다.

 *선택 정렬이 제일 좋은 상황은 키는 작고(데이터가 작고) 값들이 큰 요소를 가진 목록을 정리할 때이다.

1. 개요

 선택 정렬은 버블 정렬과 마찬가지로 정렬중에서 가장 간단한 정렬이다. 두 정렬의 차이는 버블 정렬은 최대값을 찾아 맨 

뒤로 넣지만 선택 정렬은 최소값을 찾아 맨 앞으로 옮긴다. 언뜻보면 다른게 뭐냐고 말하는 사람들이 있겠지만 코드 내부의

차이로 버블 정렬은 안쪽 루프에 스왑 과정이 있고, 선택 정렬은 바깥 루프에 스왑 과정이 있어서 둘 다 O(n^2)이지만 

버블보다 선택 정렬이 조금 더 빠르다. 이 정렬들은 대규모 데이터가 아닌 속도에 크게 영향을 안받는 작은 데이터일 경우

사용된다. 정렬의 기초중의 기초이다.

2. 코드

2-1) 메인

2-2) 선택 정렬 알고리즘

2-3) 출력

3. 해설

 여러번 테스트를 거친 것은 아니지만 앞의 버블 정렬이 약 14초쯤 걸렸던 것에 비해서 선택 정렬은 약 12초가 걸렸다.

아주 미세하게 빠르며 코드 역시 간단하다. 혹시나 1000개 미만의 데이터를 정렬할 필요가 있을 경우 복잡한 퀵이나

머지 정렬보다 선택 정렬을 사용하는 게 낮다. (높이가 낮다, 알을 낳다, 오리 날다, 내가 낫다)

 기억해야할 것

 1) 최소값을 찾아 맨 앞으로 보낸다.

 2) 인덱스를 통해서 비교.

1. 개요

 버블 정렬은 모든 정렬중에서 가장 쉬운 알고리즘이며 가장 비효율적인 알고리즘이다. 매 반복마다(가장 겉의 루프) 최대값이

제일 끝에 위치하기 때문에 이 모습이 마치 물 속의 버블(공기방울)이 수면위로 올라올수록 점점 커지는 모습을 형상화한다

하여 버블 정렬이라는 이름이 붙었다. 버블 정렬은 정말 데이터 수가 작아 속도에 영향을 안미치는 경우 사용하며 혹은 이미

데이터가 정렬되었는지 탐지할 수 있다는 것 뿐이다.

 일반 버블 정렬의 복잡도는 O(n^2) 

 개선된 버블 정렬일 경우 정렬 상태를 탐지하는 복잡도는 O(n) (정렬 속도가 아님)

2. 코드

2-1) 메인

2-2) 데이터 생성 ( O(n)으로 중복되지 않는 랜덤 숫자 배열 생성 )

2-3) 버블 정렬 알고리즘

2-4) 개선된 버블 정렬 알고리즘

2-5) 출력

3. 해설

 면접 때 코딩 문제로 한번 나왔다. 하지만 그 당시 나에겐 버블 정렬은 딱히 알고리즘이 아니었기 때문에 그런 정렬은 

모른다고 저는 퀵 정렬만 씁니다. 라고 말했다가 퀵 정렬을 코딩했다. 지금 생각하면 패기가 넘쳤던 면접이다. 번외로

대학 때 춤동아리에서 춤췄다고 말했다가 무반주로 춤도 췄다. 중요한 건 이 면접에 내 인생의 첫 면접이었다. 결과는 합격!

 기억해야 할 것.   

 1) 2개의 루프, 외곽 루프의 시작 인덱스는 맨 마지막에서 감소하며 안쪽 루프는 0부터 시작하여 증가한다.

 2) 스왑 과정이 안쪽 루프에 존재 

    (버블 정렬과 비교되는 선택 정렬의 경우 외곽 루프에 스왑 존재. 그래서 O() 같지만 선택 정렬이 조금 더 빠르다.)