[멋쟁이사자처럼 부트캠프 TIL] 유니티 게임 개발 3기 : 정렬

 

버블정렬

인접한 두 원소를 비교하여 정렬

프로세스는 아래 유튜브 영상 참고

https://www.youtube.com/watch?v=Iv3vgjM8Pv4

public void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 두 원소 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // = (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);

            }
        }
    }
}

 

퀵정렬

분할정복방법을 통한 정렬

자세한 내용은 해당 글을 참고

https://jeonyeohun.tistory.com/102

// 퀵 정렬(QuickSort) 함수
// 입력: 정렬할 배열 arr, 시작 인덱스 low, 끝 인덱스 high
public void QuickSort(int[] arr, int low, int high)
{
    // low가 high보다 작을 때만 정렬을 수행
    if (low < high)
    {
        // 배열을 분할하고 피벗(pivot)의 위치를 찾음
        int pi = Partition(arr, low, high);

        // 피벗 왼쪽 부분을 재귀적으로 정렬
        QuickSort(arr, low, pi - 1);

        // 피벗 오른쪽 부분을 재귀적으로 정렬
        QuickSort(arr, pi + 1, high);
    }
}

// 배열을 분할하고 피벗의 최종 위치를 반환하는 함수
private int Partition(int[] arr, int low, int high)
{
    // 마지막 요소를 피벗으로 선택
    int pivot = arr[high];

    // i는 작은 요소가 배치될 위치를 추적
    int i = (low - 1);

    // 배열의 low부터 high-1까지 반복
    for (int j = low; j < high; j++)
    {
        // 현재 요소가 피벗보다 작으면
        if (arr[j] < pivot)
        {
            i++; // 작은 요소 위치를 한 칸 앞으로 이동

            // i와 j 위치의 요소를 교환
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 피벗을 올바른 위치로 이동
    int temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;

    // 피벗의 최종 위치를 반환
    return i + 1;
}

 

시각화

결과물

// Bar.cs

using System.Collections;
using System.Collections.Generic;
using TMPro;
using UnityEngine;

// 정렬 시각화에 사용되는 막대(Bar) 컴포넌트 클래스
// 각 막대는 데이터 값, 텍스트, 스틱(막대 본체)을 가지고 있음
public class Bar : MonoBehaviour
{
    // 이 막대가 나타내는 실제 데이터 값 (정렬할 숫자)
    public int _data;

    // 리사이즈(위치 및 크기 조정) 작업이 완료되었는지 확인하는 플래그
    // 애니메이션 동기화 및 완료 상태 추적에 사용
    public bool bResizeFinish;
    
    // 데이터 값을 표시할 TextMeshPro 컴포넌트
    // Unity UI에서 3D 텍스트를 렌더링하는 고급 텍스트 컴포넌트
    public TextMeshPro _text;

    // 실제 막대 오브젝트 (시각적 표현)
    public GameObject _stick;

    // 오브젝트가 생성될 때 최초로 호출되는 메서드
    // 텍스트를 _data 값으로 초기화
    void Start()
    {
        // 막대의 데이터 값을 텍스트로 변환하여 표시
        _text.text = _data.ToString();
    }
    
    // 외부에서 막대의 위치와 크기를 부드럽게 조정하는 메서드
    // 정렬 과정에서 막대의 위치를 변경할 때 사용
    public void SetData(int index)
    {
        // 보간(Lerp) 코루틴 시작
        // 부드러운 위치 및 크기 변환 애니메이션 실행
        StartCoroutine(Lerp(index));
    }

    // 부드러운 보간(Interpolation) 애니메이션을 처리하는 코루틴
    // 시간에 따라 점진적으로 위치와 크기를 변경
    IEnumerator Lerp(int index)
    {
        // 리사이즈 작업 시작 시 완료 플래그를 false로 설정
        bResizeFinish = false;
        
        // 보간 진행 시간 추적 변수
        float t = 0.0f;
        // 애니메이션 지속 시간 (0.3초 동안 변환)
        float duration = 0.3f;

        // 지속 시간 동안 프레임마다 부드러운 보간 수행
        while (true)
        {
            // 프레임 간 경과 시간 누적
            t += Time.deltaTime;

            // 지정된 지속 시간 도달 시 루프 종료
            if (t >= duration)
            {
                break;
            }
            
            // 스틱의 위치를 목표 위치로 부드럽게 이동
            // t/duration을 통해 0에서 1 사이의 보간 비율 계산
            _stick.transform.position = Vector3.Lerp(
                _stick.transform.position, 
                new Vector3(index, _data / 2.0f, 0), 
                t / duration
            );

            // 스틱의 크기를 데이터 값에 맞게 부드럽게 조정
            _stick.transform.localScale = Vector3.Lerp(
                _stick.transform.localScale, 
                new Vector3(1, _data, 1), 
                t / duration
            );

            // 텍스트 위치를 스틱 위치에 맞춰 조정 (z축으로 약간 뒤로 배치)
            _text.transform.position = _stick.transform.position + new Vector3(0, 0, -3.0f);

            // 다음 프레임까지 대기
            yield return null;
        }
        
        // 최종 위치와 크기를 정확히 설정 (보간 오차 보정)
        _stick.transform.position = new Vector3(index, _data / 2.0f, 0);
        _stick.transform.localScale = new Vector3(1, _data, 1);
        _text.transform.position = _stick.transform.position + new Vector3(0, 0, -3.0f);
        
        // 리사이즈 작업 완료 플래그 설정
        bResizeFinish = true;
    }
}

// BubbleSort.cs

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

// 정렬 알고리즘 시각화를 담당하는 QuickSort 클래스
// 배열의 막대를 생성하고 정렬 과정을 시각적으로 보여줌
public class BubbleSort : MonoBehaviour
{
    // 막대의 상태를 표현하기 위한 머티리얼 (재질) 선언
    // 각 상태에 따라 다른 색상으로 막대의 상태를 표시
    public Material swapMaterial;   // 교환 중인 막대를 나타내는 머티리얼
    public Material pivotMaterial;  // 피벗(기준점) 막대를 나타내는 머티리얼
    public Material normalMaterial; // 일반 상태의 막대를 나타내는 머티리얼
    
    // 생성할 막대(Bar) 프리팹
    public Bar barPrefab;
    
    // 기본적인 버블 정렬 알고리즘 구현 메서드
    // 실제 시각화에는 사용되지 않지만, 참고용으로 구현
    public void _BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            // 배열을 순회하며 인접한 요소 비교
            for (int j = 0; j < n - i - 1; j++)
            {
                // 현재 요소가 다음 요소보다 크면 교환
                if (arr[j] > arr[j + 1])
                {
                    // 튜플을 이용한 간결한 요소 교환
                    (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
                }
            }
        }
    }
    
    // 현재 파티션의 피벗 인덱스를 저장하는 변수
    // QuickSort 알고리즘에서 분할 지점을 추적하는 데 사용
    private int pi = 0;
    
    // QuickSort의 핵심 파티션 메서드 (코루틴)
    // 배열을 분할하고 피벗을 기준으로 요소들을 재배치
    private IEnumerator Partition(Bar[] arr, int low, int high)
    {
        // 가장 오른쪽 요소를 피벗으로 선택
        int pivot = arr[high]._data; 
        
        // 작은 요소들의 인덱스를 추적하는 변수 (초기값: low - 1)
        int i = (low - 1);

        // 배열의 low부터 high-1까지 순회
        for (int j = low; j < high; j++)
        {
            // 현재 요소가 피벗보다 작으면
            if (arr[j]._data < pivot)
            {
                // 작은 요소의 인덱스 증가
                i++;
           
                // 요소 위치 교환
                (arr[i], arr[j]) = (arr[j], arr[i]);
                
                // 막대 위치 및 크기 조정
                arr[j].SetData(j);
                arr[i].SetData(i);
                
                // 교환 중인 막대 색상 변경
                arr[j]._stick.GetComponent<MeshRenderer>().material = swapMaterial;
                arr[i]._stick.GetComponent<MeshRenderer>().material = swapMaterial;

                // 애니메이션 동기화를 위한 지역 변수
                var i1 = i;
                var j1 = j;
                
                // 막대 위치 조정이 완료될 때까지 대기
                yield return new WaitUntil(() => arr[i1].bResizeFinish && arr[j1].bResizeFinish);
                
                // 막대 색상 초기화
                arr[j]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
                arr[i]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
            }
        }
        
        // 피벗을 올바른 위치로 이동
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        
        // 막대 위치 및 크기 조정
        arr[i + 1].SetData(i + 1);
        arr[high].SetData(high);
        
        // 교환 중인 막대 색상 변경
        arr[i + 1]._stick.GetComponent<MeshRenderer>().material = swapMaterial;
        arr[high]._stick.GetComponent<MeshRenderer>().material = swapMaterial;

        // 막대 위치 조정이 완료될 때까지 대기
        yield return new WaitUntil(() => arr[i + 1].bResizeFinish && arr[high].bResizeFinish);

        // 막대 색상 초기화
        arr[i + 1]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        arr[high]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        
        // 이전 피벗 색상 초기화
        arr[pi]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        
        // 새로운 피벗 인덱스 설정 및 색상 변경
        pi = i + 1;
        arr[pi]._stick.GetComponent<MeshRenderer>().material = pivotMaterial;
    }
    
    // 재귀적 QuickSort 알고리즘 구현 (코루틴)
    // 배열을 재귀적으로 분할하여 정렬
    public IEnumerator QuickSort(Bar[] arr, int low, int high)
    {
        // 부분 배열의 크기가 2개 이상일 때만 정렬 수행
        if (low < high)
        {
            // 파티션 분할 수행
            yield return StartCoroutine(Partition(arr, low, high));
            
            // 왼쪽 부분 배열 정렬
            yield return StartCoroutine(QuickSort(arr, low, pi - 1));
            
            // 오른쪽 부분 배열 정렬
            yield return StartCoroutine(QuickSort(arr, pi + 1, high));
        }
    }

    // 초기화 메서드 (게임 시작 시 호출)
    void Start()
    {
        // 정렬할 초기 배열 선언
        int[] arr = { 3, 5, 6, 9, 1, 2, 4, 11, 7 };
        
        // Bar 인스턴스 배열 생성
        Bar[] instanceArr = new Bar[arr.Length];
        for (var i = 0; i < arr.Length; i++)
        {
            // 각 막대 인스턴스 생성 및 초기화
            instanceArr[i] = Instantiate(barPrefab, transform);
            instanceArr[i].SetData(i);
            instanceArr[i]._data = arr[i];
        }
        
        // QuickSort 알고리즘 시작 (주석 처리된 버블 정렬 대신)
        StartCoroutine(QuickSort(instanceArr, 0, arr.Length - 1));
        
        // 정렬 후 각 요소 로그 출력 (디버깅용)
        foreach (var i in instanceArr)
        {
            Debug.Log(i._data);    
        }
    }
}