소소한 일상 블로그

제목에는 정렬계의 노답 삼형제라고 적었지만, 다 쓸모가 있기에 존재하겠죠... (라고 말했지만 노답 삼형제 맞는거 같은데, 쓰기 쉽단거 빼면...)

1. 버블 정렬

정렬되는게 거품이 보글보글 올라오는 것과 같아서 버블 정렬이라고 합니다. 정렬해라 했을 때 가장 직관적으로 생각하기 쉬운 알고리즘이죠. 쉬운만큼 비효율적이기도 하고요.

 동작방식은 집합 내의 이웃 요소들끼리 비교하여 교환을 통해 정렬됩니다. 쉽게 말해 키순으로 정렬했을 때 내 앞에 있는 애가 나보다 키가 작으면 자리를 바꿔가며 키가 가장 큰 애를 맨 앞까지 오게 하는 거죠.

동작 예시 :

 백마디 말보다 예를 들어 보죠.

 자 밑에 3,2,4,1 의 정렬되지 않은 숫자가 있습니다.

버블정렬을 통해 오름차순으로 정렬해보죠. (뒤에 나올 정렬들도 동일한 수로 하겠습니다.)

빨간 네모는 비교를 의미합니다.

[1싸이클]

3을 기준으로 이웃한 2와 비교하여 3이 더 크므로 교환.

3을 기준으로 이웃한 4와 비교하여 4가 더 크므로 교환되지 않습니다.

1싸이클의 마지막으로 4와 이웃한 1을 비교하여 맨 마지막 요소에 4가 확정됩니다.

1싸이클을 통해 마지막은 4가 확정됬으므로 다음 싸이클부터는 4는 제외해도 되겠네요.

[2싸이클]

이미 이웃한 3이 더 크므로 교환하지 않습니다.

3이 이웃한 1보다 크므로 교환.

2싸이믈을 마지막을 확정된 3 역시 이후 부터는 제외됩니다.

[3싸이클]

마지막으로 2와 1을 비교하여 정렬을 마무리합니다.

총 3싸이클이 돌고, 비교연산은 6번, 교환은 4번 있었네요. 

최악의 경우 즉, 만약 역으로 정렬되어있었다면, 비교는 언제나 6번이고, 교환은 비교연산 할 때마다 일어나겠죠 (6번)

장점 : 

만들기 쉽다...

단점 :

비교 연산도 교환 연산도 많다.

시간복잡도 : O(n^2)

활용:

언제나 중요한 건 "그래서 이걸 어따 써먹을수 있는데?" 라고 생각합니다. 이게 곧 배우는 이유니까요.

 버블 정렬은 비효율의 대명사죠...

실제로 대학교에서 버블정렬을 접할 때, 이걸 배우는 이유는 비효율을 알아야 효율을 알 수 있기때문에 배우는거라고도 교수님이 그러셨죠.

2. 선택 정렬

 선택 정렬은 정렬되지 않은 집합 내 요소 중 가장 크거나 작은 것을 선택해 차례로 맨 앞이나 뒤로 보내 정렬하는 알고리즘입니다.

  쉽게 생각해서 포커나 고스톱을 칠 때, 카드를 다 받고나면 뒤죽박죽 섞여있잖아요. 그 때 카드들을 작은 것부터 뽑아서 앞으로 옮기면서 보기 좋게 바꾸죠. (버블 정렬처럼 옆으로 차례차례 옮기진 안잖아요?) 그런 방식을 생각하면 됩니다.

동작 예시:

빨간 네모는 최소값으로 선택된 요소입니다.

[1싸이클]

각 요소들의 최소값을 판별하면 1이 최소값인걸 알 수 있죠.

선택된 최소값인 1을 맨 앞으로 이동시킵니다.

[2싸이클]

[3싸이클]

3싸이클에 비교연산은 총 6번, 교환은 2번 일어났네요.

최악의 경우엔, 비교는 동일하고 (매번 동일하겠죠), 교환은 3번 일어날겁니다.

장점 :

버블에 비해 교환 연산이 적다. (최대 n번)

단점 :

안정성을 보장하지 않는다.

(같은 값이 있을 때 상대적으로 같은 위치에 있을거라 보장하지 못한다. 즉 정렬 후에는 순서가 뒤바껴 있을 수 있다.)

비교연산이 많다. (매번 최소값을 구해야하므로)

