C YC

IT Dev who working in Tokyo

3 minute read

개요

힙 정렬(Heap Sort)이란? => 이진 트리구조를 이용하여 정렬하는 방식으로, 최대 최소값을 빠르게 가져오기 위해 고안된 정렬방식

정렬하는 과정

  1. 가장 끝 자리에 노드를 삽입
  2. 노드와 부모 노드를 비교한다.
  3. 규칙(크거나 작거나)에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
  4. 모든 노드가 규칙에 맞을 때까지 3번을 반복

heapsort

(이미지 출처 :https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC)


  • 장점
    • 최대 최소값을 구할때 유용하다.
  • 단점
    • 데이터의 상태에 따라 다소 느리다.

유니티에서 예제

소스코드

아래는 유니티를 기준으로 작성하였으나 기본적으로 C#이기때문에 숫자를 입력하고 출력하는 부분 외에는 바로 참고하셔도 무방합니다.

[초기화 및 출력함수]

#region private
    [SerializeField] InputField m_input_txt;
    [SerializeField] Text m_answer_txt;

    string[] m_split_text;
    string m_input_text, m_output_text;
    List<int> split_number_list;
#endregion

    public override void Awake()
    {
        m_input_text = null;
        m_output_text = null;

        split_number_list = new List<int>();
    }

    /// <summary>
    /// splite number and add in to list
    /// </summary>
    void InitList()
    {
        m_input_text = m_input_txt.GetComponent<InputField>().text;

        // split text of inputfield
        m_split_text = m_input_text.Split(',');

        // add splited text into int list(split_number_list) 
        for (int count = 0; count < m_split_text.Length; count++) {
            split_number_list.Add(int.Parse(m_split_text[count]));
        }
    }

    /// <summary>
    /// Show number list
    /// </summary>
    void ShowText()
    {
        for (int count = 0; count < split_number_list.Count; count++) {
            m_output_text += split_number_list[count].ToString() + " ";
        }

        // Display result of QuickSort
        m_answer_txt.text = m_output_text;
    }


[힙생성]

    /// <summary>
    /// activate when press enter
    /// </summary>
    void OnclickEnter()
    {
        InitList();
        // 트리구조를 힙 구조로 변환
        for(int count = (split_number_list.Count - 1)/2; count >= 0; --count) {
            HeapSort(count, split_number_list.Count);
        }

        // 힙의 크기를 줄이면서 반복적으로 힙을 구성
        for (int count = split_number_list.Count - 1; count > 0; --count) {
            Swap(count, 0);
            HeapSort(0, count);
        }

        ShowText();
    }



[정렬]

    /// <summary>
    /// Heap Sort
    /// </summary>
    /// <param name="root_num">first num</param>
    /// <param name="max_num">last num</param>
    private void HeapSort(int root_num, int max_num)
    {
        while(root_num < max_num)
        {
            int _child = root_num * 2 + 1;
            // child중 더 큰 값을 찾기
            if ((_child + 1 < max_num) && (split_number_list[_child] < split_number_list[_child + 1])) {
                ++_child;
            }
            // root_num보다 child가 더 크면 교환 
            if ((_child < max_num) && (split_number_list[root_num] < split_number_list[_child])) {
                Swap(root_num, _child);
                root_num = _child;
            } else {
                break;
            }
        }
    }

    /// <summary>
    /// Swap number which is in splited list
    /// </summary>
    /// <param name="num_1">first num</param>
    /// <param name="num_2">second num</param>
    private void Swap(int num_1, int num_2)
    {
        int temp = split_number_list[num_1];
        split_number_list[num_1] = split_number_list[num_2];
        split_number_list[num_2] = temp;
    }


[전체 코드]

public class HeapSortManager : BaseTemplateClass
{
#region private
    [SerializeField] InputField m_input_txt;
    [SerializeField] Text m_answer_txt;

    string[] m_split_text;
    string m_input_text, m_output_text;
    List<int> split_number_list;
#endregion

    public override void Awake()
    {
        m_input_text = null;
        m_output_text = null;

        split_number_list = new List<int>();
    }

    /// <summary>
    /// splite number and add in to list
    /// </summary>
    void InitList()
    {
        m_input_text = m_input_txt.GetComponent<InputField>().text;

        // split text of inputfield
        m_split_text = m_input_text.Split(',');

        // add splited text into int list(split_number_list) 
        for (int count = 0; count < m_split_text.Length; count++) {
            split_number_list.Add(int.Parse(m_split_text[count]));
        }
    }

    /// <summary>
    /// Show number list
    /// </summary>
    void ShowText()
    {
        for (int count = 0; count < split_number_list.Count; count++) {
            m_output_text += split_number_list[count].ToString() + " ";
        }

        // Display result of QuickSort
        m_answer_txt.text = m_output_text;
    }

    /// <summary>
    /// Heap Sort
    /// </summary>
    /// <param name="root_num">first num</param>
    /// <param name="max_num">last num</param>
    private void HeapSort(int root_num, int max_num)
    {
        while(root_num < max_num)
        {
            int _child = root_num * 2 + 1;
            // child중 더 큰 값을 찾기
            if ((_child + 1 < max_num) && (split_number_list[_child] < split_number_list[_child + 1])) {
                ++_child;
            }
            // root_num보다 child가 더 크면 교환 
            if ((_child < max_num) && (split_number_list[root_num] < split_number_list[_child])) {
                Swap(root_num, _child);
                root_num = _child;
            } else {
                break;
            }
        }
    }

    /// <summary>
    /// Swap number which is in splited list
    /// </summary>
    /// <param name="num_1">first num</param>
    /// <param name="num_2">second num</param>
    private void Swap(int num_1, int num_2)
    {
        int temp = split_number_list[num_1];
        split_number_list[num_1] = split_number_list[num_2];
        split_number_list[num_2] = temp;
    }

    /// <summary>
    /// activate when press enter
    /// </summary>
    void OnclickEnter()
    {
        InitList();
        // 트리구조를 힙 구조로 변환
        for(int count = (split_number_list.Count - 1)/2; count >= 0; --count) {
            HeapSort(count, split_number_list.Count);
        }

        // 힙의 크기를 줄이면서 반복적으로 힙을 구성
        for (int count = split_number_list.Count - 1; count > 0; --count) {
            Swap(count, 0);
            HeapSort(0, count);
        }

        ShowText();
    }
}


실행 영상





Top

You May Also Enjoy

2 minute read