알고리즘) 병합정렬 구현

쉘,기수, 계수정렬<구현[   ]check만 

 

제자리 병합인가[  ]

 

구현할떄 매개변수도[  ]

 

 

int[] C = new int[K]
K :0부터K아니었나 

 

 

 

경곗값처리[  ]

if (lo >= hi) {
    //등호는 왜있어야하는거지
    return;
}
int mid=(lo+hi)/2;
//+1해줘야하나 <경곗값처리 모르겟음

---

 

제자리 병합(In-place merge)'**이란, 추가적인 메모리 공간(별도의 배열)을 사용하지 않고 원래 데이터가 담겨 있는 배열 안에서 요소들의 위치를 바꾸어 가며 병합을 완료하는 방식을 의미합니다.

 

 

 왜 배열을 두 개(a, aux)나 받나요?

• a[]: 실제로 데이터가 들어있고, 최종적으로 정렬된 결과를 담을 "진짜" 배열입니다.
• aux[]: 병합을 하기 위해 잠시 데이터를 옮겨놓는 **"임시 작업실(보조 배열)"**입니다.

병합 정렬은 두 편으로 나뉜 데이터를 비교해서 순서대로 하나씩 뽑아내는 방식입니다. 그런데 만약 임시 배열(aux) 없이 원래 배열(a)에서 바로 자리를 바꾸려고 하면, 아직 비교도 안 한 뒷부분의 데이터가 덮어씌워져서 사라질 위험이 있습니다. 그래서 안전하게 원본 데이터를 복사해둘 공간이 따로 필요한 것입니다.

 

 

• 비교는 백업본(aux)을 보고 합니다.
• 결정된 순서대로 담는 것은 원본(a)에 합니다.

 

두 배열은 서로 다른 객체인가요? (메모리 구조)

네, 서로 다른 객체입니다.

• a와 aux는 메모리의 서로 다른 주소에 위치한 별개의 배열 객체입니다.
• aux[k] = a[k]를 한다고 해서 두 배열이 하나가 되는 것이 아닙니다. a[k]에 들어있는 '값'(또는 객체의 주소)을 aux[k]라는 별도의 공간에 복사해서 넣는 것뿐입니다.

 

 

 

 

먼소리지[   ]

왜 함수 인자로 aux를 같이 넘겨줄까요?

보통 병합 정렬은 재귀적으로 수없이 많이 호출됩니다.

• 함수가 실행될 때마다 내부에서 new Comparable[n] 처럼 임시 배열을 새로 만들면, 메모리를 계속 할당하고 해제하느라 컴퓨터가 너무 힘들어합니다(성능 저하).
• 그래서 처음에 딱 한 번만 큰 임시 배열(aux)을 만들어두고, 모든 merge 함수들이 이 배열을 "공용 작업대"처럼 같이 쓰도록 인자로 계속 넘겨주는 방식을 주로 사용합니다.

 

 

 

 

 

 

 

 

참조 변수는 객체를 가리키는(가지는) 이름표

 

 

 

aux[k] = a[k]
aux = a;

 

C언어에서 배열 이름(arr1)은 배열의 첫 번째 요소를 가리키는 **'상수 포인터'**와 같습니다. 그래서 주소값을 마음대로 바꿀 수 없기 때문에 arr1 = arr2 같은 대입이 불가능합니다.

하지만 자바에서 배열 변수(arr1, arr2)는 **'참조 변수(리모컨)'**입니다.

• 자바의 배열 변수는 "어떤 배열 객체를 가리킬 것인가?"를 담는 유연한 변수입니다.
• 따라서 arr1 = arr2;를 하면, arr1이라는 리모컨이 원래 가리키던 {1, 2, 3, 4}를 버리고, arr2가 가리키는 {5, 4, 3, 2}를 똑같이 가리키게 됩니다.
• 결과: 이제 arr1과 arr2는 똑같은 하나의 배열 객체를 가리킵니다.

 

(아 복제할때 for문 돌았엇구나, 하긴 [k]가 뭔가 했는데 )

 

 

 

 

 

각 메소드의 역할

① public static void sort(Comparable[] a) : [공장 입구 / 안내데스크]

• 역할: 외부 사용자가 정렬을 시작할 때 사용하는 **API(입구)**입니다.
• 특징: 사용자는 그냥 배열 a만 던져주면 됩니다. 인덱스(lo, hi)나 임시 공간(aux) 같은 복잡한 내부 사정은 여기서 알아서 준비합니다.
• 하는 일: 정렬에 꼭 필요한 임시 작업대(aux)를 딱 한 번 생성하고, 본격적인 정렬을 시키는 내부 메소드를 호출합니다.

