[알고리즘][정렬] 버블정렬, 선택정렬, 삽입정렬 (정렬계의 노답삼형제)

제목에는 정렬계의 노답 삼형제라고 적었지만, 다 쓸모가 있기에 존재하겠죠... (라고 말했지만 노답 삼형제 맞는거 같은데, 쓰기 쉽단거 빼면...)

1. 버블 정렬

정렬되는게 거품이 보글보글 올라오는 것과 같아서 버블 정렬이라고 합니다. 정렬해라 했을 때 가장 직관적으로 생각하기 쉬운 알고리즘이죠. 쉬운만큼 비효율적이기도 하고요.

 동작방식은 집합 내의 이웃 요소들끼리 비교하여 교환을 통해 정렬됩니다. 쉽게 말해 키순으로 정렬했을 때 내 앞에 있는 애가 나보다 키가 작으면 자리를 바꿔가며 키가 가장 큰 애를 맨 앞까지 오게 하는 거죠.

동작 예시 :

 백마디 말보다 예를 들어 보죠.

 자 밑에 3,2,4,1 의 정렬되지 않은 숫자가 있습니다.

버블정렬을 통해 오름차순으로 정렬해보죠. (뒤에 나올 정렬들도 동일한 수로 하겠습니다.)

빨간 네모는 비교를 의미합니다.

[1싸이클]

3을 기준으로 이웃한 2와 비교하여 3이 더 크므로 교환.

3을 기준으로 이웃한 4와 비교하여 4가 더 크므로 교환되지 않습니다.

1싸이클의 마지막으로 4와 이웃한 1을 비교하여 맨 마지막 요소에 4가 확정됩니다.

1싸이클을 통해 마지막은 4가 확정됬으므로 다음 싸이클부터는 4는 제외해도 되겠네요.

[2싸이클]

이미 이웃한 3이 더 크므로 교환하지 않습니다.

3이 이웃한 1보다 크므로 교환.

2싸이믈을 마지막을 확정된 3 역시 이후 부터는 제외됩니다.

[3싸이클]

마지막으로 2와 1을 비교하여 정렬을 마무리합니다.

총 3싸이클이 돌고, 비교연산은 6번, 교환은 4번 있었네요. 

최악의 경우 즉, 만약 역으로 정렬되어있었다면, 비교는 언제나 6번이고, 교환은 비교연산 할 때마다 일어나겠죠 (6번)

장점 : 

만들기 쉽다...

단점 :

비교 연산도 교환 연산도 많다.

시간복잡도 : O(n^2)

활용:

언제나 중요한 건 "그래서 이걸 어따 써먹을수 있는데?" 라고 생각합니다. 이게 곧 배우는 이유니까요.

 버블 정렬은 비효율의 대명사죠...

실제로 대학교에서 버블정렬을 접할 때, 이걸 배우는 이유는 비효율을 알아야 효율을 알 수 있기때문에 배우는거라고도 교수님이 그러셨죠.

2. 선택 정렬

 선택 정렬은 정렬되지 않은 집합 내 요소 중 가장 크거나 작은 것을 선택해 차례로 맨 앞이나 뒤로 보내 정렬하는 알고리즘입니다.

  쉽게 생각해서 포커나 고스톱을 칠 때, 카드를 다 받고나면 뒤죽박죽 섞여있잖아요. 그 때 카드들을 작은 것부터 뽑아서 앞으로 옮기면서 보기 좋게 바꾸죠. (버블 정렬처럼 옆으로 차례차례 옮기진 안잖아요?) 그런 방식을 생각하면 됩니다.

동작 예시:

빨간 네모는 최소값으로 선택된 요소입니다.

[1싸이클]

각 요소들의 최소값을 판별하면 1이 최소값인걸 알 수 있죠.

선택된 최소값인 1을 맨 앞으로 이동시킵니다.

[2싸이클]

[3싸이클]

3싸이클에 비교연산은 총 6번, 교환은 2번 일어났네요.

최악의 경우엔, 비교는 동일하고 (매번 동일하겠죠), 교환은 3번 일어날겁니다.

장점 :

버블에 비해 교환 연산이 적다. (최대 n번)

단점 :

안정성을 보장하지 않는다.

(같은 값이 있을 때 상대적으로 같은 위치에 있을거라 보장하지 못한다. 즉 정렬 후에는 순서가 뒤바껴 있을 수 있다.)

비교연산이 많다. (매번 최소값을 구해야하므로)

위와 같은 이유로 집합이 클수록 속도가 크게 느려진다.

시간복잡도 : O(n^2)

활용:

집합이 작은 정렬  + 안정성이 보장될 필요 없는 경우 

3. 삽입 정렬

 삽입 정렬은 정렬이 필요한 요소를 뽑아 적당한 곳에 삽입하는 정렬입니다. 적당히라는 말이 들어가있네요. 가장 어려운 말이죠.... 좀 더 풀어 설명하죠. 정렬되지 않은 요소를 순서대로 뽑아 이미 정렬되어 있는 집합 내 올바른 위치에 삽입하는 정렬입니다. 그렇기 때문에 우선 맨 앞의 요소를 정렬된 집합으로 취급하여 두 번째 요소부터 비교가 진행되죠. 

 바닥에 흩어진 트럼프 카드를 주우며 정렬하고자 할 때, 이 방법이 쓰이겠네요. 한 장씩 주우면서 이미 정렬되어 내 손에 쥐어진 카드에 올바른 위치에 넣는 식으로 정렬을 하겠죠.

동작 예시:

빨간 네모는 비교대상

빨간 선은 비교입니다.

[1싸이클]

3은 이미 정렬된 집합으로 판단하고, 두 번째 요소인 2와 비교해 정렬된 집합 내에 맨 앞으로 이동됩니다.

[2싸이클]

4를 이미 정렬된 집합의 맨 마지막과 먼저 비교하여 4보다 큰 수가 없으므로 맨 뒤에 정렬됩니다.  

[3싸이클]

1을 이미 정렬된 집합의 맨 앞의 2와 비교했을 때. 1일 작으므로 바로 맨 앞으로 이동시킨다.

이로써 싸이클 종료.

3싸이클에 비교연산은 총 3번, 교환은 2번 일어났네요.

최악의 경우엔? 4,1,2,3가 될거 같네요. 비교 6번에 교환은 3번 일어납니다.

장점 :

교환 연산이 비교적 적다. (최대 n번)

이미 일부 정렬된 상태라면 비교연산이 줄어 속도가 빠르다.

단점 :

정렬상태에 따라 속도가 민감하다.

시간복잡도 : O(n^2)

활용:

이미 일정부분 정렬되어 있는 집합.

정렬된 요소에 새 요소의 추가가 빈번할 때.

*항상 선택정렬하고, 삽입정렬하고 헷갈린다... 선택정렬은 최소값이나 최대값을 선택하여 정렬하고, 삽입정렬은 앞에서부터 순서대로 삽입하면서 정렬한다라고는 생각하지만... 아마 한 달 뒤면 또 헷갈리겠지... (삽입과 선택이라는 단어가 바꾸고자 하면 충분히 바꿀 수가 있는지라....)