파이썬 pair type stable sort 배우기(tuple counting sort)

https://blog.naver.com/jqkt15/222031601969

[알고리즘] Counting Sort for Stable Sort - Pair Type (ppt, 소스코드)

 

1. stable counting sort

 

원소가 (첫번째 원소, 두번째 원소)의 튜플로 이루어졌을때, 이를 stable하게 counting sort하는 방법

 

https://deepdata.tistory.com/367

조건을 만족할때 매우 빠른 정렬 - counting sort

 

counting sort는 먼저 원소가 가질 수 있는 값의 범위가 일정할때 적절하며 O(N)으로 가장 빠르다.

 

pair type의 원소를 stable sort하려면

 

1) 두번째 원소를 기준으로 counting sort하는데 전체 원소의 index를 저장

 

2) 두번째 원소를 기준으로 정렬된 인덱스를 이용하여 첫번째 원소를 기준으로 정렬하며 이때는 원소를 저장

 

다음과 같은 배열이 주어질때, stable sort를 한다고 생각해보자.

 

각 원소는 0~10까지 등장할 수 있다고 생각한다.

 

index	0	1	2	3	4
first	5	9	10	4	7
second	2	0	1	3	5

 

두번째 원소를 기준으로 counting sort를 수행한다.

 

두번째 원소의 counting배열을 만드는데.. 0~10까지 나올 수 있으므로..

 

index	0	1	2	3	4	5	6	7	8	9	10
count	1	1	1	1	0	1	0	0	0	0	0

 

다음 counting배열의 누적합 배열을 구성

 

index	0	1	2	3	4	5	6	7	8	9	10
count	1	1	1	1	0	1	0	0	0	0	0
sum	1	2	3	4	4	5	5	5	5	5	5

 

이 누적합 배열의 의미는?

 

0이 1개, 1이 1개, 2가 1개, 3이 1개, 4는 0개, 5가 1개...

 

각 원소에 해당하는 부분에 1개씩 있다는 의미

 

#stable counting sort(pair type)

#정렬하고자 하는 배열
x = [[5,2],[9,0],[10,1],[4,3],[7,5]]

n = len(x) #배열의 크기
m = 10 #나올 수 있는 원소 크기

#먼저 두번째 원소를 기준으로 정
counting = [0]*(m+1)

for i in range(n):
    
    counting[x[i][1]] += 1

for i in range(1,m+1):
    
    counting[i] += counting[i-1]

print(counting)
[1, 2, 3, 4, 4, 5, 5, 5, 5, 5, 5]

 

이제 배열의 맨 뒤부터 순회하여 counting sort를 수행

 

해당 원소의 index를 저장하도록 한다.

 

다음과 같은 두번째 원소에 대한 배열에서.. 4번 인덱스부터 순회를 하는데

 

index	0	1	2	3	4
second	2	0	1	3	5

 

4번 인덱스의 원소가 5니까.. 누적합 배열의 5번 인덱스에 접근

 

5번 인덱스에는 위의 "누적합 배열의 의미"에서 보인대로 5가 1개 저장되어있다고 생각할 수 있음

 

이걸 하나 쓸 예정

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	1	2	3	4	4	5	5	5	5	5	5

 

5-1번인 4번 인덱스에 4를 저장

 

index	0	1	2	3	4
new					4

 

그리고 하나를 썼으니까 누적합 배열의 값을 1 감소

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	1	2	3	4	4	4	5	5	5	5	5

 

다음 index = 3에 접근

 

index	0	1	2	3	4
second	2	0	1	3	5

 

index = 3의 원소가 3이고 누적합 배열의 3번 인덱스에 접근

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	1	2	3	4	4	4	5	5	5	5	5

 

이 3번 인덱스에는 3이 하나 저장되어 있다는 뜻으로 이해할 수 있고... 이를 4-1번 = 3번 인덱스에 인덱스 3으로 저장

 

index	0	1	2	3	4
new				3	4

 

그리고 누적합 배열의 원소를 1 감소

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	1	2	3	3	4	4	5	5	5	5	5

 

다시 두번째 원소 배열의 2번 인덱스에 접근하면서 위 과정을 반복함

 

index	0	1	2	3	4
second	2	0	1	3	5

 

그러면 1이 나오는데 누적합 배열의 1번 인덱스에 접근하고...

 

1번 인덱스의 원소는 2니까 2-1 = 1번 인덱스에 인덱스 2를 저장

 

index	0	1	2	3	4
new		2		3	4

 

마찬가지로 누적합 배열의 원소 1 감소시키고...

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	1	1	3	3	4	4	5	5	5	5	5

 

