[C#] 2차원 배열 정렬하기(1)_ counting sort

안녕하세요. 우당탕탕 개발일지 입니다. 이번학기에 학과 과목으로 C#을 배우게 되었습니다. 3학년이 되서 배우다 보니 기초 문법부터 배우진 않았습니다. 과제나 수업중 배운 부분, 그리고 따로 공부한 정렬 알고리즘 같이 올리겠습니다! 아자아자 화이팅!

 

데이터 수 : 50만개 
열: idx, 과목1, 과목2, 과목3 , 과목 합계 , 순위 
정렬 방법 : couting sort, radix sort
출력: 각 정렬의 처리 시간. 

 

0. 기본 세팅 

• Random() 이용 => a.Next(101); 범위가 0~100까지 숫자만 랜덤으로 들어감. 
• Clone()이용 => 배열 복사하는 내장함수.

static void Main(string[] args)
{
	int[,]a =new int[500000,6];// 500000명의 데이터 (번호, 성적1, 성적2, 성적3, 합계, 순위)
    
    Random r =new Random();
    
    for(int i=0; i<a.GetLength(0); i++)
    {
    	a[i,0]=i+1; // 순위 
    	a[i,1]=r.Next(101); // 성적1
        a[i,2]=r.Next(101); // 성적2
        a[i,3]=r.Next(101); // 성적3
        
        a[i,4]=a[i,1]+a[i,2]+a[i,3]; // 합계
        
    }
    
    // 다른 배열로 복사해서 정렬하기
    int [,] arr_counting =(int[,])a.Clone(); 
    int [,] arr_radix = (int[,])a.Clone();
    
    
    
    
}

 

 

시간 측정을 위한 내장함수 : Stopwatch()

using System.Globalization; // 시간 측정을 위한 

Stopwatch sw = Stopwatch.StarNew();

sw.Start();

~~~~

sw.Stop();

---

 

1. 50만개의 데이터를 출력하지는 않지만 test시 정렬이 올바르게 되었는지 확인하는 함수 : Print();

• \t : tab된 것 처럼 화면에 출력되어 한눈에 알아보기 쉬움. 
• array.GetLength(0): 2차원 배열은 열,행의 길이가 다를 수 있음 => GetLength(0)은  array[a,b]에서 자리.

static void Print(int[,]array)
{
	Console.WriteLine("번호\t성적1\t성적2\t성적3\t합계\t순위");
    for(int i=0; i<array.GetLength(0); i++)
    {
    	for(int j=0; j<array.GetLength(1); j++)
        {
        	Console.Write(array[i,j]+ "\t");
        }
        Console.WriteLine();
    }
    
    Console.WriteLine();


}

---

 

2.  Counting sort 

* 배열의 수의 범위를 알아야 함! 

*배열의 수의 범위 만큼의 임시 배열을 만들기 -> 거기에 해당 하는 값을 count -> 오름차순인 경우 임시배열이 0이 아닌 값을 순서대로 출력하면 정렬 완료됨.

 

2-1 Counting sort_C++

 #include<iostream>
 using namespace std;
 
 int main()
 {
 	int n;
  	cin>>n;
 	int arr[n];
  
    for(int i=0; i<n; i++)
    {
    	cin>>arr[i];
    }
    
    // arr의 값의 범위 0~100
    int tmp[101]={};
    
    for(int i=0; i<n; i++)
    {
    	for(int j=0; j<101; j++)
        {
        	if(j==arr[i])
            {
            	tmp[j]++;
            }
        }
    	
    }
    
    
    /* for(int i = 0; i < n; i++) {
        tmp[arr[i]]++;
    }*/
    
    
    
    
    int idx=0;
   for(int i=0; i<101; i++)
   {
   		if(tmp[i]==1)
        {
        	arr[idx++]=tmp[i];
        }
        else if(tmp[i]>1)
        {
        	for(int k=0; k<tmp[i]; k++)
            {
            	arr[idx++]=tmp[k];
            }
        }
   }
    
 
 
 
 }

---

 

2-2 C# 2차원 배열로 Couting sort구현

static void Counting_sort_func(int[,]arr)
{
	Stopwatch sw =new Stopwatch();
    sw.Start();
    
    int n=arr.GetLength(0);
    int size =arr.GetLength(1);
    
    // 합의 최대값 : 0~300
    
    int []tmp =new int[301];
    
    //초기화 
    for(int i=0; i<n; i++)
    {
    	for(int j=0; j<301; j++)
        {
        	if(arr[i,4]==j)
            {
            	tmp[j]++;
            }
        }
    }
    
    
    int[,]sorted_arr =new int[n,size];
    int[]rank=new int[n];
    
    int r=1;
    int idx=0;// 정렬된 배열
    
    for(int i=300; i>=0; i--)// 내림차순
    {
    	if(tmp[i]>0) // 수가 들어 있는 곳만 
        {
        	for(int k=0; k<n; k++)// 일치하는 값이 있는 열 전부 복사 하기 위해서 반복문 사용. 
            {
            	if(arr[i,4]==i) // 
                {
                	sorted_arr[idx,j]=arr[i,j]; // 정렬한거 2차원 배열에 넣어주기
                }
              rank[idx]=r;
              idx++;
            }
          r=idx++;//순위 증가
        }
    }
    
    
    for(int i=0; i<n; i++)
    {
    	sorted_arr[i,5]=ranks[i];
    }
    
    
   for (int i = 0; i < n; i++)
	{
    	for (int j = 0; j < size; j++)
    	{
       		 array[i, j] = sorted_arr[i, j];
    	}
	}


	sw.Stop();
	Console.WriteLine($"Counting sort: {sw.ElapsedMilliseconds}ms");
}