[Algorithm] 정렬 (1)

geonhee1492·2022년 8월 5일

알고리즘 정렬

알고리즘

목록 보기

6/6

작은거부터 : 오름차순
내부 정렬 : 하나의 배열 안에서 정렬
외부 정렬 : 데이터가 많아서 하나의 배열로 안되는 경우

선택,버블 생략

단순 삽입 정렬

주목한 원소보다 앞에다가 삽입한다. 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다르다.

1.주목한 원소에서 앞에꺼가 자신보다 큰 수인지 비교한다.
2.만약에 자기가 더 크면 또 앞에 꺼랑 비교한다.
3.막히면 멈추고 그 자리에 삽입한다.

6 4 1 7 3 9 8
4 6 1 7 3 9 8 -> 두 번째 원소부터 시작
1 4 6 7 3 9 8 -> 1이 제일 작으므로 막힘없이 앞으로 갔다.
1 4 6 7 3 9 8 -> 7이 제일 크므로 가만히 있는다.
1 3 4 6 7 9 8 -> 3이 쭉 가다가 1에서 막혀서 삽입되었다.
1 3 4 6 7 8 9 -> 끝~~

코드로 구현해보았다.

이 외에 파이썬은 배열 쪼개는걸로도 할 수 있을 것 같다.

셸 정렬

원소를 그룹으로 나눠 단순 삽입 정렬한 후 합친다.
8 1 4 2 7 6 3 5
4칸씩 떨어진 원소 8 7,1 6,4 3,2 5로 나누고 단순 삽입 정렬
7 1 3 2 8 6 4 5
2칸씩 떨어진 원소 7 3 8 4,1 2 6 5로 나누고 단순 삽입 정렬
3 1 4 2 7 5 8 6
1칸씩 떨어진 원소,즉 배열 전체 정렬하면 끝

초깃값은 n // 2로 구현
원소가 8개면 4 -> 2 -> 1
원소가 7개면 3 -> 1

코드로 구현해보았다.

O(nlog(n)) 정렬들

퀵 정렬

일반적인 경우에 가장 많이 사용함

시간복잡도: 조금씩 나누어 작은 문제 반복하므로 n x log(n), 최악의 경우 n^2
피벗을 기준(이상,이하)으로 그룹을 나누기를 반복하여 모든 그룹이 1명씩 남으면 정렬이 완료됨
5 7 1 4 6 2 3 9 6
pl(왼쪽),pr(오른쪽), 피벗은 6
a[pl] >= x가 성립할 때까지 pl 오른쪽으로 이동
a[pr] <= x가 성립할 때까지 pr 왼쪽으로 이동
=이 붙는 이유는 만약 피벗이랑 값이 같으면 피벗도 옮겨줘야하기 때문이다.
둘다 멈추면 값 교환,이 과정을 pl > pr까지 반복

피벗과 일치하는 그룹이 생기려면 pl > pr + 1일때 생긴다.

병합 정렬

얘도 퀵 정렬처럼 분할 정복 방식이고 일반적인 경우에 사용한다.
퀵 정렬은 최악의 경우 수행 시간이 O(n^2)일 수 있지만 병합 정렬은 수행 시간 O(NlogN)을 보장한다.

병합 정렬(merge sort) : 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

정렬을 마친 배열의 병합

정렬을 마친 두 배열을 병합
2 4 6 8 11 13
1 2 3 4 9 16 21

인덱스 pa,pb,pc 지정

병합 정렬 만들기

이제 응용한다.
원소가 12개인 배열이 있다.
5 6 4 8 3 7 9 0 1 5 2 3
이 배열을 6개씩 2개의 배열로 나누어 정렬 후 병합한다.
그 과정에서 원소가 6개인 배열을 또 3개씩 2개의 배열로 나누어 정렬한다.

즉 병합 정렬의 알고리즘을 다음과 같이 정리할 수 있다.
배열의 원소 수가 2개 이상일 때
1.배열의 앞부분을 병합 정렬로 정렬합니다.
2.배열의 뒷부분을 병합 정렬로 정렬합니다.
3.배열의 앞부분과 뒷부분을 병합합니다.

재귀를 이용해야 할 것 같다.

p,j,k는 그냥 위에 a,b,c 커서랑 대응된다고 생각하자
마찬가지로 반복문 3개도 위에서의 역할과 대응된다.

