유니티(다익스트라 알고리즘, 정렬 - 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬) _ 멋쟁이사자처럼 유니티 부트캠프 후기 40회차

[40회차 수업 내용] 250714

 

1. 다익스트라 알고리즘

2. 선택 정렬

3. 삽입 정렬

4. 버블 정렬

5. 퀵 정렬

 

 

0. 그래프의 이해

0.1. 그래프(Graph)란?

우선, 그래프는 노드(Node 또는 Vertex, 정점)와 간선(Edge, 변)으로 구성된 자료구조

• 노드(Node): 점이나 동그라미로 표현되는 개체(예: 도시, 사람, 웹페이지)
• 간선(Edge): 두 노드 사이의 연결을 나타내는 선 (예: 도시 간 도로, 친구 관계, 웹페이지 간 링크)

 

0.2. 가중치(Weight)란?

• 가중치는 간선에 부여된 숫자 값
• 이 숫자는 해당 간선을 통과하는 데 드는 비용, 거리, 시간, 용량 등 다양한 의미를 가질 수 있습니다.

 

 

1. 다익스트라(Dijkstra) 알고리즘

• 특정 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘
• 간선의 가중치가 모두 양수일 때만 정확하게 최단 경로를 보장

using UnityEngine;

public class DijkstraSearch : MonoBehaviour
{
    // 가중치가 있는 그래프를 인접 행렬로 표현 (6x6)
    // 0은 연결 안됨, 0이 아닌 값은 간선의 가중치(거리)
    private int[,] nodes = new int[6, 6]
    {
       // 0  1  2  3  4  5
        { 0, 1, 2, 0, 4, 0 }, // 0번 노드
        { 1, 0, 0, 0, 0, 8 }, // 1번 노드
        { 2, 0, 0, 3, 0, 0 }, // 2번 노드
        { 0, 0, 3, 0, 0, 0 }, // 3번 노드
        { 4, 0, 0, 0, 0, 2 }, // 4번 노드
        { 0, 8, 0, 0, 2, 0 }, // 5번 노드
    };

    void Start()
    {
        int start = 0; // 시작 노드 설정
        int[] dist;    // 시작점부터 각 노드까지의 최단 거리 저장 배열
        int[] prev;    // 각 노드로 가는 최단 경로의 이전 노드 저장 배열
        
        // 0번부터 다익스트라 알고리즘 수행
        Dijkstra(start, out dist, out prev);

        // Dijkstra 함수가 완료되면, 각 노드까지의 최단 거리와 경로를 Debug.Log로 출력
        for (int i = 0; i < nodes.GetLength(0); i++)
            Debug.Log($"{start}에서 {i}까지 최단 거리 : {dist[i]}, 경로 : {GetPath(i, prev)}");
    }

