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

 
(사용자 2명의 중간 판 45개는 보이지 않습니다)
1번째 줄: 1번째 줄:
[[분류: 정렬]]
[[분류:계수정렬]]
;계수정렬 구현
;카운팅정렬 구현
 
==C==
==C==
[[분류: C]]
[[분류: C]]
{{참고|C 카운팅정렬 구현}}
{{참고|C 계수정렬 구현}}
<source lang='c'>
<syntaxhighlight lang='c' run>  
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <string.h>
void count_sort(int arr[], int size) {
void counting_sort(int arr[], int size) {
    int i, max=arr[0];
int i, max=arr[0];
    for(i=0; i<size; i++) if( arr[i]>max ) max=arr[i];
for(i=0; i<size; i++) if( arr[i]>max ) max=arr[i];
int output[size], count[max+1];
int output[size], count[max+1];
memset(count, 0, sizeof(count));
memset(count, 0, sizeof(count));
21번째 줄: 24번째 줄:
int main() {
int main() {
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
int size = sizeof(arr)/sizeof(arr[0]);
int size = sizeof(arr)/sizeof(int);
count_sort(arr, size);
counting_sort(arr, size);
for(int i=0; i<size; i++) printf("%d ",arr[i]);
for(int i=0; i<size; i++) printf("%d ",arr[i]);
// 0 1 2 3 4 5 6 7 8 9 10 100
}
</syntaxhighlight>
==C++==
[[분류: C++]]
{{참고|C++ 계수정렬 구현}}
<syntaxhighlight lang='cpp' run>
#include <iostream>
void counting_sort(int a[], int size) {
int i, max=a[0];
for(i=0; i<size; i++) if( a[i]>max ) max=a[i];
int output[size], count[max+1] = {0};
for(i=0; i<size; i++) count[a[i]]++;
for(i=1; i<=max; i++) count[i] += count[i-1];
for(i=0; i<size; i++) {
output[count[a[i]]-1] = a[i];
count[a[i]]--;
}
for(i=0; i<size; i++) a[i] = output[i];
}
int main() {
int arr[] = {9,1,22,4,0,1,22,100,10};
counting_sort(arr, sizeof(arr)/sizeof(int));
for(int x: arr) std::cout << x << " ";
// 0 1 1 4 9 10 22 22 100
}
}
</source>
</syntaxhighlight>
 
==C#==
[[분류: Csharp]]
{{참고|C샵 계수정렬 구현}}
<syntaxhighlight lang='csharp' run>
using System;
using System.Linq;
class Program {
static void countingSort(int []a) {
int i, size=a.Length, max=a.Max();
int[] output = new int[size];
int[] count = new int[max+1];
for(i=0; i<max; i++) count[i] = 0;
for(i=0; i<size; i++) count[a[i]]++;
for(i=1; i<=max; i++) count[i] += count[i-1];
for(i=0; i<size; i++) {
output[count[a[i]]-1] = a[i];
count[a[i]]--;
}
for(i=0; i<size; i++) a[i] = output[i];
}
static void Main() {
int[] arr = {3,4,2,1,7,5,8,9,0,6,100,10};
countingSort(arr);
        Console.Write(string.Join(",",arr));
// 0,1,2,3,4,5,6,7,8,9,10,100
}
}
</syntaxhighlight>


==Java==
==Java==
[[분류: Java]]
[[분류: Java]]
{{참고|Java 카운팅정렬 구현}}
{{참고|Java 계수정렬 구현}}
<source lang='java'>
{{소스헤더|트리맵 사용}}
import java.util.Arrays;
<syntaxhighlight lang='java' run>
import java.util.Map;
import java.util.TreeMap;
public class MyClass {
    static void counting_sort(Integer a[]) {
        Map<Integer,Integer> count = new TreeMap();
        for(int x: a) {
            if( !count.containsKey(x) ) count.put(x,1);
            else count.put(x,count.get(x)+1);
        }
        int k, v, pos=0;
        for (Map.Entry<Integer,Integer> entry: count.entrySet()) {
            k = entry.getKey();
            v = entry.getValue();
            while( v-- > 0 ) a[pos++] = k;
        }
    }
    public static void main(String args[]) {
    Integer arr[] = {9,1,22,4,0,-1,1,22,100,10};
    counting_sort(arr);
    for(int x:arr) System.out.format("%d ",x);
    // -1 0 1 1 4 9 10 22 22 100
    }
}
</syntaxhighlight>
{{소스헤더|배열 사용, 음수 정렬 불가}}
<syntaxhighlight lang='java' run>
public class MyClass {
public class MyClass {
private static void count_sort(int arr[]) {
static void counting_sort(int a[]) {
int i, size=arr.length, max=arr[0];
int i, size=a.length, max=a[0];
for(int e:arr) if(max<e)max=e;
for(int x: a) if(max<x)max=x;
int output[] = new int[size];
int output[] = new int[size];
int count[] = new int[max+1];
int count[] = new int[max+1];
for(i=0; i<size; i++) count[arr[i]]++;
for(i=0; i<size; i++) count[a[i]]++;
for(i=1; i<=max; i++) count[i] += count[i-1];
for(i=1; i<=max; i++) count[i] += count[i-1];
for(i=0; i<size; i++) {
for(i=0; i<size; i++) {
output[count[arr[i]]-1] = arr[i];
output[count[a[i]]-1] = a[i];
count[arr[i]]--;
count[a[i]]--;
}
}
for(i=0; i<size; i++) arr[i] = output[i];
for(i=0; i<size; i++) a[i] = output[i];
}
}
public static void main(String args[]) {
public static void main(String args[]) {
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
count_sort(arr);
counting_sort(arr);
System.out.println( Arrays.toString(arr) );
for(int x:arr) System.out.format("%d ",x);  
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
// 0 1 2 3 4 5 6 7 8 9 10 100  
}
}
}
}
</source>
</syntaxhighlight>
 
==PHP==
[[분류: PHP]]
{{참고|PHP 계수정렬 구현}}
<syntaxhighlight lang='php' run>
function counting_sort(&$a) {
    $count=[];
    foreach($a as $x) {
        if(!array_key_exists($x,$count)) $count[$x]=1;
        else $count[$x]++;
    }
    ksort($count);
    $pos=0;
    foreach($count as $x => $repeat) {
        while( $repeat-- > 0 ) $a[$pos++]=$x;
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
counting_sort( $arr );
echo implode(',', $arr);
# -1,0,1,1,4,9,10,22,22,100
</syntaxhighlight>


==Python==
==Python==
[[분류: Python]]
[[분류: Python]]
{{참고|Python 카운팅정렬 구현}}
{{참고|Python 계수정렬 구현}}
<source lang='python'>
<syntaxhighlight lang='python' run>
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
pos=0
count = [0]*(mx+1)
for x,repeat in sorted(count.items()):
for i in range(size):
    a[pos:pos+repeat] = [x]*repeat
count[i] += 1
    pos += repeat
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 )
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>
</syntaxhighlight>
 
==Ruby==
[[분류: Ruby]]
{{참고|Ruby 계수정렬 구현}}
<syntaxhighlight lang='ruby' run>
def counting_sort(a)
    count={}
    for x in a
        if not count.key?(x) then count[x]=1
        else count[x]+=1 end
    end
    pos = 0
    for x,repeat in count.sort_by {|k,v| k}
        a[pos,repeat] = Array.new(repeat,x)
        pos += repeat
    end
end
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]
</syntaxhighlight>


==같이 보기==
==같이 보기==
* [[계수정렬]]
* [[정렬 구현]]
* [[기수정렬 구현]]
* [[기수정렬 구현]]
* [[정렬 구현]]
 
* [[카운팅정렬]]
==참고==
* https://www.geeksforgeeks.org/counting-sort/

2022년 2월 26일 (토) 14:12 기준 최신판

계수정렬 구현
카운팅정렬 구현

1 C[ | ]

 
#include <stdio.h>
#include <string.h>
void counting_sort(int arr[], int size) {
	int i, max=arr[0];
	for(i=0; i<size; i++) if( arr[i]>max ) max=arr[i];
	int output[size], count[max+1];
	memset(count, 0, sizeof(count));
	for(i=0; i<size; i++) count[arr[i]]++;
	for(i=1; i<=max; i++) count[i] += count[i-1];
	for(i=0; i<size; i++) {
		output[count[arr[i]]-1] = arr[i];
		count[arr[i]]--;
	}
	for(i=0; i<size; i++) arr[i] = output[i];
}
int main() {
	int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
	int size = sizeof(arr)/sizeof(int);
	counting_sort(arr, size);
	for(int i=0; i<size; i++) printf("%d ",arr[i]);
	// 0 1 2 3 4 5 6 7 8 9 10 100 
}

2 C++[ | ]

#include <iostream>
void counting_sort(int a[], int size) {
	int i, max=a[0];
	for(i=0; i<size; i++) if( a[i]>max ) max=a[i];
	int output[size], count[max+1] = {0};
	for(i=0; i<size; i++) count[a[i]]++;
	for(i=1; i<=max; i++) count[i] += count[i-1];
	for(i=0; i<size; i++) {
		output[count[a[i]]-1] = a[i];
		count[a[i]]--;
	}
	for(i=0; i<size; i++) a[i] = output[i];
}
int main() {
	int arr[] = {9,1,22,4,0,1,22,100,10};
	counting_sort(arr, sizeof(arr)/sizeof(int));
	for(int x: arr) std::cout << x << " ";
	// 0 1 1 4 9 10 22 22 100 
}

3 C#[ | ]

using System;
using System.Linq;
class Program {
	static void countingSort(int []a) {
		int i, size=a.Length, max=a.Max();
		int[] output = new int[size];
		int[] count = new int[max+1];
		for(i=0; i<max; i++) count[i] = 0;
		for(i=0; i<size; i++) count[a[i]]++;
		for(i=1; i<=max; i++) count[i] += count[i-1];
		for(i=0; i<size; i++) {
			output[count[a[i]]-1] = a[i];
			count[a[i]]--;
		}
		for(i=0; i<size; i++) a[i] = output[i];
	}
	static void Main() {
		int[] arr = {3,4,2,1,7,5,8,9,0,6,100,10};
		countingSort(arr);
        Console.Write(string.Join(",",arr));
		// 0,1,2,3,4,5,6,7,8,9,10,100
	}
}

4 Java[ | ]

트리맵 사용
import java.util.Map;
import java.util.TreeMap;
public class MyClass {
    static void counting_sort(Integer a[]) {
        Map<Integer,Integer> count = new TreeMap();
        for(int x: a) {
            if( !count.containsKey(x) ) count.put(x,1);
            else count.put(x,count.get(x)+1);
        }
        int k, v, pos=0;
        for (Map.Entry<Integer,Integer> entry: count.entrySet()) {
            k = entry.getKey();
            v = entry.getValue();
            while( v-- > 0 ) a[pos++] = k;
        }
    }
    public static void main(String args[]) {
    	Integer arr[] = {9,1,22,4,0,-1,1,22,100,10};
    	counting_sort(arr);
    	for(int x:arr) System.out.format("%d ",x); 
    	// -1 0 1 1 4 9 10 22 22 100 
    }
}
배열 사용, 음수 정렬 불가
public class MyClass {
	static void counting_sort(int a[]) {
		int i, size=a.length, max=a[0];
		for(int x: a) if(max<x)max=x;
		int output[] = new int[size];
		int count[] = new int[max+1];
		for(i=0; i<size; i++) count[a[i]]++;
		for(i=1; i<=max; i++) count[i] += count[i-1];
		for(i=0; i<size; i++) {
			output[count[a[i]]-1] = a[i];
			count[a[i]]--;
		}
		for(i=0; i<size; i++) a[i] = output[i];
	}
	public static void main(String args[]) {
		int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
		counting_sort(arr);
		for(int x:arr) System.out.format("%d ",x); 
		// 0 1 2 3 4 5 6 7 8 9 10 100 
	}
}

5 PHP[ | ]

function counting_sort(&$a) {
    $count=[];
    foreach($a as $x) {
        if(!array_key_exists($x,$count)) $count[$x]=1;
        else $count[$x]++;
    }
    ksort($count);
    $pos=0;
    foreach($count as $x => $repeat) {
        while( $repeat-- > 0 ) $a[$pos++]=$x;
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
counting_sort( $arr );
echo implode(',', $arr);
# -1,0,1,1,4,9,10,22,22,100

6 Python[ | ]

def counting_sort(a):
	count={}
	for x in a: count[x]=count.get(x,0)+1
	pos=0
	for x,repeat in sorted(count.items()):
	    a[pos:pos+repeat] = [x]*repeat
	    pos += repeat
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]

7 Ruby[ | ]

def counting_sort(a)
    count={}
    for x in a
        if not count.key?(x) then count[x]=1
        else count[x]+=1 end
    end
    pos = 0
    for x,repeat in count.sort_by {|k,v| k}
        a[pos,repeat] = Array.new(repeat,x)
        pos += repeat
    end
end
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]

8 같이 보기[ | ]

9 참고[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}