단순히 buff에 배열의 앞부분을 저장(위 코드의 a역할)한 것이고,뒷부분은 그대로 a에 놔둔 채로 j만 커서로서 활용하였다.

나머지는 주석을 참고하자.

너무 복잡한 것 같아 다른 방식을 찾아봤다

파이썬의 유연한 장점을 이용하여 다시 만들었다. 이거를 사용하도록 하자.

배열 병합의 시간 복잡도는 O(n)이지만 데이터 원소 수가 n일 때 병합 정렬의 단계는 반씩이니까 O(log n)이다. 따라서 병합 정렬의 전체 시간 복잡도는 O(n * log n)이다.

힙 정렬

힙 정렬(heap sort) : 선택 정렬을 응용한 알고리즘. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는
*완전 이진 트리. 이때 부모의 값이 자식의 값보다 항상 작아도(반대) 힙이라고 한다. 즉 , 이러한 두 값의 대 관계가 일정하면 된다. 하지만 형제 사이의 대소는 일정하지 않다.

*완전 이진 트리
완전 : 부모는 왼쪽 자식부터 추가하여 모양을 유지하라
이진 : 부모가 가질 수 있는 자식의 최대 개수는 2개

10
9 5
8 3 2 4
6 7 1
이런 식의 완전 이진 트리가 있으면
배열에는 10 9 5 8 3 2 4 6 7 1 식으로 저장한다.

인덱스로 치면 0 1 3 7 15 ...

그러면 원소 a[i]에서
부모 -> a[(i - 1) // 2]
자식 -> a[i*2 + 1], a[i*2 + 2]

ex) a[3]이면 a[1] , a[7], a[8]

힙 정렬 과정

1.루트를 꺼낸다.
2.마지막 원소를 루트로 이동한다.
3.루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래로 내려가는 작업을 반복한다.

종료 조건
1.자식의 값이 작을 때
2.*리프(leaf)의 위치에 도달했을 때

*리프(leaf) : 자식이 없는 노드,단일 노드라고도 한다.

꺼낸 값들을 나열하면 정렬이 끝난 배열이 완성된다.
재귀..?

10
9 5
8 3 2 4
6 7 1

세부 과정
10 9 5 8 3 2 4 6 7 1
a. 10을 꺼내고(삭제) 힙의 마지막 원소인 1을 루트 자리에 넣는다.
1 9 5 8 3 2 4 6 7
b. 그럼 자식이 9 5인데 1 9 5 를 비교하여 가장 큰 값인 9와 1의 자리를 바꾼다. "부모의 값 >= 자식의 값"
9 1 5 8 3 2 4 6 7
c. 이제 1의 두 자식은 8 3. 똑같이 한다.
9 8 5 1 3 2 4 6 7
d.1의 두 자식은 6 7. 똑같이 한다. 가장 아래이므로 종료한다.
9
8 5
7 3 2 4
6 1

배열을 힙으로 만들기 (1단계)

정렬되지 않은 서브르티를 힙으로 만드는 과정이다

트리가 있으면 아래 서브트리들은 힙 상태일 수도 있다.
그래서 아래 서브트리부터 상향식(bottom-up)으로 진행하면 된다.
먼저 가장 아랫부분의 오른쪽 서브트리의 힙을 만들고 같은 단계에 있는 왼쪽 서브트리로 진행

예를 들어보자

1
3 5
7 9 2 4
6 8 10

a. 마지막 서브트리 (9,10)에 주목한다. 원소 9와 10을 교체한다.
b. 정렬한 서브트리의 왼쪽에 있는 서브트리인 (7,6,8)에 주목합니다. 원소 7과 8을 교체하여 힙으로 만든다.
c. 아랫부분 끝남.한 단계 위(오른쪽)로 간다. 이미 힙이다.
d. 바로 왼쪽에 있는 3을 루트로 하는 서브트리에 주목, 원소 3과 9를 교체한다.
e. 같은 단계의 힙이 모두 끝나고 한 단계로 위로 올라가면 트리 전체에 주목.

2단계는 e를 반복하는 것이다. (즉, 이미 서브트리들은 전부 힙 상태,책 그림 참고하면 좋음)

힙 만들어진 후 정렬 과정 (2단계)

10 9 5 8 3 2 4 6 7 1
같은 층의 자식 노드끼리는 아직 대소가 뒤죽박죽이다.