② private static void sort(a, aux, lo, hi) : [설계도 / 작업 지시서]

• 역할: 배열을 반으로 쪼개고 또 쪼개는 재귀(Recursion) 엔진입니다.
• 하는 일:
  1. 배열이 1칸이 될 때까지 계속 반으로 나눕니다. (Divide)
  2. 왼쪽 반을 정렬시키고, 오른쪽 반을 정렬시킵니다. (Conquer)
  3. 다 쪼개졌으면 아래의 merge를 불러서 다시 합칩니다. (Combine)

③ private static void merge(a, aux, lo, mid, hi) : [조립실 / 실제 노동]

• 역할: 쪼개진 두 덩어리를 순서대로 비교해서 하나로 합치는 진짜 일꾼입니다.
• 하는 일: 이전 질문에서 본 것처럼 aux에 백업해두고, a에다가 작은 순서대로 차곡차곡 쌓아서 정렬을 완성합니다.

 

 

 

병합 정렬은 재귀 함수입니다. 100만 개를 정렬하면 merge 함수는 약 100만 번 가까이 호출됩니다.

• 메모리 할당 폭탄: merge가 호출될 때마다 new Comparable[...]이 실행됩니다. 컴퓨터는 100만 번이나 메모리에서 빈 공간을 찾아서 "여기 배열 하나 만들어줘!"라는 요청을 처리해야 합니다.

 

 

 

 

"한 번에 다 정렬하는 것도 아닌데, 커다란 aux 배열을 계속 통째로 들고 다니는 게 정말 괜찮나?"라는 의문이 드시는군요.

이게 가능한 이유는 "인덱스(lo, hi)라는 안전장치" 덕분입니다. 

 

 

 

aux는 큰 도화지지만, lo와 hi만큼의 구역만 씁니다.

merge 함수 안의 첫 번째 코드를 다시 보세요.
for (int k = lo; k <= hi; k++) aux[k] = a[k];

• 포인트: aux 배열의 전체를 복사하는 게 아니라, **지금 딱 합치려고 하는 구역(lo부터 hi까지)**만 a에서 aux로 복사합니다.
• 만약 지금 lo=4, hi=7 구역을 정렬 중이라면, aux 배열의 4, 5, 6, 7번 칸만 건드립니다. 나머지 0~3번 칸이나 8번 이상의 칸에 뭐가 들어있는지는 전혀 신경 쓰지 않고, 건드리지도 않습니다.

 

 

어차피 백업본만드는데 이걸 왜 sort에서 안하고 merge에서 하냐고

 

sort에서 복사하면 데이터가 '옛날 데이터'라서 정렬이 안 됩니다.

 

 

 

왜 sort 시작할 때 복사하면 안 되는가? 

사용자님 말씀대로 sort 시작할 때 복사를 한다고 가정해봅시다.

• 단계 1: sort(0, 3) 시작하자마자 복사함.
  • 이때 a는 [4, 2, 3, 1] (엉망)
  • aux도 [4, 2, 3, 1] (엉망) ← 이 시점에 복사됨
• 단계 2: sort(0, 1)이 실행되어 a 배열의 앞부분을 [2, 4]로 정렬함.
  • 현재 a: [2, 4, 3, 1]
• 단계 3: sort(2, 3)이 실행되어 a 배열의 뒷부분을 [1, 3]로 정렬함.
  • 현재 a: [2, 4, 1, 3] (자, 이제 왼쪽/오른쪽 조각은 정렬됐죠?)
• 단계 4: 이제 merge(0, 1, 3)를 하려고 aux를 딱 열었는데!
  • 대참사: aux는 아까 단계 1에서 복사해둔 [4, 2, 3, 1](정렬 안 된 옛날 거) 그대로임!
  • 왜냐하면 단계 2, 3에서 a만 고쳤지, aux는 안 건드렸으니까요.

 

(sort함수가 해주는 역할을 제대로 파악못했엇던는듯)

 

(sort: 쪼개는데

쪼개면 내부적으로 재귀있어서 merge가 있기떄문에 정렬됨)

 

 

 

 

1

for (int k = lo; k <= hi; k++) aux[k] = a[k];

// aux[] 배열에 a[]의 내용을 일단 복사