    // 다익스트라 최단 경로 알고리즘 구현
    private void Dijkstra(int start, out int[] dist, out int[] prev)
    { 
  
        int n = nodes.GetLength(0); // 노드 개수 (6)
        dist = new int[n];          // 최단 거리 배열
        prev = new int[n];          // 이전 노드 배열
        bool[] visited = new bool[n]; // 방문 체크 배열

        // 초기화: 모든 거리는 무한대(최대값)로, 이전 노드는 -1(없음), 방문 안함
        for (int i = 0; i < n; i++)
        {
            dist[i] = int.MaxValue;  // 모든 노드까지의 거리를 '무한대'로 설정 (아직 모르므로)
            prev[i] = -1; // 모든 노드의 이전 노드를 '-1'로 설정 
            // 어떤 노드도 '이전 노드'로 지정되지 않았음, 어떤 노드도 '이전 노드'로 지정되지 않았음
          
          visited[i] = false; //모든 노드가 아직 방문되지 않았음
            
             /// 왜 '무한대로 설정?'
            ///거리 갱신의 원리: 다익스트라 알고리즘은 노드를 방문하면서 거리를 갱신할 때 
            ///새로운 경로의 거리가 현재까지 알려진 거리보다 짧으면 갱신한다는 비교 로직을 사용하기 떄문
        }

        dist[start] = 0; // 시작 노드까지 거리는 0
        
        
        

        // 메인 루프 - n 번 반복 루프
        // 아직 방문하지 않은 노드 중에서 시작점으로부터 가장 가까운 노드를 찾아내고, 
        // 그 노드까지의 최단 거리를 확정, 그 노드를 통해 다른 노드들의 거리를 갱신
        
        for (int cnt = 0; cnt < n; cnt++)
        {
            int u = -1;            // 현재 단계에서 최단 거리로 '확정'할 노드 (인덱스)
            int min = int.MaxValue; // 현재 최단 거리 값
            
            // 가장 가까운 미방문 노드 찾기
            for (int j = 0; j < n; j++)
            {
                if (!visited[j] && dist[j] < min)
                {
                    min = dist[j];
                    u = j;
                }
            }

            // 더 이상 방문할 노드가 없으면 종료
            if (u == -1)
                break;

            visited[u] = true; // 선택한 노드 방문 처리

            // 선택한 노드와 연결된 노드들의 거리 갱신 시도
            for (int k = 0; k < n; k++)
            {
                // 간선이 있고 방문하지 않은 노드일 때
                if (nodes[u, k] > 0 && !visited[k])
                {
                    int newDist = dist[u] + nodes[u, k]; // 현재 노드를 경유하는 거리 계산
                    if (newDist < dist[k]) // 더 짧으면 갱신
                    {
                        dist[k] = newDist;
                        prev[k] = u; // 이전 노드 갱신
                    }
                }
            }
        }
    }

    // 특정 노드까지의 경로를 재귀적으로 문자열로 생성하는 함수
    private string GetPath(int end, int[] prev)
    {
        if (prev[end] == -1)
            return end.ToString(); // 시작 노드거나 경로 없음

        // 이전 노드 경로 + 현재 노드
        return $"{GetPath(prev[end], prev)} -> {end.ToString()}";
    }
}

 

//출력값

0에서 0까지 최단 거리 : 0, 경로 : 0

0에서 1까지 최단 거리 : 1, 경로 : 0 -> 1

0에서 2까지 최단 거리 : 2, 경로 : 0 -> 2

0에서 3까지 최단 거리 : 5, 경로 : 0 -> 2 -> 3

0에서 4까지 최단 거리 : 4, 경로 : 0 -> 4

0에서 5까지 최단 거리 : 6, 경로 : 0 -> 4 -> 5

 

 

Start() 메서드 실행

1. int start = 0; : 시작 노드를 0번으로 설정합니다.
2. Dijkstra(start, out dist, out prev); : 0번 노드부터 다익스트라 알고리즘을 시작합니다.
3. for 루프 : Dijkstra 함수가 완료되면, 각 노드까지의 최단 거리와 경로를 Debug.Log로 출력합니다.

---

Dijkstra(int start, out int[] dist, out int[] prev) 메서드 실행 (start = 0)

초기 상태 설정:

• n = 6 (노드 개수)
• dist = [Max, Max, Max, Max, Max, Max] (모든 거리 무한대)
• prev = [-1, -1, -1, -1, -1, -1] (모든 이전 노드 없음)
• visited = [F, F, F, F, F, F] (모든 노드 방문 안 함)
• dist[start] = 0; : 시작 노드 0번까지의 거리는 0으로 설정합니다.
  • dist: [0, Max, Max, Max, Max, Max]

---

메인 루프: for (int cnt = 0; cnt < n; cnt++) (총 6번 반복될 수 있음)

이 루프는 각 반복마다 **"아직 방문하지 않은 노드 중에서 시작점으로부터 가장 가까운 노드"**를 찾아내고, 그 노드까지의 최단 거리를 확정합니다. 그리고 그 노드를 통해 다른 노드들의 거리를 갱신합니다.

---

Cnt 0 (첫 번째 반복): 0번 노드의 최단 거리 확정

1. u와 min 초기화:
   • u = -1 (확정할 노드)
   • min = int.MaxValue (확정할 노드의 거리)
