"Python 계수정렬 구현"의 두 판 사이의 차이

2018년 8월 27일 (월) 03:12 판

1 개요

Python 카운팅정렬 구현

def counting_sort(a):
	count = {}
	for x in a: count[x]=count.get(x,0)+1
	i = 0
	for x, c in sorted(count.items()):
	    a[i:i+c] = [x]*c
	    i += c
arr = [9,1,22,4,0,-1,1,22,100,10]
counting_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

2 같이 보기

@@ 2번째 줄: / 2번째 줄: @@
 ;Python 카운팅정렬 구현
-{{소스헤더|원본 미보존}}
 <source lang='python'>
-def count_sort(arr):
+def counting_sort(a):
-	size = len(arr)
+	count = {}
-	mx = max(arr)
+	for x in a: count[x]=count.get(x,0)+1
-	output = [0]*size
+	i = 0
-	count = [0]*(mx+1)
+	for x, c in sorted(count.items()):
-	for i in range(size):
+	    a[i:i+c] = [x]*c
-		count[i] += 1
+	    i += c
-	for i in range(mx):
+arr = [9,1,22,4,0,-1,1,22,100,10]
-		count[i] += count[i-1]
+counting_sort(arr)
-	for i in range(size):
-		output[count[arr[i]]-1] = arr[i]
-		count[arr[i]] -= 1
-	for i in range(size):
-		arr[i] = output[i]
-arr = [3,4,2,1,7,5,8,9,0,6,100,10]
-count_sort(arr)
 print( arr )
-# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
+# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]
-</source>
-{{소스헤더|원본 보존}}
-<source lang='python'>
-def count_sort(arr):
-	size = len(arr)
-	mx = max(arr)
-	output = [0]*size
-	result = [0]*size
-	count = [0]*(mx+1)
-	for i in range(size):
-		count[i] += 1
-	for i in range(mx):
-		count[i] += count[i-1]
-	for i in range(size):
-		output[count[arr[i]]-1] = arr[i]
-		count[arr[i]] -= 1
-	for i in range(size):
-		result[i] = output[i]
-	return result
-arr = [3,4,2,1,7,5,8,9,0,6,100,10]
-sorted = count_sort(arr)
-print( arr )
-print( sorted )
-# [3, 4, 2, 1, 7, 5, 8, 9, 0, 6, 100, 10]
-# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
 </source>