다시 두번째 원소 배열 인덱스 1에 접근하면.. 원소는 0인데 누적합 배열 0번 인덱스에 접근하면...

 

원소가 1인데.. 1-1 = 0번 인덱스에 인덱스 1을 저장

 

index	0	1	2	3	4
new	1	2		3	4

 

다시 누적합 배열의 원소 1 감소시키고..

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	1	3	3	4	4	5	5	5	5	5

 

두번째 원소 배열의 0번 인덱스에 접근하면.. 원소가 2인데

 

index	0	1	2	3	4
second	2	0	1	3	5

 

누적합 배열의 2번 인덱스에 접근하면 원소가 3이고.. 3-1 = 2번 인덱스에 인덱스 0을 저장

 

index	0	1	2	3	4
new	1	2	0	3	4

 

 

#stable counting sort(pair type)

#정렬하고자 하는 배열
x = [[5,2],[9,0],[10,1],[4,3],[7,5]]

n = len(x) #배열의 크기
m = 10 #나올 수 있는 원소 크기

#먼저 두번째 원소를 기준으로 정렬
counting = [0]*(m+1)

#counting배열에 두번째 원소 등장 횟수를 세고..
for i in range(n):
    
    counting[x[i][1]] += 1

#누적합 배열을 만들어서..
for i in range(1,m+1):
    
    counting[i] += counting[i-1]

#정렬된 두번째 원소의 인덱스를 저장
second = [0]*(n)

#원래 배열의 뒤에서부터 순회하여, 

#i >> x[i][1](두번째 원소 값에 접근) >> 
# >> counting[x[i][1]](누적합 배열에 접근) >> 
#second[counting[x[i][1]-1] = i(새로운 배열에 누적합배열-1번 인덱스에 순회중인 인덱스 i를 저장)
for i in range(n-1,-1,-1):
    
    second[counting[x[i][1]]-1] = i
    
    counting[x[i][1]] -= 1

print(second)
[1,2,0,3,4]

 

다음은 첫번째 원소를 기준으로 정렬하는 단계

 

첫번째 원소에 대한 counting 배열을 생성

 

index	0	1	2	3	4
first	5	9	10	4	7
second	2	0	1	3	5

 

역시 0~10까지 나올수 있다고 생각한다면..

 

index	0	1	2	3	4	5	6	7	8	9	10
count	0	0	0	0	1	1	0	1	0	1	1

 

stable sort를 위한 누적합 배열을 생성

 

index	0	1	2	3	4	5	6	7	8	9	10
count	0	0	0	0	1	1	0	1	0	1	1
sum	0	0	0	0	1	2	2	3	3	4	5

 

#stable counting sort(pair type)

#정렬하고자 하는 배열
x = [[5,2],[9,0],[10,1],[4,3],[7,5]]

n = len(x) #배열의 크기
m = 10 #나올 수 있는 원소 크기

#먼저 두번째 원소를 기준으로 정렬
counting = [0]*(m+1)

#counting배열에 두번째 원소 등장 횟수를 세고..
for i in range(n):
    
    counting[x[i][1]] += 1

#누적합 배열을 만들어서..
for i in range(1,m+1):
    
    counting[i] += counting[i-1]

#정렬된 두번째 원소의 인덱스를 저장
second = [0]*(n)

#원래 배열의 뒤에서부터 순회하여, 

#i >> x[i][1](두번째 원소 값에 접근) >> 
# >> counting[x[i][1]](누적합 배열에 접근) >> 
#second[counting[x[i][1]-1] = i(새로운 배열에 누적합배열-1번 인덱스에 순회중인 인덱스 i를 저장)
for i in range(n-1,-1,-1):
    
    second[counting[x[i][1]]-1] = i
    
    counting[x[i][1]] -= 1

#다음 첫번째 원소를 기준으로 정렬하는 단계

counting = [0]*(m+1)

#첫번째 원소의 등장 횟수를 counting배열에 저장
for i in range(n):
    
    counting[x[i][0]] += 1

#stable sort를 위한 누적합 배열 구성
for i in range(1,m+1):
    
    counting[i] += counting[i-1]

print(counting)
[0, 0, 0, 0, 1, 2, 2, 3, 3, 4, 5]

 

이제 이전에 두번째 원소를 정렬하면서 얻은 인덱스 배열 second를 이용하여 전체 배열을 정렬하는 단계

 

second 배열의 맨 뒤부터 순회하는데... 먼저 4번 인덱스에 접근하면..

 

index	0	1	2	3	4
new	1	2	0	3	4

 

 