2. 가장 가까운 미방문 노드 찾기 (for (int j = 0; j < n; j++)):
   • j = 0: !visited[0]은 true이고, dist[0] (0)은 min (Max)보다 작습니다.
     • min = 0
     • u = 0
   • j = 1~5: dist[j]는 모두 Max이므로 min (0)보다 작지 않습니다.
   • 결과: u = 0, min = 0 (즉, 0번 노드가 현재까지 가장 가까운 미방문 노드)
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[0] = true;
   • visited: [T, F, F, F, F, F]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 0.
   • k = 0: nodes[0, 0]은 0. if 조건 불만족.
   • k = 1: nodes[0, 1]은 1 (>0). !visited[1]은 true. 조건 만족.
     • newDist = dist[0] + nodes[0, 1] = 0 + 1 = 1
     • newDist (1) < dist[1] (Max) 이므로 갱신.
     • dist[1] = 1
     • prev[1] = 0
   • k = 2: nodes[0, 2]은 2 (>0). !visited[2]은 true. 조건 만족.
     • newDist = dist[0] + nodes[0, 2] = 0 + 2 = 2
     • newDist (2) < dist[2] (Max) 이므로 갱신.
     • dist[2] = 2
     • prev[2] = 0
   • k = 3: nodes[0, 3]은 0. if 조건 불만족 (연결 안 됨).
   • k = 4: nodes[0, 4]은 4 (>0). !visited[4]은 true. 조건 만족.
     • newDist = dist[0] + nodes[0, 4] = 0 + 4 = 4
     • newDist (4) < dist[4] (Max) 이므로 갱신.
     • dist[4] = 4
     • prev[4] = 0
   • k = 5: nodes[0, 5]은 0. if 조건 불만족 (연결 안 됨).

Cnt 0 종료 시 상태:

• dist: [0, 1, 2, Max, 4, Max]
• prev: [-1, 0, 0, -1, 0, -1]
• visited: [T, F, F, F, F, F]

---

Cnt 1 (두 번째 반복): 1번 노드의 최단 거리 확정

1. u와 min 초기화: u = -1, min = Max
2. 가장 가까운 미방문 노드 찾기:
   • j = 0: visited[0]이 T이므로 스킵.
   • j = 1: !visited[1]은 true, dist[1] (1)은 min (Max)보다 작습니다.
     • min = 1
     • u = 1
   • j = 2: !visited[2]은 true, dist[2] (2)은 min (1)보다 크므로 u와 min 갱신 안 함.
   • j = 3: !visited[3]은 true, dist[3] (Max)은 min (1)보다 크므로 갱신 안 함.
   • j = 4: !visited[4]은 true, dist[4] (4)은 min (1)보다 크므로 갱신 안 함.
   • j = 5: !visited[5]은 true, dist[5] (Max)은 min (1)보다 크므로 갱신 안 함.
   • 결과: u = 1, min = 1
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[1] = true;
   • visited: [T, T, F, F, F, F]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 1.
   • k = 0: nodes[1, 0]은 1 (>0). !visited[0]은 false. 조건 불만족 (이미 방문).
   • k = 1~4: nodes[1, k]가 0이거나 이미 방문.
   • k = 5: nodes[1, 5]은 8 (>0). !visited[5]은 true. 조건 만족.
     • newDist = dist[1] + nodes[1, 5] = 1 + 8 = 9
     • newDist (9) < dist[5] (Max) 이므로 갱신.
     • dist[5] = 9
     • prev[5] = 1

Cnt 1 종료 시 상태:

• dist: [0, 1, 2, Max, 4, 9]
• prev: [-1, 0, 0, -1, 0, 1]
• visited: [T, T, F, F, F, F]

---

Cnt 2 (세 번째 반복): 2번 노드의 최단 거리 확정