위와 같은 이유로 집합이 클수록 속도가 크게 느려진다.

시간복잡도 : O(n^2)

활용:

집합이 작은 정렬  + 안정성이 보장될 필요 없는 경우 

3. 삽입 정렬

 삽입 정렬은 정렬이 필요한 요소를 뽑아 적당한 곳에 삽입하는 정렬입니다. 적당히라는 말이 들어가있네요. 가장 어려운 말이죠.... 좀 더 풀어 설명하죠. 정렬되지 않은 요소를 순서대로 뽑아 이미 정렬되어 있는 집합 내 올바른 위치에 삽입하는 정렬입니다. 그렇기 때문에 우선 맨 앞의 요소를 정렬된 집합으로 취급하여 두 번째 요소부터 비교가 진행되죠. 

 바닥에 흩어진 트럼프 카드를 주우며 정렬하고자 할 때, 이 방법이 쓰이겠네요. 한 장씩 주우면서 이미 정렬되어 내 손에 쥐어진 카드에 올바른 위치에 넣는 식으로 정렬을 하겠죠.

동작 예시:

빨간 네모는 비교대상

빨간 선은 비교입니다.

[1싸이클]

3은 이미 정렬된 집합으로 판단하고, 두 번째 요소인 2와 비교해 정렬된 집합 내에 맨 앞으로 이동됩니다.

[2싸이클]

4를 이미 정렬된 집합의 맨 마지막과 먼저 비교하여 4보다 큰 수가 없으므로 맨 뒤에 정렬됩니다.  

[3싸이클]

1을 이미 정렬된 집합의 맨 앞의 2와 비교했을 때. 1일 작으므로 바로 맨 앞으로 이동시킨다.

이로써 싸이클 종료.

3싸이클에 비교연산은 총 3번, 교환은 2번 일어났네요.

최악의 경우엔? 4,1,2,3가 될거 같네요. 비교 6번에 교환은 3번 일어납니다.

장점 :

교환 연산이 비교적 적다. (최대 n번)

이미 일부 정렬된 상태라면 비교연산이 줄어 속도가 빠르다.

단점 :

정렬상태에 따라 속도가 민감하다.

시간복잡도 : O(n^2)

활용:

이미 일정부분 정렬되어 있는 집합.

정렬된 요소에 새 요소의 추가가 빈번할 때.

*항상 선택정렬하고, 삽입정렬하고 헷갈린다... 선택정렬은 최소값이나 최대값을 선택하여 정렬하고, 삽입정렬은 앞에서부터 순서대로 삽입하면서 정렬한다라고는 생각하지만... 아마 한 달 뒤면 또 헷갈리겠지... (삽입과 선택이라는 단어가 바꾸고자 하면 충분히 바꿀 수가 있는지라....)

처음 유니티의 C#을 접했을 때 가장 궁금했던 점이 델리게이트의 존재 이유였다.

델리게이트는 콜백함수로 사용할 때 주로 사용되는 대리자 변수 개념인데, 이전에 JAVA를 주로 사용하던 저로써는 인터페이스로 콜백함수를 구현 할 수 있는데 왜 델리게이트가 또 필요하지 싶었다.

뭐 그런거를 궁금해하냐 할 수도 있는데.. 저같은 경우 뭐든 반드시 그게 필요한 경우가 있기때문에 존재한다고 생각하는 편이라 의문을 가지게 되었다.

혹시 저와 비슷한 생각을 가진 사람들에게 조금이라도 도움이 됐으면하는 생각에 여기저기 조사하고, 사용해보며 느낀 것을 좀 적고자 한다.

우선 두 개념부터 간단하게 살펴보면

1. 인터페이스

클래스의 형태를 디자인 / 정의하는 것이죠

다시말하면 "이 인터페이스를 구현하는 클래스는 이 함수를 반드시 가져야해" 하고 껍데기를 정의하고 있는거죠.

주요특징은

기본적으로 메소드 정의를 하면 public 권한에 추상이기 때문에 인터페이스내에서 구현을 할 순 없고, 때문에 인터페이스 자체로 변수를 생성해내진 못합니다 (new) 

그리고 인터페이스는 클래스와는 달리 다중 상속이 가능하죠.

기능상으로는 껍데기를 정의하는 기능밖에 없지만 실제 활용면에서는 범용적으로 함수를 호출하기에 굉장히 좋죠. 왜냐! 이 인터페이스를 구현하고있는 클래스는 무조건 이 함수를 가지고 있다는 것을 알기때문이죠.