그 원소는 4이고 원래 배열의 4번에 접근

 

index	0	1	2	3	4
first	5	9	10	4	7

 

첫번째 원소 값이 7인데.. 누적합 배열의 7번 인덱스에 접근하면 원소가 3이다.

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	1	2	2	3	3	4	5

 

새로운 정렬 배열에서 3-1 = 2번 인덱스에 정렬 전의 배열 4번 원소 (7,5)을 넣는다

 

index	0	1	2	3	4
first			7
second			5

 

그리고 누적합 배열의 원소 1 감소시킨다

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	1	2	2	2	3	4	5

 

 

다시 second 배열의 3번 인덱스에 접근하면 원소가 3이다.

 

index	0	1	2	3	4
new	1	2	0	3	4

 

원래 배열의 3번 인덱스에 접근하여 첫번째 원소값을 구하면.. 4인데

 

index	0	1	2	3	4
first	5	9	10	4	7

 

누적합 배열의 4번 인덱스에 접근하면 원소가 1인데.. 

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	1	2	2	2	3	4	5

 

새롭게 정렬된 배열의 1-1 = 0번 인덱스에 정렬 전 배열의 3번 인덱스의 원소 (4,3)을 넣는다

 

index	0	1	2	3	4
first	4		7
second	3		5

 

그리고 누적합 배열의 원소 1 감소시키고..

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	2	2	2	3	4	5

 

위 과정을 계속 반복하자..

 

다음 인덱스는 2번인데 값이 0이고

 

index	0	1	2	3	4
new	1	2	0	3	4

 

정렬 전 배열의 0번 인덱스의 첫번째 원소 값이 5이다.

 

index	0	1	2	3	4
first	5	9	10	4	7

 

 

누적합 배열의 5번 원소는... 2이고..

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	2	2	2	3	4	5

 

정렬전 배열의 2-1 = 1번 인덱스에 정렬 전 배열의 0번 원소인 (5,2)를 넣는다..

 

index	0	1	2	3	4
first	4	5	7
second	3	2	5

 

역시 누적합 배열의 원소는 1 감소시키자.

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	1	2	2	3	4	5

 

다음 인덱스는 1이고 second 배열에서 이 값은 2이다.

 

index	0	1	2	3	4
new	1	2	0	3	4

 

정렬 전 배열의 2번 원소 값이 10이다

 

index	0	1	2	3	4
first	5	9	10	4	7

 

누적합 배열의 10번 원소에는 5가 있고.. 

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	1	2	2	3	4	5

 

5-1 = 4번 인덱스에 정렬 전 배열 2번 원소인 (10,1)을 넣는다

 

index	0	1	2	3	4
first	4	5	7		10
second	3	2	5		1

 

그리고 누적합 배열 원소는 1 감소시키자

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	1	2	2	3	4	4

 

 

마지막 인덱스는 0이고 원소가 1이다.

 

index	0	1	2	3	4
new	1	2	0	3	4

 

정렬 전 배열의 1번 인덱스의 첫번째 원소는 9이다.

 

index	0	1	2	3	4
first	5	9	10	4	7

 

누적합 배열의 9번 인덱스는 4가 있고

 

index	0	1	2	3	4	5	6	7	8	9	10
sum	0	0	0	0	0	1	2	2	3	4	4

 

새롭게 정렬된 배열의 4-1 = 3번 인덱스에 정렬 전 배열의 1번 원소 (9,0)을 넣는다

 

index	0	1	2	3	4
first	4	5	7	9	10
second	3	2	5	0	1

 

정렬 전 배열을 보면 예상 결과와 잘 맞는 것 같다.

 

index	0	1	2	3	4
first	5	9	10	4	7
second	2	0	1	3	5

 

#stable counting sort(pair type)

#정렬하고자 하는 배열
x = [[5,2],[9,0],[10,1],[4,3],[7,5]]

n = len(x) #배열의 크기
m = 10 #나올 수 있는 원소 크기

#먼저 두번째 원소를 기준으로 정렬
counting = [0]*(m+1)

#counting배열에 두번째 원소 등장 횟수를 세고..
for i in range(n):
    
    counting[x[i][1]] += 1

#누적합 배열을 만들어서..
for i in range(1,m+1):
    
    counting[i] += counting[i-1]

#정렬된 두번째 원소의 인덱스를 저장
second = [0]*(n)

#원래 배열의 뒤에서부터 순회하여, 