1. u와 min 초기화: u = -1, min = Max
2. 가장 가까운 미방문 노드 찾기:
   • j = 0, 1: visited이 T이므로 스킵.
   • j = 2: !visited[2]은 true, dist[2] (2)은 min (Max)보다 작습니다.
     • min = 2
     • u = 2
   • j = 3: dist[3] (Max)은 min (2)보다 크므로 갱신 안 함.
   • j = 4: dist[4] (4)은 min (2)보다 크므로 갱신 안 함.
   • j = 5: dist[5] (9)은 min (2)보다 크므로 갱신 안 함.
   • 결과: u = 2, min = 2
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[2] = true;
   • visited: [T, T, T, F, F, F]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 2.
   • k = 0: nodes[2, 0]은 2 (>0). !visited[0]은 false. 조건 불만족.
   • k = 1: nodes[2, 1]은 0. 조건 불만족.
   • k = 3: nodes[2, 3]은 3 (>0). !visited[3]은 true. 조건 만족.
     • newDist = dist[2] + nodes[2, 3] = 2 + 3 = 5
     • newDist (5) < dist[3] (Max) 이므로 갱신.
     • dist[3] = 5
     • prev[3] = 2
   • 나머지 k는 연결 없거나 이미 방문.

Cnt 2 종료 시 상태:

• dist: [0, 1, 2, 5, 4, 9]
• prev: [-1, 0, 0, 2, 0, 1]
• visited: [T, T, T, F, F, F]

---

Cnt 3 (네 번째 반복): 4번 노드의 최단 거리 확정

1. u와 min 초기화: u = -1, min = Max
2. 가장 가까운 미방문 노드 찾기:
   • j = 0, 1, 2: visited이 T이므로 스킵.
   • j = 3: !visited[3]은 true, dist[3] (5)은 min (Max)보다 작습니다. min = 5, u = 3.
   • j = 4: !visited[4]은 true, dist[4] (4)은 min (5)보다 작습니다.
     • min = 4
     • u = 4
   • j = 5: dist[5] (9)은 min (4)보다 크므로 갱신 안 함.
   • 결과: u = 4, min = 4
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[4] = true;
   • visited: [T, T, T, F, T, F]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 4.
   • k = 0: nodes[4, 0]은 4 (>0). !visited[0]은 false. 조건 불만족.
   • k = 1~3: 연결 없거나 이미 방문.
   • k = 5: nodes[4, 5]은 2 (>0). !visited[5]은 true. 조건 만족.
     • newDist = dist[4] + nodes[4, 5] = 4 + 2 = 6
     • newDist (6) < dist[5] (9) 이므로 갱신.
     • dist[5] = 6
     • prev[5] = 4

Cnt 3 종료 시 상태:

• dist: [0, 1, 2, 5, 4, 6]
• prev: [-1, 0, 0, 2, 0, 4]
• visited: [T, T, T, F, T, F]

---

Cnt 4 (다섯 번째 반복): 3번 노드의 최단 거리 확정

1. u와 min 초기화: u = -1, min = Max
2. 가장 가까운 미방문 노드 찾기:
   • j = 0, 1, 2, 4: visited이 T이므로 스킵.
   • j = 3: !visited[3]은 true, dist[3] (5)은 min (Max)보다 작습니다.
     • min = 5
     • u = 3
   • j = 5: dist[5] (6)은 min (5)보다 크므로 갱신 안 함.
   • 결과: u = 3, min = 5
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[3] = true;
   • visited: [T, T, T, T, T, F]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 3.
   • k = 2: nodes[3, 2]은 3 (>0). !visited[2]은 false. 조건 불만족.
   • 나머지 k는 연결 없거나 이미 방문. (아무것도 갱신되지 않음)

Cnt 4 종료 시 상태:

• dist: [0, 1, 2, 5, 4, 6]
• prev: [-1, 0, 0, 2, 0, 4]
• visited: [T, T, T, T, T, F]

---

Cnt 5 (여섯 번째 반복): 5번 노드의 최단 거리 확정

1. u와 min 초기화: u = -1, min = Max
2. 가장 가까운 미방문 노드 찾기:
   • j = 0, 1, 2, 3, 4: visited이 T이므로 스킵.
   • j = 5: !visited[5]은 true, dist[5] (6)은 min (Max)보다 작습니다.
     • min = 6
     • u = 5
   • 결과: u = 5, min = 6
