[멋쟁이사자처럼 부트캠프 TIL 회고] 유니티 게임개발 3기 16일차 알고리즘(정렬)

Bubble Sort

• 인접한 두 인덱스를 비교하여 정렬이 필요한 경우 교환

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;
            }
        }
    }
}

 

Quick Sort

• 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
  순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

public void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        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];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            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;
}

Quick Sort 시각화

using System;
using System.Collections;
using System.Collections.Generic;
using TMPro;
using Unity.VisualScripting;
using UnityEditor;
using UnityEngine;
using Random = UnityEngine.Random;

public class SortExample : MonoBehaviour
{
    private const int arraySize = 10;
    
    public GameObject cubePrefab;
    public GameObject[] cubeArray;
    public Material mPivot;
    public Material mOnChanging;
    public Material mDefault;
    
    private int[] arr = new int[arraySize];
    public bool ok = false;
    private int pi = 0;
    IEnumerator QuickSort(int[] arr, int low, int high)
    {
        ResetColors();
        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));
        }
    }

    IEnumerator Partition(int[] arr, int low, int high)
    {
        int pivot = arr[high];
        SetPivotColor(high);
        int i = low - 1;
        for (int j = low; j < high; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                SetOnChangingColor(i,j);
                StartCoroutine(Swap(i, j));
                yield return new WaitUntil(() => ok);
                (arr[i], arr[j]) = (arr[j], arr[i]);
                (cubeArray[i], cubeArray[j]) = (cubeArray[j], cubeArray[i]);
                ResetColors();
            }
        }
        SetOnChangingColor(i+1,high);
        StartCoroutine(Swap(i+1, high));
        yield return new WaitUntil(() => ok);
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        (cubeArray[i+1], cubeArray[high]) = (cubeArray[high], cubeArray[i+1]);
        ResetColors();
        
        pi = i + 1;
    }
    
    IEnumerator Swap(int p1, int p2)
    {
        ok = false;
        float time = 0.0f;
        const float lerpTime = 0.5f;
        
        var target1 = cubeArray[p2].transform.position;
        var target2 = cubeArray[p1].transform.position;
        while (lerpTime >= time)
        {
            time += Time.deltaTime;
            cubeArray[p1].transform.position = 
                Vector3.Lerp(cubeArray[p1].transform.position, target1, time/lerpTime);
            cubeArray[p2].transform.position = 
                Vector3.Lerp(cubeArray[p2].transform.position, target2, time/lerpTime);
            yield return null;
        }
        ok = true;
    }

    private void SetPivotColor(int index)
    {
        cubeArray[index].GetComponentInChildren<MeshRenderer>().material = mPivot;
    }

    private void SetOnChangingColor(int i, int j)
    {
        cubeArray[i].GetComponentInChildren<MeshRenderer>().material = mOnChanging;
        cubeArray[j].GetComponentInChildren<MeshRenderer>().material = mOnChanging;
    }

    private void ResetColors()
    {
        for (var i = 0; i < cubeArray.Length; i++)
        {
            cubeArray[i].GetComponentInChildren<MeshRenderer>().material = mDefault;
        }
    }
    
    private void Start()
    {
        for (var i = 0; i < arraySize; i++)
        {
            arr[i] = Random.Range(0, 101);
        }
        //int[] arr = { 8, 2, 4, 10, 6, 7, 9, 1, 3, 5 };
        cubeArray = new GameObject[arr.Length];
        for (int i = 0; i < arr.Length; i++)
        {
            cubeArray[i] = Instantiate(cubePrefab, new Vector3(i-4.5f, 0, 0), Quaternion.identity);
            cubeArray[i].GetComponentInChildren<TextMeshPro>().text = arr[i].ToString();
        }
        
        StartCoroutine(QuickSort(arr, 0, arr.Length - 1));
    }
}