a. 힙의 루트 a[0]에 위치한 10을 맨 끝 원소인 a[9]와 교환
b. a[0]~a[8]을 힙으로 만든다. 그러면 9가 루트에 위치한다. 이 9를 a[8]과 교환한다.
c. 그 결과 a[8]~a[9]가 정렬을 마친다. 이 과정을 반복한다.

코드 흐름
준비물: 힙
1. i값을 n - 1로 초기화(n은 배열의 길이,i는 배열의 마지막 인덱스)
2. a[0]과 a[i]을 교환
3. a[0], a[1], ~~~ ,a[i - 1]을 힙으로 만듭니다.
4. i값을 1씩 감소시켜 0이 되면 종료. 그렇지 않으면 2로 돌아감.

힙 정렬 구현

두줄 요약
1. 아래부터 부분(서브트리) -> 전체로 쓱쓱 힙을 만든다.
2. 완성된 힙을 이용하여 루트(최댓값)를 뒤로 보내 차곡차곡 쌓는다.

계수(=도수,분포수 세기) 정렬

계수 정렬(counting sort) : 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘.

특징
1.특정한 조건이 부합할 때만 사용할 수 있지만 "매우 빠르게" 동작하는 정렬 알고리즘이다.
2.원소를 비교할 필요가 없다.

계수 정렬은 데이터의 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
최악의 경우에도 수행 시간 O(n + K)를 보장

1단계 : 도수 분포표 만들기

학생들을 점수대로 오름차순 정렬할 것이다.

ex) 배열 a에 있는 학생들의 점수를 바탕으로 '각 점수에 해당하는 학생이 몇 명인가'를 나타내는 도수 분포표 만들기

배열 a -> 5 7 0 2 4 10 3 1 3
배열(도수 분포표)f -> 1 1 1 2 1 1 0 1 0 0 1 (0~10점)

2단계 : 누적 도수 분포표 만들기

"0점부터 n점까지 학생이 몇명 있는지"

ex) f -> 1 1 1 2 1 1 0 1 0 0 1
1 2 1 2 1 ...
1 2 3 2 1 ...
1 2 3 5 1 ... 이런식으로 쌓아 나간다.
그럼 마지막 원소는 9

3단계 : 작업용 배열 만들기

앞의 단계에서 각 점수를 받은 학생이 몇 번쨰에 위치하는지 알 수 있으므로 이 시점에서 정렬은 거의 마쳤다고 볼 수 있다.

여기서 배열 a는 그냥 학생들의 점수이다.
f의 배열 크기는 점수표이다.
ex)
f의 인덱스가 0~10이다. -> 0~10점
f[8]=8 -> 0~8점까지 8명이 있다.

이제 배열 a의 각 원솟값과 누적 도수 분포표 f를 대조하여 정렬을 마무리해야 한다. 작업용 배열 b를 생성한다.
배열 a를 맨 끝에서 맨 앞으로 스캔하면서 배열 f와 대조한다.

a -> 5 7 0 2 4 10 3 1 (3)
0 1 2 3 4 5 6 7 8 (인덱스)
f -> 1 2 3 (5) 6 7 7 8 8 8 9
b -> [, , , ,3]

a의 맨 끝 원소인 a[8]의 값은 3.
f[3]의 값이 5 -> 0~3점 사이에 5명이 있다는 뜻
-> 3점을 받은 이 학생은 5번째 학생이다.
(그전에 f[a[i]] -= 1 을 수행한다.)
그러므로 b[4]에 3을 저장한다. (01234 -> 5번쨰 학생은 3점)

다시 a[7]의 값은 1.
f[1]의 값 2는 0~1점 사이에 2명이 있다는 뜻
(그전에 f[a[i]] -= 1 을 수행한다.)
그러므로 b[1]에 1을 저장한다.

여기서 의문
1.작업용 배열은 어따 쓰는가
2.f의 값에 왜 1을 빼주는가

다시 a[6]의 값은 3.
f[3]의 값이 4,또 f[a[3]] -= 1을 수행한다.
아까 미리 값을 감소시켰기 때문에 중복되는 값인 3을 배열 b[3]에 저장할 수 있다!!
이렇게 a[0]까지 수행하면 b에 정렬이 완료된다.

그러므로 작업용 배열 b[4]에 3을 저장한다.