3. 종료 조건 확인: u는 -1이 아니므로 계속 진행.
4. 노드 u 방문 처리:
   • visited[5] = true;
   • visited: [T, T, T, T, T, T]
5. 이웃 노드 거리 갱신 (for (int k = 0; k < n; k++)):
   • 현재 노드 u = 5.
   • k = 1: nodes[5, 1]은 8 (>0). !visited[1]은 false. 조건 불만족.
   • k = 4: nodes[5, 4]은 2 (>0). !visited[4]은 false. 조건 불만족.
   • 나머지 k는 연결 없거나 이미 방문. (아무것도 갱신되지 않음)

Cnt 5 종료 시 상태:

• dist: [0, 1, 2, 5, 4, 6]
• prev: [-1, 0, 0, 2, 0, 4]
• visited: [T, T, T, T, T, T]

---

메인 루프 종료

cnt가 5가 되어 for 루프(for (int cnt = 0; cnt < n; cnt++))가 종료됩니다. 모든 노드의 최단 거리가 확정되었습니다.

---

Start() 메서드 마지막 부분 (Debug.Log 출력)

이제 dist와 prev 배열을 사용하여 결과를 출력합니다.

• dist: [0, 1, 2, 5, 4, 6]
• prev: [-1, 0, 0, 2, 0, 4]

for (int i = 0; i < nodes.GetLength(0); i++) 루프가 실행됩니다.

1. i = 0:
   • GetPath(0, prev): prev[0]은 -1이므로 "0" 반환.
   • 출력: 0에서 0까지 최단 거리 : 0, 경로 : 0
2. i = 1:
   • GetPath(1, prev): prev[1]은 0. GetPath(0, prev) -> "0" 반환. 최종: "0 -> 1"
   • 출력: 0에서 1까지 최단 거리 : 1, 경로 : 0 -> 1
3. i = 2:
   • GetPath(2, prev): prev[2]은 0. GetPath(0, prev) -> "0" 반환. 최종: "0 -> 2"
   • 출력: 0에서 2까지 최단 거리 : 2, 경로 : 0 -> 2
4. i = 3:
   • GetPath(3, prev): prev[3]은 2. GetPath(2, prev) 호출.
     • GetPath(2, prev): prev[2]은 0. GetPath(0, prev) 호출.
       • GetPath(0, prev): prev[0]은 -1. "0" 반환.
     • "0 -> 2" 반환.
   • "0 -> 2 -> 3" 반환.
   • 출력: 0에서 3까지 최단 거리 : 5, 경로 : 0 -> 2 -> 3
5. i = 4:
   • GetPath(4, prev): prev[4]은 0. GetPath(0, prev) -> "0" 반환. 최종: "0 -> 4"
   • 출력: 0에서 4까지 최단 거리 : 4, 경로 : 0 -> 4
6. i = 5:
   • GetPath(5, prev): prev[5]은 4. GetPath(4, prev) 호출.
     • GetPath(4, prev): prev[4]은 0. GetPath(0, prev) 호출.
       • GetPath(0, prev): prev[0]은 -1. "0" 반환.
     • "0 -> 4" 반환.
   • "0 -> 4 -> 5" 반환.
   • 출력: 0에서 5까지 최단 거리 : 6, 경로 : 0 -> 4 -> 5

       0   1   2   3   4   5
   0: { 0,  1,  2,  0,  4,  0 }  // 0-1(1), 0-2(2), 0-4(4)
   1: { 1,  0,  0,  0,  0,  8 }  // 1-0(1), 1-5(8)
   2: { 2,  0,  0,  3,  0,  0 }  // 2-0(2), 2-3(3)
   3: { 0,  0,  3,  0,  0,  0 }  // 3-2(3)
   4: { 4,  0,  0,  0,  0,  2 }  // 4-0(4), 4-5(2)
   5: { 0,  8,  0,  0,  2,  0 }  // 5-1(8), 5-4(2)

 

 

2. 선택 정렬 O(n²)

