알고리즘) 1장

 

 

 

 

1. 쉘 정렬과 간격 h의 관계

왜 h가 크면 정렬이 거의 안 되는 것처럼 보일까요?

1. 부분 리스트의 크기 축소
   • h가 크다는 것은 데이터를 아주 넓은 간격으로 띄엄띄엄 선택한다는 뜻입니다.
   • 전체 데이터가 10개인데 h가 7이라면, 한 그룹에 속하는 원소는 고작 1~2개뿐입니다.
   • 원소가 1개면 정렬할 필요가 없고, 2개면 단 한 번의 비교와 교환(Exchange)으로 끝납니다.
2. 교환 횟수의 감소
   • 질문하신 대로 리스트(부분 리스트)의 크기가 작기 때문에 교환 연산 횟수 자체가 매우 적어집니다.
   • 이 단계에서는 전체적인 정렬이 이루어지는 것이 아니라, 멀리 떨어져 있는 큰 값과 작은 값을 대략적인 위치로 빠르게 보내는 데 집중합니다.
3. h의 역할
   • 초기 단계(큰 h): 멀리 떨어진 원소들을 크게 이동시켜 전체적인 불균형을 해소합니다.
   • 후기 단계(작은 h): 간격을 좁혀가며 세밀하게 정렬합니다.
   • 마지막 단계(h=1): 사실상 삽입 정렬과 같지만, 이미 앞 단계에서 어느 정도 정렬이 된 상태라 매우 빠르게 끝납니다.

---

2. 정렬 알고리즘의 두 가지 흐름

비교 기반 정렬 vs 선형 정렬

1. 비교 기반 정렬 (Comparison Sort)
   • 특징: 데이터가 무엇인지 몰라도 두 값을 비교한 결과만으로 정렬합니다.
   • 성능: 이론적으로 O(n log n)보다 빨라질 수 없는 한계가 있습니다.
   • 예시: 퀵 정렬, 병합 정렬, 힙 정렬, 삽입 정렬 등
2. 선형 정렬 (Linear Sort)
   • 특징: 데이터의 값 범위나 자릿수 같은 사전 정보(제약 조건)가 있을 때만 사용 가능합니다.
   • 성능: 비교를 하지 않고 값을 특정 바구니에 담는 방식을 사용하여 O(n)의 속도를 낼 수 있습니다.
   • 예시: 계수 정렬(Counting Sort), 기수 정렬(Radix Sort)

---

요약 및 결론

1. 쉘 정렬은 삽입 정렬의 "가까운 것끼리만 비교하는 단점"을 h라는 간격을 도입해 해결한 방식입니다.
2. h가 클 때는 교환 횟수가 적어 정렬이 덜 된 것처럼 보이지만, 사실은 무거운 원소를 먼 거리에 한 번에 보내는 효율적인 작업을 수행 중인 것입니다.
3. 일반적인 상황에서는 비교 기반인 O(n log n) 알고리즘을 쓰지만, 데이터의 특성을 미리 안다면 제약 조건을 활용해 O(n)의 선형 정렬을 사용하는 것이 가장 빠릅니다.

 

 

 

 

 

[25, 10, 4, 18, 50, 5, 2, 8, 33, 11, 7, 22]

두개씩 저장할때 정렬을 한다음에 저장

[10, 25]

 

 

 

 

File 1: [10, 25], [5, 50], [11, 33] (런 3개)

 

 

*Sorting Phase(정렬 단계)

**"뒤죽박죽인 전체 데이터를 메모리에 들어갈 만큼만 쪼개서, 일단 그 안에서만 정렬해 두는 단계

 

 

 

 

이전 방식은 파일을 합친 후(File 3), 다시 나누는(File 1, 2) 작업이 필요했죠?

이 방식은 File 1, 2를 합쳐서 결과를 번갈아가며 File 3, 4에 바로 나눠 담습니다.

그다음 판에는 File 3, 4가 입력이 되고, 합쳐서 다시 File 1, 2에 담습니다.

 

 

 

 

이름들 

 

 