그래서 호출부 입장에서는 실제 내부는 어떻게 구현했는지 몰라도 해당 인터페이스의 함수를 필요에 의해 호출해 사용하죠.

게다가 클래스나 추상클래스와는 달리 다중 상속이 가능하기 때문에 필요한 함수가 속해있는 인터페이스를 필요에따라 여러개 가져다 쓸 수 있죠.

이런 점을 이용해서 JAVA에서는 주로 콜백함수로도 많이 활용하죠.

아래부터는 예전에 DB 콜백함수를 구현할 때 사용한 코드 일부입니다. (언어는 C#인데....)

public interface DB_callback
{
   void callback_result(string str);
}

위와 같이 DB_callback 인터페이스를 생성해놓고, DB 콜백이 필요한 클래스에서는 해당 인터페이스를 구현하는 방식으로 만들었죠.

open_db 함수에서 send_query 함수에 자기자신을 매개변수로 보내고 있습니다.

  public class MatchQuizManager : MatchManager, DB_callback
  {
         void open_db()
         {
               // 유저 퀴즈 씬.
               AmazonDBManager db_manager = new AmazonDBManager();
               Dictionary<string, string> fields = new Dictionary<string, string>();
               fields.Add("type", "0");
               fields.Add("db", "0");
               fields.Add("resultType", "1");
               fields.Add("quiz_index", index.ToString());
               fields.Add("sub", "0");
               StartCoroutine(db_manager.send_query(fields,this)); // DB 연결시 자기자신 전달
         }
         //콜백함수
         public void callback_result(string str)
        {
               Quiz quiz = Split_quiz(str);
               Split_index(quiz.quiz_question);
               phase = Phase.answer;
               split_answer_index(quiz.quiz_answer);
               subject_text.text = quiz.quiz_subject;
               explain_text.text = quiz.quiz_content;
         }
  }

그리고 실제 DB 클래스에서는 DB_callback 인터페이스를 전달받아 DB_callback의 함수를 호출하기만 하면 실제 호출하고 있는 클래스의 DB 콜백함수들을 호출하게 되죠.

아래 소스에서 전달받은 callback의 callback_result를 호출하고 있죠.

 public class AmazonDBManager : MonoBehaviour {
     public IEnumerator send_query(Dictionary<string,string> fields,DB_callback callback)
     {
         WWWForm form = new WWWForm();
         foreach(KeyValuePair<string,string> field in fields)
         {
                form.AddField(field.Key, field.Value);
         }
         WWW webRequest = new WWW("서버경로", form);

         yield return webRequest;
         if (webRequest.isDone)
         {
               if (callback != null)
              {
                    callback.callback_result(webRequest.text); //인터페이스의 콜백함수 호출
              }
         }
         else
        {
              Debug.Log("webRequest error");
         }
     }
}

*콜백 외에는 별도로 설명하지 않겠습니다.    

과정을 요약하면

1) callback 함수를 가진 DB_callback 인터페이스 생성

2) DB를 사용할 클래스에서 DB_callback 인터페이스의 callback 함수를 구현 (인터페이스에서 제공하는 함수만 구현)

3) DB를 사용할 클래스에서 DB 연결 클래스로 DB 연결 클래스에 자기 자신을 넘김.

3) DB를 연결하는 클래스에서 DB_callback 인터페이스를 전달받아 callback 함수 호출.

2. 델리게이트

C#의 델리게이트는 말그대로 대리자 개념으로, 반환형과 매개변수가 동일한 함수를 등록해놓으면 대신 함수를 호출해주는 변수이다.

단순하게 생각하면 실행해야될 함수를 저장해놓는다? 라고 생각하면 될 것 같다.

변수이기 때문에 우선 반환형과 매개변수를 정의해야한다.

그리고 해당 델리게이트 타입으로 변수를 생성해서 변수에 함수를 참조시키면 연결 끝!

  public class AmazonDBManager : MonoBehaviour {
        public delegate void DBFunc(string str);    //타입 선언 (반환형 void, 매개변수 string)
        //DBFunc amazonDBFunc        // 일반적인 델리게이트 변수 선언
        // 델리게이트를 매개변수로 받는다. (함수를 전달)
        public IEnumerator send_query(Dictionary<string,string> fields,DBFunc amazonDBFunc)
        {
              //중복 생략
             if (webRequest.isDone)
             {
                    if (callback != null)
                    {
                          amazonDBFunc(webRequest.text);      //전달된 콜백 함수 호출
                    }
             }
        }
  }