:주어진 배열에서 가장 작은(또는 가장 큰) 요소를 찾아 첫 번째 위치의 요소와 교환하고,

그다음 나머지 배열에서 가장 작은(또는 가장 큰) 요소를 찾아 두 번째 위치의 요소와 교환하는 과정을 반복

 

using UnityEngine;

public class SelectionSort : MonoBehaviour
{
    // 정렬할 배열
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };

    void Start()
    {
        // 정렬 전 배열 출력
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        // 선택 정렬 실행
        Selection(array);

        // 정렬 후 배열 출력
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }
    
    // 선택 정렬 메소드
    private void Selection(int[] arr)
    {
        int n = arr.Length; // 배열 길이
        
        // 배열의 처음부터 끝까지 반복 (마지막 원소 제외)
        for (int i = 0; i < n - 1; i++) // i: 현재 선택된 위치
        {
            int minIdx = i; // 최소값의 인덱스를 현재 i로 초기화
            
            // i 이후의 원소들 중에서 최소값 찾기
            for (int j = i + 1; j < n; j++) // j: 비교 대상 인덱스
            {
                if (arr[j] < arr[minIdx]) // 현재 최소값보다 더 작은 값이 있으면
                    minIdx = j; // 최소값 인덱스 갱신
            }

            // 최소값을 현재 위치(i)와 교환
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

 

3. 삽입 정렬 O(n²)

: 이미 정렬된 부분 배열에 새로운 값을 올바른 위치에 "삽입"해서 정렬을 완성하는 알고리즘

 

 

using UnityEngine;

public class InsertionSort : MonoBehaviour
{
    // 정렬할 배열 선언
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };
    
    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));


        Insertion(array);
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Insertion(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n; i++)
        {
            int key = arr[i];    // 현재 삽입할 원소 = key
            int j = i - 1;       // key의 왼쪽에 있는 바로 왼쪽 인덱스

            // key보다 큰 값들을 한 칸씩 오른쪽으로 이동
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];  // 값을 오른쪽으로 복사
                j--;                 // j--를 통해 다음 루프에서의 비교 대상을 왼쪽으로 이동! 
            }

            // key를 올바른 위치에 삽입
            arr[j + 1] = key; // -했으니까 올바른 위치는 +1 !!
        }
    }
}

총 비교 횟수 : 1 + 2 + 3 + ... + (n - 1) = >  n(n - 1)/2 => n^2

 

 

4. 버블 정렬 (Bubble Sort) → O(n²)

using UnityEngine;