(aux에 정렬하는게 아니라, a(원본 배열에 정렬하는거네 ))

 

2

사용자 api sort에는 새로운 배열 생성해줘야 

 

 

3

분할 정렬(sort)이 끝난 후(재귀이후), 두 부분을 합치는 merge(a, aux, lo, mid, hi); 과정이 반드시 들어가야 합니다.

 

 

4

// [질문 답변] 젤 처음에 return이 필요한 이유

<우리가 알고있는 정보중, 매개변수를 이용하네 

 

 

 

5

왜 mid가 첫번째 구간의 끝이냐 

 

sort(a,aux,lo,mid);
//아 재귀함수호출할떄, 첫번째 재귀의 끝이  mid가 되어야하니깐,

무한 루프 방지 (Progress toward Base Case)

재귀 함수가 멈추려면, 쪼개진 문제의 크기가 반드시 원래보다 작아져야 합니다.

• 가정: 만약 mid를 두 번째 부분의 시작으로 설정해서 [lo, mid-1]과 [mid, hi]라고 나눈다고 해봅시다.
• 문제 상황: 원소가 2개 남았을 때 (lo=0, hi=1)
  • mid = (0 + 1) / 2 = 0 (정수 나눗셈은 내림됨)
  • 첫 번째 부분: [0, -1] (범위 오류)
  • 두 번째 부분: [0, 1] (원래 크기랑 똑같음!)
• 결과적으로 원소가 2개일 때 계속해서 자기 자신과 똑같은 크기로 쪼개려다가 **StackOverflow(무한 루프)**가 발생합니다.
• 반면, **[lo, mid]와 [mid+1, hi]**로 나누면 [0, 0]과 [1, 1]로 깔끔하게 1개씩 쪼개지며 종료 조건에 도달합니다.

 

 

 

 

 

 

 

 

 

 

 

 

6

 

 

 

 

//i,j가 왜필요하더라<움직여야하니깐<그러면 lo,mid,hi는 안움직인다는 의미
//얼마만큼 반복해야하나 <원소갯수만큼, 
// 
// 그러면 i,j어떻게 분리하지, <매개변수있잖아

 

// 전체를 순회아님 0~a.length아님

 

 

for (int k = lo; k <= hi; k++) {
    //등호들어가나

 

(어떻게 약속하느냐에 따라 다른거겟지만..)

 

 

 

sort(a, aux, 0, a.length - 1); //호출할때도 매개변수에 어떤값을 넣을지가 중요할지도

 

 

aux가 뭘 의미하는 거지?"

• aux는 **Auxiliary(보조)**의 약자입니다. 병합 정렬은 두 그룹을 비교해서 정렬된 결과를 만들어낼 때 임시로 데이터를 담아둘 공간이 필요합니다. 원본 배열(a)의 값을 잠시 복사해두고, 값을 비교하며 다시 a에 차곡차곡 정렬해서 넣기 위한 임시 저장소라고 생각하시면 됩니

 

 

 

//반복문 두개 범위 똑같네
for (int k = lo; k <=hi ; k++) {
    if(i>mid){
        a[k]=aux[j++];
    }
    else if (j>hi) {
        a[k]=aux[i++];
    }
    else if (less(aux[j],aux[i])) {
        a[k]=aux[j++];
        //왜 먼저대입이더라, 아 그렇겟구

 

 

sort(a,aux,0,a.length-1); //젤 큰 재귀 sort는 0~마지막 인덱스까지니깐 

 

 

 

 

 

 

---

for (int i = 0; i < A.length; i++) {
    C[ A[i] ]+=1; //C는 갯수에 대한거니깐, 전위연산 
}

 

//여기서 안헷갈리려고 변수 n만든거였구나
//인덱스 0~n-1
for (int i = n-1; i >=0; i--) {

 

 

 

❌ 틀린 부분 (누락된 부분)

각 자릿수 정렬(Counting Sort)이 끝날 때마다 그 결과를 A 배열에 반영해주어야, 다음 자릿수(10의 자리, 100의 자리 등)를 정렬할 때 이전 정렬 상태가 유지됩니다. 이 과정이 없으면 A 배열은 항상 처음 상태 그대로여서 정렬이 이루어지지 않습니다

 

 

 

 

            // ⭐ [추가된 부분] 임시 배열 B의 내용을 원본 배열 A에 복사
            for (int i = 0; i < n; i++) {
                A[i] = B[i];
            }

 

(살짝 병합정렬에도 필요했던 부분이긴햇음)