아래는 위의 MatchQuizManager의 함수들을 델리게이트 형식으로 변경했을 때.

   void open_db()
  {
       //중복 생략
       StartCoroutine(db_manager.send_query(fields,callback_result));        // 함수를 전달

       // 필요에 따라 다른 함수를 콜백함수로 전달.
       //StartCoroutine(db_manager.send_query(fields,callback_result_another));
  }
  //콜백함수
  public void callback_result(string str)
  {
        //중복 생략
  }
  public void callback_result_another(string str)
  {
        //다른 일
  }

변수타입이기 때문에 델리게이트를 매개변수로 전달받는 함수를 만들어놓으면 동일한 시그니쳐를 같는 함수를 전달 할 수 있고, 여러 함수를 하나의 델리게이트 변수에 연결하는 델리게이트 체인도 가능하다.

ex)

amazonDBFunc += callback_result_select

amazonDBFunc += callback_reault_insert

amazonDBFunc(str) //실행시 체인된 함수들을 모두 실행시킨다.

딱 기능만 봐도 콜백함수에 특화되어 있는게 느껴진다.

그럼 마찬가지로 과정을 요약하면

1) callback 받을 함수 형태를 delegate 변수로 선언

2) DB를 사용할 클래스에서 1)의 델리게이트와 동일한 형태로 콜백함수 작성 (콜백함수를 여러개 작성 가능)

3) DB를 사용할 클래스에서 콜백함수를 DB 연결 클래스에 전달

4) DB 연결 클래스에서 델리게이트 변수를 실행.

음....전체적인 사용방법과 2)번의 과정에서 큰 차이가 보이네요.

개념은 전혀 다른데요?

네, 개념은 다르지만 역할면에서 공통분모가 있습니다. 둘 다 콜백함수에 사용되죠...

JAVA에서 인터페이스를 콜백함수를 위해서 자주 사용하다보니 그것에 길들여져 델리게이트의 필요성을 잘 못느꼈죠.

개인적인 결론
델리게이트를 여러번 사용해보면서 이제와서 생각해보면 콜백의 역할을 수행하는건 델리게이트가 맞는거 같다고 생각한다. JAVA에는 저런게 없어서 인터페이스를 사용해서 매꾼걸까...

특히 델리게이트의 체인과 함수를 넘길 수 있다는 점이 굉장히 좋은 점인 것 같다.

인터페이스를 이용해서 콜백함수를 만들게 되면 하나의 클래스에는 하나의 콜백함수만 존재하게 되고, 호출부에서는 하나의 함수만을 호출한다. 하지만 델리게이트처럼 필요에 따라 함수를 넘기는 식으로 하면 하나의 클래스에서도 다양한 함수를 넘길 수 있다. 콜백함수에 특화되어 있는 느낌?

예를 들어) A 클래스에서 DB를 통해 하고자 하는 행동이 DB에서 Select해서 얻은 걸 출력하는 것과 Update한 결과 행 수를 받는 것 두 가지라고 했을 때, 

 - 인터페이스를 사용하면 인터페이스에 정의된 함수에 모든걸 작성해야 합니다. 하나의 함수내에서 select 결과와 update를 분기처리해서 처리하는 것이죠. 설령 클래스에서 하고자하는 행동이 3~4가지가 되어도 하나의 함수내에서 해결을 해야하죠. (물론 여러 콜백을 만들어도 되지만 이러면 다른 구현클래스도 통일해줘야하여 쓸모없는 코드가 생긴다.)

 - 델리게이트를 쓰게되면 select 용 함수, update용 함수를 별도로 작성하여 필요에 맞춰 적절하게 넘겨주면 되죠. DB에 접근하여 하는 전혀 다른 행동이 10개면 10가지의 함수를 반환형과 매개변수만 동일하게 갖추고 DB에 연결할 때 필요한 함수를 전달하면 됩니다.

*가르치기 위한 글보다는 공부하며 생각을 정리하며 쓰는 글입니다. 잘못된 정보가 있을 수도 있으며, 혹시 잘못된 부분을 발견하거나 의아한 점이 있을시 피드백을 주시면 큰 힘이 됩니다!