public class BubbleSort : MonoBehaviour
{
 
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };
    
    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));
        Bubble(array);
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

 
    private void Bubble(int[] arr)
    {
        int n = arr.Length;

		 // 현재 회차에서 인접한 두 값을 비교하고 큰 값을 뒤로 보내는 (버블링) 반복문
          //n-1번 반복
        for (int i = 0; i < n - 1; i++)
        {
            // 내부 루프: 인접한 요소들을 비교하고 교환하여 가장 큰(오름차순 기준) 요소를 현재 탐색 범위의 끝으로 보냅니다.
            // 이미 정렬된 뒷부분(i만큼)은 비교 대상에서 제외합니다. (1번 하면 오른쪽에 1개의 요소 정렬. i+1개가 정렬됨) i=0 -> 1번
            for (int j = 0; j < n - i - 1; j++)
            {
                // 앞의 값이 뒤의 값보다 크면 서로 교환
                if (arr[j] > arr[j + 1])
                {
                    // 값 교환 (swap)
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

(n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 => n^2

 

 

5. 퀵 정렬 (Quick Sort) → O(nlogn)

: 퀵 정렬은 분할 정복(Divide and Conquer) 방식에 기반을 둔 정렬 알고리즘 

- 피봇 설정: 양쪽 끝 , 중앙값, 무작위 등

• 분할(Partition)
  : 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동. 피벗은 중간에 위치하도록 배치.
• 재귀 호출
  : 피벗 기준으로 나눠진 좌/우 부분 배열에 대해 다시 퀵정렬 수행.
• 종료 : 배열의 크기가 1 이하가 되면 재귀 종료 (더 이상 정렬 필요 없음).

 

 

 

using UnityEngine;

public class QuickSort : MonoBehaviour
{
    // 정렬할 배열 선언
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };
    
    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));
        Quick(array, 0, array.Length - 1); // left = 0 (배열의 시작 인덱스), right = array.Length - 1 (배열의 마지막 인덱스)
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    // 퀵 정렬 메소드
    // arr: 정렬할 배열
    // left: 현재 부분 배열의 시작 인덱스
    // right: 현재 부분 배열의 마지막 인덱스
    private void Quick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            // 피벗을 기준으로 배열을 두 부분으로 나누고
            int pivot = Partition(arr, left, right);
            
            // 피벗 기준 왼쪽 부분 재귀 호출
            Quick(arr, left, pivot - 1);
            // 피벗 기준 오른쪽 부분 재귀 호출
            Quick(arr, pivot + 1, right);
        }
    }

	// 배열을 피벗 기준으로 분할하고 피벗의 최종 위치를 반환하는 메소드 (Lomuto Partition Scheme)
    // arr: 분할할 배열
    // left: 분할할 부분 배열의 시작 인덱스
    // right: 분할할 부분 배열의 마지막 인덱스
    private int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];   // 맨 오른쪽 값을 피벗으로 선택
        int index = left - 1;     // 작은 값들의 마지막 인덱스

        // left부터 right-1까지 반복
        for (int i = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                index++;

                // arr[i]와 arr[index] 교환 (작은 값을 앞쪽으로 이동)
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }

        // 피벗을 index + 1 자리로 이동 (피벗의 최종 위치)
        int temp2 = arr[index + 1];
        arr[index + 1] = arr[right];
        arr[right] = temp2;

        // 피벗의 인덱스를 반환
        return index + 1;
    }
}

 

 

1. 분할(Partition) 작업: O(N) :과정에서 배열의 모든 요소를 정확히 한 번씩만 피벗과 비교하며 위치를 조정

2. 재귀적 호출 (Log N 단계): O(logN) : 배열을 대략 절반씩 나누어 재귀적으로 호출 : N→N/2→N/4→⋯→1= log2​N에 비럐

=> Nlogn
      

 

 

Partition 메서드의 목표는 다음과 같습니다:

1. 주어진 배열(또는 부분 배열) 범위 내에서 **피벗(Pivot)**을 하나 선택합니다.
2. 피벗보다 작은 값들은 피벗의 왼쪽에, 피벗보다 큰 값들은 피벗의 오른쪽에 오도록 배열 요소들을 재배치합니다.
3. 피벗이 최종적으로 자리 잡은 **인덱스(위치)**를 반환합니다.

예시 배열: arr = { 5, 2, 8, 1, 7, 3 } 여기서 left = 0, right = 5 (즉, 배열 전체를 대상으로 Partition을 수행한다고 가정해 봅시다.)

---

1단계: 피벗 선택 및 변수 초기화

C#

 

private int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];    // 피벗 선택: 가장 오른쪽 값 (arr[5] = 3)이 피벗이 됩니다.
    int index = left - 1;      // 작은 값들이 들어갈 영역의 마지막 인덱스 (초기: -1)
    // index는 피벗보다 작은 값들을 모으는 공간의 '경계' 역할을 합니다.
    // 처음에는 작은 값이 없으므로, 경계는 시작 지점(left)의 바로 왼쪽(-1)으로 설정합니다.

• pivot: arr[5]에 해당하는 **3**이 피벗으로 선택됩니다.
• index: left - 1이므로, **-1**로 초기화됩니다.

현재 배열 상태: [ 5, 2, 8, 1, 7, 3 ] ^ ^ left right (pivot = 3) index = -1

---

2단계: 배열 탐색 및 교환 (for 루프)

이제 left부터 right - 1 (즉, 인덱스 0부터 4까지)을 반복하면서 각 요소를 피벗과 비교합니다.