#i >> x[i][1](두번째 원소 값에 접근) >> 
# >> counting[x[i][1]](누적합 배열에 접근) >> 
#second[counting[x[i][1]-1] = i(새로운 배열에 누적합배열-1번 인덱스에 순회중인 인덱스 i를 저장)
for i in range(n-1,-1,-1):
    
    second[counting[x[i][1]]-1] = i
    
    counting[x[i][1]] -= 1

#다음 첫번째 원소를 기준으로 정렬하는 단계

counting = [0]*(m+1)

#첫번째 원소의 등장 횟수를 counting배열에 저장
for i in range(n):
    
    counting[x[i][0]] += 1

#stable sort를 위한 누적합 배열 구성
for i in range(1,m+1):
    
    counting[i] += counting[i-1]

#새롭게 정렬된 결과를 담을 배열
new_x = [0]*(n)

#second배열의 뒤에서부터 순회
for i in range(n-1,-1,-1):
    
    #i >> second[i]:second 배열의 인덱스
    #>> x[second[i]][0]: 정렬전 배열의 첫번째 원소
    #counting[x[second[i]][0]]: 누적합 배열에 접근
    #new_x[counting[x[second[i]][0]]-1]: 새롭게 정렬할 배열의 (누적합 배열의 값-1)번 인덱스에
    #정렬 전 배열의 x[second[i]]값 저장
    new_x[counting[x[second[i]][0]]-1] = x[second[i]]

    #접근했던 누적합 배열의 원소 1 감소
    counting[x[second[i]][0]] -= 1

print(new_x)
[[4, 3], [5, 2], [7, 5], [9, 0], [10, 1]]

 

 

2. 연습문제

 

11650번: 좌표 정렬하기 (acmicpc.net)

11650번: 좌표 정렬하기

 

(x,y)를 정렬하는 문제

 

x,y가 -10만부터 10만까지 가능한데 인덱스로 음수는 불가능하니, 0~20만까지로 지정하고,

 

-10만~-1까지는 0~99999로 대응시키고, 0~10만까지는 10만~20만까지 대응시키면 될 것이다.

 

이 부분만 살짝 바꿔서 구현하면 된다..

 

근데 배열 크기 N = 10만인데 class 크기는 m = 20만이라 O(20만)이라서 

 

퀵정렬 O(NlogN)이랑 큰 차이 없을듯...

 

#stable counting sort(pair type)

def counting_sort(x):

    n = len(x) #배열의 크기
    m = 200000 #나올 수 있는 원소 크기

    #먼저 두번째 원소를 기준으로 정렬
    counting = [0]*(m+1)

    #counting배열에 두번째 원소 등장 횟수를 세고..
    for i in range(n):
        
        counting[x[i][1]+100000] += 1

    #누적합 배열을 만들어서..
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]

    #정렬된 두번째 원소의 인덱스를 저장
    second = [0]*(n)

    #원래 배열의 뒤에서부터 순회하여, 

    #i >> x[i][1](두번째 원소 값에 접근) >> 
    # >> counting[x[i][1]](누적합 배열에 접근) >> 
    #second[counting[x[i][1]-1] = i(새로운 배열에 누적합배열-1번 인덱스에 순회중인 인덱스 i를 저장)
    for i in range(n-1,-1,-1):
        
        second[counting[x[i][1]+100000]-1] = i
        
        counting[x[i][1]+100000] -= 1

    #다음 첫번째 원소를 기준으로 정렬하는 단계

    counting = [0]*(m+1)

    #첫번째 원소의 등장 횟수를 counting배열에 저장
    for i in range(n):
        
        counting[x[i][0]+100000] += 1

    #stable sort를 위한 누적합 배열 구성
    for i in range(1,m+1):
        
        counting[i] += counting[i-1]

    #새롭게 정렬된 결과를 담을 배열
    new_x = [0]*(n)

    #second배열의 뒤에서부터 순회
    for i in range(n-1,-1,-1):
        
        #i >> second[i]:second 배열의 인덱스
        #>> x[second[i]][0]: 정렬전 배열의 첫번째 원소
        #counting[x[second[i]][0]]: 누적합 배열에 접근
        #new_x[counting[x[second[i]][0]]-1]: 새롭게 정렬할 배열의 (누적합 배열의 값-1)번 인덱스에
        #정렬 전 배열의 x[second[i]]값 저장
        new_x[counting[x[second[i]][0]+100000]-1] = x[second[i]]

        #접근했던 누적합 배열의 원소 1 감소
        counting[x[second[i]][0]+100000] -= 1
    
    return new_x

n = int(input())

points = []

for _ in range(n):
    
    x,y = map(int,input().split())

    points.append((x,y))

sorted_points = counting_sort(points)


for x,y in sorted_points:
    
    print(x,y)