알고리즘 )1주차 퀴즈 준비_코드( 26.3.20)

AbstractSort 클래스[  ]

 

병합: 왜제자리 정렬이라는거지 [  ]

 

성능개선 부분이랑[  ]

 

시간복잡도들

 

 

else if(less(aux[j],aux[i])){

aux에서 비교

---

 

 

C[A[(i/exp)%10]]++ 부분에서 인덱스 i가 아니라 실제 값인 A[i]를 가져와야 합니다.

• 수정: C[(A[i] / exp) % 10]++

 

 

 

 

즉, B 배열에 값을 채울 때 뒤에서부터(n-1 -> 0) 루프를 돌려야 합니다. 현재처럼 앞에서부터 돌면 이전 자릿수에서 정렬된 순서가 뒤섞입니다.

• 수정: for (int i = n - 1; i >= 0; i--) { B[--C[(A[i] / exp) % 10]] = A[i]; }

 

 

 

 

 

while(exp <= maxValue) 대신 강의 자료의 로직대로라면 while(maxValue / exp > 0)

• 컴퓨터의 정수 나눗셈 특성을 이용한 것입니다.
  • 예: 179 / 1 = 179 (0보다 큼, 1의 자리 존재)
  • 예: 179 / 10 = 17 (0보다 큼, 10의 자리 존재)
  • 예: 179 / 100 = 1 (0보다 큼, 100의 자리 존재)
  • 예: 179 / 1000 = 0 (0임, 종료!)

 

 

이전 자릿수의 정렬 결과가 왜 계속 필요한가요?

이 부분이 기수 정렬(LSD 방식)의 가장 신기한 점입니다. **"낮은 자릿수에서 정렬된 순서가 유지되어야만, 높은 자릿수에서 값이 같을 때 전체 순서가 흐트러지지 않기 때문"**입니다.

 

 

 

 

(실수보소)

1. 누적 합 계산 (Prefix Sum) 부분

• 이미지: C[i] += C[i - 1]; (누적 합을 구함)
• 텍스트: C[i] = C[i - 1];
• 설명: +=가 아니라 =만 쓰게 되면 앞의 값을 그냥 덮어쓰게 되어 정렬 위치를 제대로 계산할 수 없습니다.

2. 인덱스 계산 부분 (가장 치명적인 오류)

• 이미지: B[--C[(A[i] / exp) % 10]] = A[i];
• 텍스트: B[ --C[(A[i]/exp)%exp] ]=A[i];
• 설명: 텍스트 코드의 마지막 부분에서 %10이 아니라 %exp라고 적혀 있습니다. 특정 자릿수의 숫자(0~9)를 가져오려면 항상 **% 10**을 해야 합니다.

 

 

 

// [Page 18] 계수 정렬 //return값이 있네 

return B; //기수에서는 B값을 계속 A에 업데이트 햇지만
//계수정렬은 그걸 딱한번만 하는거니깐

 

 

 

 

if(lo>=hi){ //hi도 인덱스라는걸 기억하면

sort(a,aux,0,a.length-1);

 

 

 

//뭐를 어디에다가 써줘야하지
for (int i = 0; i < a.length; i++) {
    //a[i]=aux[i]; 이건 말이 안되느ㄴ게 젤처음 시행일떄 aux 빈 배열인데
    aux[i]=a[i];
}

 

 

 

• 이미지: less(aux[j], aux[i])
• 작성 코드: less(a[j], a[i])
• 이유: merge 함수 내부의 반복문에서 a[k]에 계속해서 값을 새로 채워 넣고 있습니다. 이때 비교를 원본 데이터가 보존된 aux 배열이 아니라, 값이 바뀌고 있는 a 배열끼리 비교하게 되면 정렬 논리가 꼬이게 됩니다. 반드시 복사본인 aux를 비교해야 합니다.

 

 

 

• 이미지: for (int k = lo; k <= hi; k++) aux[k] = a[k];
• 작성 코드: for (int i = 0; i < a.length; i++) aux[i] = a[i];

 

 

 (원소가 1개이거나 없으면 멈춘다는 뜻) 질문하신 "왜 등호가 있어야 하나요?"에 대한 답은, lo == hi인 상황은 정렬할 원소가 딱 1개라는 뜻인데, 원소가 1개일 때는 더 이상 쪼갤 필요가 없으므로 바로 리턴해서 함수를 끝내야 하기 때문입니다.

 

 

 

 

public static void sort(Comparable[] a) {
    //d이떄는 top down이랑 다르게 왜 return해주지않았더라 
    //애초에 재귀구조가 아니고, 반복문 구조니깐, 음 그러면 swap은 sort부분에 있엇겟네 

 

 

System.arraycopy(src,0,a,0,N);

 

//근데 swap을 내부반복문에서 해줫던가 외부반복문에서 해줫던가
//내부지, 왜 merge< 두개 정렬해주니깐 <그래서 정렬된거 내놓으니깐 갱신해야해서

 

왜 Top-down과 달리 return이 없나요?

• Top-down(재귀): 재귀 방식에서는 문제를 더 이상 쪼갤 수 없을 때(배열의 크기가 1일 때) 함수를 종료해야 하므로 Base Case인 if (hi <= lo) return;이 반드시 필요합니다.
• Bottom-up(반복): 반복문 방식은 애초에 가장 작은 단위(크기 1)부터 시작해서 점점 키워나가는 방식입니다. for (int i = 1; i < N; i *= 2) 루프 조건 자체가 끝나는 시점을 제어하기 때문에 별도의 재귀 종료 조건(return)이 필요하지 않은 것입니다.

 

 

1. [성능 개선 1] 소규모 배열에서 삽입 정렬 사용 (Cutoff)

• 작성 코드: if(hi-lo<=7){ Selection.sort(a); }
• 문제점 1: Selection.sort(a)를 호출하면 배열 전체를 매번 정렬하게 됩니다. 현재 정렬 중인 범위인 lo부터 hi까지만 정렬하는 Insertion.sort(a, lo, hi)를 사용해야 합니다.
• 문제점 2: 정렬을 한 뒤에는 더 이상 재귀를 타지 않도록 **반드시 return;**을 해줘야 합니다. (이미지 노란색 박스 참고)
• 문제점 3: 보통 성능상 **Selection(선택)**보다는 Insertion(삽입) 정렬이 소규모 배열에서 더 빠르기 때문에 삽입 정렬을 권장합니다.

2. [성능 개선 2] 이미 정렬된 경우 병합 건너뛰기

• 작성 코드: merge 함수 내부 for문 안에 if(less(aux[lo],aux[mid+1])){ return; }
• 문제점 1 (위치): 이 체크는 merge 함수 안에서 반복문 돌 때마다 하는 것이 아니라, sort 함수에서 merge를 호출하기 직전에 한 번만 해야 효율적입니다. (merge조차 할필요없으니깐 )
• 문제점 2 (비교 대상): aux[lo]와 비교하는 것이 아니라, **앞부분의 끝(a[mid])**과 **뒷부분의 시작(a[mid+1])**을 비교해야 합니다. 앞부분의 가장 큰 놈이 뒷부분의 가장 작은 놈보다 작거나 같으면 이미 합쳐진 상태나 다름없기 때문입니다.

 

 

 

 

// ★성능 개선을 위해 새로 추가해야 할 범위 정렬 코드★
    public static void sort(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) { // lo+1부터 hi까지
            for (int j = i; j > lo && less(a[j], a[j-1]); j--) { // j가 lo보다 클 때까지만
                exch(a, j, j-1);
            }
        }
    }

 

 

 

hi 포함 여부 (i <= hi)

• 맞습니다. 병합 정렬(Merge Sort)에서 사용하는 hi는 보통 마지막 인덱스를 의미하기 때문에, 그 인덱스까지 정렬하려면 **<= hi**라고 써주는 것이 정확합니다.

 

 

cutoff 등호가 있으니깐 

 

 

 

 

a[k]=aux[j++];

 

복사를 해야했던 이유는 우리가 매번 뒤에있는걸 참고해서 앞에있는얘한테 썻는데 

 

 

 

 

 

1. 원래 방식 (바보 같은 방식)

방 A에 있는 책들을 정렬해서 다시 방 A에 꽂으려고 합니다.

1. 복사: 방 A의 책들을 일단 **임시 박스(AUX)**에 다 옮겨 담습니다. (시간 낭비!)
2. 정렬: 박스에 있는 책들을 하나씩 꺼내서 방 A의 책꽂이에 순서대로 꽂습니다.

• 문제: 매번 정렬할 때마다 **"박스로 옮기는 과정"**이 무조건 들어갑니다.

2. 성능 개선 방식 (핑퐁 방식)

우리에게 방 A와 방 B, 똑같은 방이 두 개 있다고 칩시다.
**"박스로 옮길 시간에, 그냥 옆 방으로 바로 정렬해서 꽂아버리자!"**는 생각입니다.

1. 1단계: 방 A에 있는 책들을 정렬하면서 방 B에 바로 꽂습니다. (복사 단계 생략!)
2. 2단계: 이제 방 B에 정렬된 책들이 있죠? 이걸 다시 정렬하면서 방 A에 바로 꽂습니다.
3. 결과: 왔다 갔다(핑퐁)만 하면 정렬이 끝납니다. **"임시 박스에 옮겨 담는 시간"**이 아예 사라집니다.

 

 

sort(dst, src) : "src에 있는 재료를 써서, 정렬된 결과를 dst에 담아라!"

 

 

 

왜 sort와 merge의 매개변수 순서가 다른가?

• merge(aux, a, ...) 의 의미:
  • 코드를 보면 a[k] = aux[i++]; 라고 되어 있죠?
  • 즉, aux(재료)에서 읽어서 a(결과창고)에 담겠다는 뜻입니다.
  • 그래서 이미지의 merge는 (재료, 결과창고) 순서입니다.
• sort(a, aux, ...) 의 의미:
  • 이 함수의 목표는 **"최종 결과를 a에 담는 것"**입니다.
  • 그래서 (결과창고, 재료) 순서로 이름을 붙인 것입니다.

 

 

 

 

 

"결과창고(Destination)를 먼저 써라."

이 알고리즘에서 sort 함수의 정의(Definition)는 다음과 같은 약속입니다.

sort(A, B)의 약속: "함수가 끝나면 결과는 A에 들어있어야 한다."

(성능개선 전에도 sort 서순은 a먼저이긴함)

 

 

 

 

 

왜 merge는 순서가 (aux, a)인가요? (시험용 핵심)

이미지 속 merge 함수의 구현부를 다시 보세요.
a[k] = aux[i++]; (즉, aux에서 꺼내서 a에 넣는다.)

• 보통 merge 함수는 merge(src, dst) 즉, (재료, 결과) 순서로 정의합니다.
• 우리가 sort(a, aux)라고 불렀을 때, 우리의 최종 목적지는 **a**입니다.
• 그러니까 마지막에 부르는 merge는 당연히 (재료: aux, 결과: a) 순서가 되어야만 합니다.

 

 

 

 

 

merge(a, aux, lo, mid, hi);

성능개선하기전에는 

merge에서 일일이 복사된 aux보면서 a에 썻는데 

 

 

1. [이미지 1] 기본 버전: merge(a, aux)

• 약속: 1번 자리(a)가 결과창고다!
• 논리:
  1. 일단 1번(a)에 있는 데이터를 2번(aux)에 복사한다.
  2. 복사본(aux)을 보고 정렬해서 다시 1번(a)에 채운다.
• 그래서: sort(a, aux) 호출 → 자식도 sort(a, aux) → merge(a, aux) 순서로 순서가 일정합니다.

---

2. [이미지 2] 성능 개선 버전: merge(aux, a)

• 약속: 2번 자리(a)가 결과창고다! (Source -> Destination 구조)
• 논리:
  1. (복사 안 함) 1번(aux)은 이미 자식들이 정렬을 다 끝낸 재료다.
  2. 재료(aux)를 합쳐서 2번(a)에 바로 병합한다.
• 그래서: 이 버전은 **"어디서 읽어서 어디에 쓰느냐"**를 명확히 하려고 merge(재료, 결과) 순서로 이름을 바꾼 것입니다.

 

 

 

• 기본 버전의 철학: "나는 무조건 a가 주인공이야. aux는 그냥 거들 뿐이야." (그래서 a를 앞에 둠)
• 개선 버전의 철학: "'재료' 배열과 '결과' 배열의 역할을 명확히 나누자. (핑퐁을 해야 하니까!)"

 

 

 merge(aux, a) 순서로 호출하는 이유는 딱 하나입니다.

**"내 자식들이 정렬된 결과물을 aux에다가 다 차려놓았기 때문"**입니다.

 

 

 

sort(a, aux, ...) 함수의 목표

이 함수의 목표는 명확합니다. **"결과물을 a 배열에 담는 것

(이게 왜 결과물인지는, merge함수 참고)

 

 

 

 

2. 자식들에게 시키는 일 (역할 교대)

내가 a에 결과를 담으려면, 재료가 되는 두 덩어리(왼쪽, 오른쪽)가 반대편 배열인 aux에 정렬되어 있어야 합니다.

그래서 자식들에게 이렇게 시킵니다.

• sort(aux, a, lo, mid); -> "aux에다가 정렬해서 담아와!"
• sort(aux, a, mid+1, hi); -> "aux에다가 정렬해서 담아와!"

3. 자식들이 일을 마친 직후의 상태

자식들이 일을 완벽하게 끝냈습니다. 현재 상태는 이렇습니다.

• aux 배열: 왼쪽 덩어리 정렬 완료 / 오른쪽 덩어리 정렬 완료
• a 배열: (자식들이 재료로 쓰느라 휘저어 놓아서) 엉망진창인 상태

4. 마지막 단계: merge(aux, a)를 하는 이유

자, 이제 내가 마지막으로 두 덩어리를 합쳐서(Merge) **최종 목적지인 a**에 담아야 합니다.

• 지금 정렬된 재료들이 어디 있죠? **aux**에 있습니다.
• 내가 담아야 할 목적지는 어디죠? **a**입니다.
• 그러니까 당연히 merge(aux, a, ...) 순서로 호출해야 합니다!
  • (해석: aux에 있는 재료들을 합쳐서 a에다가 꽂아 넣어라!)

 

 

 

1. less 비교 대상 오류 (가장 중요)

• 작성 코드: else if(less(a[j], a[i]))
• 수정 사항: else if(less(aux[j], aux[i]))
• 이유: merge(aux, a, ...) 함수는 aux에 있는 데이터를 재료로 써서 a에 결과를 담는 함수입니다. 즉, 지금 정렬된 예쁜 데이터는 aux에 들어있으므로, 비교도 당연히 aux끼리 해야 합니다. a는 지금 값이 채워지고 있는 '빈 그릇' 상태라 a를 비교하면 안 됩니다.

2. 초기 복사 (System.arraycopy) 누락

• 질문하신 부분: public static void sort(Comparable[] a) 내부
• 수정 사항: sort를 시작하기 전에 a의 내용을 aux로 한 번 복사해줘야 합니다.

 

 

 

 

 

 

 

public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        // ★ 중요: 시작 전 딱 한 번 복사 (핑퐁의 전제조건)
        System.arraycopy(a, 0, aux, 0, a.length);

아 선언만 하면 안되고 

(지금은 모든 원소가 0이니깐 )