1500 vs 1500이 가능했던 이유

*"디스크에서 읽어오기 때문"

 

 

 

앞서 배운 'Balanced' 방식은 입구 2개, 출구 2개처럼 딱딱 짝이 맞아야(Balanced) 재분배를 안 하고 속도가 빨랐죠? 그런데 Polyphase는 입구와 출구의 개수가 달라도 아주 머리를 잘 써서 재분배 과정을 없앤 방식입니다.
하지만 Polyphase는 일부러 피보나치 수열(1, 1, 2, 3, 5, 8...) 같은 숫자에 맞춰서 덩어리(Run) 개수를 다르게 나눠 담습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

힙이 아니네,

선택트리는  옆집 숫자가 뭔지 볼 필요 없이 자기 부모랑만 싸우며 올라가면 됩니다.

 

 

 

n

선택 트리로 하던, 일일이 비교하건,

데이터 갯수마큼은 항상 곱해줘야하나,ㅇㅇㅇ

 

 

r,k차이 

 

 

 

 

 

 

 

logk r== 1로 하면 단계수가 왜 2인거지, 

k==r

한번에 합칠갯수 == 런의 갯수 

 

 

 

 

 

 

 

 

 

48,49 해석

 

 

 

 

그림에서 숫자 3개가 들어가는 박스 하나를 **'블록(Block)'**이라고 부릅니다.

• 컴퓨터는 하드디스크에서 데이터를 가져올 때 숫자 1개씩 안 가져오고, **한 바구니(블록)**씩 통째로 가져옵니다.
• 이 그림에서는 **"1블록 = 숫자 3개"**라고 약속한 상황입니다. 그래서 모든 칸이 3개씩 묶여 있는 거예요

 

 

 

 

 

 

 

 

 

 

 

Maximum file size==n데이터 개수인가 

(f랑 n

 

 

 

성능 향상이지 r<=k여야하는데 r이 줄어들어서 ?

런 생성 

 

 

 '대체 선택(Replacement Selection)'을 쓰면 런(Run)들의 크기가 제각각이 됩니다. (어떤 건 크고, 어떤 건 작고...)

이 제각각인 런들을 합칠 때, 

 

어떤 순서로 합치느냐에 따라 디스크를 읽고 쓰는 총량이 달라집니다.

 

 

 

 

만약 공식에서 + N을 빼버리면 어떻게 될까요?
그건 **"각각 정리만 해두고, 하나로 합치는 힘은 전혀 쓰지 않았다"**는 뜻이 됩니다. 합치지 않으면 한 줄로 정렬된 카드를 가질 수 없겠죠? 그래서 꼭 더해줘야 하는 힘이랍니다.

 

 

o(n)=o(n/2)+o(n/2)+N인데 이 o(n/2)에도 n/2가 더해질거 아니야

각 층에서 카드를 합치느라 쓴 힘의 총합을 구해보면, 어느 층이든 신기하게 항상 전체 카드 개수 4(N)로 똑같습니다

>그래서 NlogN

 

 

 

 

전체 카드 개수()가 아니라, 딱 절반 크기()의 작은 보조 책상만 가지고도 카드 정렬(병합)을 끝마칠 수 있을까?"

ㅇㅇㅇ

 

왜 이게 가능할까요?
사람들이 자리를 이동할 때마다, 원래 서 있던 자리가 '새로운 빈자리'로 변하기 때문입니다.
마치 도미노처럼 앞사람이 채워지면 뒷자리가 비고, 그 빈자리에 다음 사람을 세우는 과정이 딱딱 맞아떨어집니다.

 

 

 

sort 함수를 위에서 두 번 호출한 것은 "각각 정렬을 끝마쳐 놓아라" 하고 일을 맡긴 것이기 때문에, 그 아랫줄로 내려왔을 때는 이미 두 부분집합이 완벽하게 정렬된 상태가 보장된 상태 

 

 

 

//결국 안에서는 바깥의 상황은 모르겟고 , aux는 보조니깐, 결과물은 a에 담고싶어하나 ?

aux,a방향 헷갈릴때