C#

 

    for (int i = left; i < right; i++) // i는 left(0)부터 right-1(4)까지
    {
        if (arr[i] < pivot) // 현재 요소 arr[i]가 피벗(3)보다 작으면
        {
            index++; // 작은 값 영역 경계를 한 칸 확장하고
            // arr[i]와 arr[index]를 교환 (작은 값을 index 위치로 이동)
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }

단계별 실행:

• i = 0: arr[0] = 5. 5 < 3 (거짓). 아무 일도 일어나지 않습니다.
  • 배열: [ 5, 2, 8, 1, 7, 3 ]
  • index = -1
• i = 1: arr[1] = 2. 2 < 3 (참).
  • index를 증가시킵니다: index는 **0**이 됩니다.
  • arr[1] (값 2)과 arr[0] (값 5)를 교환합니다.
    • temp = arr[1] (temp = 2)
    • arr[1] = arr[0] (arr[1] = 5)
    • arr[0] = temp (arr[0] = 2)
  • 배열: [ 2, 5, 8, 1, 7, 3 ]
  • index = 0 (이제 arr[0]까지는 피벗보다 작은 값들입니다)
• i = 2: arr[2] = 8. 8 < 3 (거짓). 아무 일도 일어나지 않습니다.
  • 배열: [ 2, 5, 8, 1, 7, 3 ]
  • index = 0
• i = 3: arr[3] = 1. 1 < 3 (참).
  • index를 증가시킵니다: index는 **1**이 됩니다.
  • arr[3] (값 1)과 arr[1] (값 5)를 교환합니다.
    • temp = arr[3] (temp = 1)
    • arr[3] = arr[1] (arr[3] = 5)
    • arr[1] = temp (arr[1] = 1)
  • 배열: [ 2, 1, 8, 5, 7, 3 ]
  • index = 1 (이제 arr[1]까지는 피벗보다 작은 값들입니다)
• i = 4: arr[4] = 7. 7 < 3 (거짓). 아무 일도 일어나지 않습니다.
  • 배열: [ 2, 1, 8, 5, 7, 3 ]
  • index = 1

for 루프가 종료되었습니다. 현재 배열 상태: [ 2, 1, 8, 5, 7, 3 ] ^ ^ 작은 값 영역 index = 1

---

3단계: 피벗의 최종 위치 확정 및 삽입

for 루프가 끝나면 index는 피벗보다 작은 값들이 모여 있는 영역의 마지막 인덱스를 가리킵니다. 이제 피벗을 이 작은 값들 바로 뒤에 삽입합니다.

C#

 

    // 피벗을 index + 1 자리로 이동 (피벗의 최종 위치)
    // arr[index + 1]과 arr[right]를 교환합니다.
    int temp2 = arr[index + 1]; // index+1 위치의 값 (arr[1+1] = arr[2] = 8)을 임시 저장
    arr[index + 1] = arr[right]; // 원래 피벗 값(arr[5] = 3)을 arr[2] 위치로 이동
    arr[right] = temp2;          // 임시 저장했던 값(8)을 원래 피벗 위치(arr[5])로 이동

    // 피벗의 인덱스를 반환
    return index + 1; // 피벗의 최종 인덱스 반환 (1 + 1 = 2)
}

• index = 1이므로, index + 1은 **2**가 됩니다.
• arr[2] (값 8)과 arr[5] (값 3, 즉 피벗)을 교환합니다.
  • temp2 = arr[2] (temp2 = 8)
  • arr[2] = arr[5] (arr[2] = 3)
  • arr[5] = temp2 (arr[5] = 8)

최종 배열 상태 (Partition 후): [ 2, 1, 3, 5, 7, 8 ]

• 반환되는 피벗의 인덱스는 **2**입니다.

---

결과

이제 Partition 메서드는 2를 반환합니다. Quick 메서드는 이 2를 기준으로 배열을 두 부분으로 나누어 재귀 호출합니다:

1. 왼쪽 부분: Quick(arr, 0, 1) (즉, {2, 1}을 정렬)
2. 오른쪽 부분: Quick(arr, 3, 5) (즉, {5, 7, 8}을 정렬)