알고리즘)26.3.9

선형 정렬이 뭔지 잘 이해안가도 나중에 배울거니깐 [  p  ]
 
 
 
1선택,삽입,쉘, 구현 다시 ✅
 
2sort부모클래스 구현
 
3선택, 쉘, 삽입 장,단점

---

 
 

 

 
 
 
 

---

Comparable은 인터페이스입니다. 하지만 자바에서 인터페이스는 일종의 '추상적인 상위 타입' 역할
 
 
 

왜 Comparable[] a로 모든 타입을 다 받을 수 있나?

자바의 다형성 원리에 따라, 상위 타입(인터페이스)의 참조 변수는 하위 타입(구현 클래스)의 객체를 가리킬 수 있습니다.

• String은 Comparable을 구현했으므로, **String은 일종의 Comparable**이기도 합니다. (String is-a Comparable)
• 따라서 Comparable[] a라는 배열 안에는 String 객체 배열도 들어올 수 있고, Integer 객체 배열도 들어올 수 있는 것입니다.

 

1. 최상위 (규격): Comparable (인터페이스)
   • "모든 정렬할 데이터는 compareTo 메소드를 가지고 있어야 한다"는 규칙을 정의합니다.
2. 공통 도구함: AbstractSort (추상 클래스)
   • less(Comparable v, Comparable w): "v가 w보다 작니?" (내부적으로 v.compareTo(w) < 0 호출)
   • exch(Comparable[] a, int i, int j): "배열의 i번째와 j번째를 바꿔라."
   • 이 클래스는 정렬 알고리즘들이 공통적으로 쓰는 칼, 가위 같은 도구를 미리 만들어 둔 곳입니다.
3. 실제 정렬 구현: Selection, Insertion, Shell (구체 클래스)
   • AbstractSort를 상속(extends) 받습니다.
   • 핵심: sort(Comparable[] a) 메소드 딱 하나만 만듭니다.
   • 이 메소드 하나로 String[], Integer[], Double[]을 다 처리합니다. 왜? 모두 Comparable[] 타입으로 간주할 수 있기 때문입니다.

 
 
정렬을 할 때마다 객체를 생성하면 메모리가 낭비됩니다. static으로 만들면 프로그램 시작 시 메모리에 딱 한 번 올라가서 어디서든 편하게 호출해 쓸 수 있습니다.
 
static 안에서의 제약: static 메소드 안에서는 클래스의 일반 변수(인스턴스 변수)를 직접 쓸 수 없습니다. 오직 파라미터로 넘어온 값(Comparable[] a 등)이나 다른 static 변수만 다룰 수 있습니다.
Selection s = new Selection(); s.sort(data);라고 안 하고, 그냥 **Selection.sort(data);**라고 깔끔하게 한 줄로 쓰는 것입니다.
 
 
 

왜  AbstractSort를 상속?

이 구조의 핵심은 sort(): 스태틱 메소드 를 오버라이딩하려는 것이 아니라, less()와 exch() 같은 '도구'를 물려받아 쓰기 위해서입니다.
 
 
static 메소드이기 때문에 자식 클래스에서 sort를 구현하는 것은 사실상 부모의 sort와는 별개의, 이름만 같은 메소드를 자식 클래스에 새로 만드는 것과 같습니다.
 
 
 
 
 
 

 
 
 

 
 
 
 
 
 
 

 
 
 
(아무튼 거리만큼뺴면 된다는거_)

 
 
일반 삽입정렬 코드에서 j-1이었던거 생각해보면

 
 

//얘도 젤 끝에서 시작하는게 아니라, i는 처음부터인데,
// 그 i에 대해서, 비교할떄 거꿀로 올라가는거네<< 그래서 내부를 위해서 내부 반복문이 사용되는거네
//아 그래서 이중반복문이니깐, n**2 시간복잡도가 나오는거고 (선택정렬처럼)

//h-sort하기전, 그 기반이 되는 삽입정렬코드를 보면

for (int i = 1; i < a.length; i++) {
    for (int j =i; j >0 && less(a[j],a[j-1]); j--) {
        exch(a,j,j-1);
    }
}

 
 
 
(사소한 부분)

 

 
 
 
쉘정렬은, 삽입정렬의 외부반복문을, 
while h작아지면서 점점...1로 작아지는것으로만 감싸면 
 
 
 
 
 

 
 
 
 

 
 
 
 

ㅇㅇ
h식이 
3*h+1이니깐
 
 
 

    for (int j = i; 1번 j >0 && less(a[j],a[j-h]); j--  2번) {
        exch(a,j,j-h);
    }
}

내부반복문도 수정해야
 
 
 
 
 

---

 
while(h >= 1) 루프 마지막에 **h = h / 3;**을 넣어주어야 
쉘
 
 
 
1자리에 h넣으면 되는건가": 맞습니다. 셸 정렬은 삽입 정렬을 h간격으로 수행하는 것이므로, 기존 삽입 정렬의 간격 1을 h로 치환하면 됩니다.
 
 
 
 
 
 
선택정렬

• "둘다 가나다일때 멤버변수 정렬되있던거 바뀌는거": 이를 Stable(안정성) 여부라고 합니다. 선택 정렬은 서로 떨어져 있는 원소를 교환(exch)하기 때문에 Unstable(불안정) 정렬에 속합니다. 즉, 값이 같은 원소들의 상대적인 순서가 바뀔 수 있습니다.

 
 
 
 
Insertion Sort (삽입 정렬)

• "뭐랑 뭐랑 바꾸는거지": 현재 선택된 원소(a[j])와 그 이전 원소(a[j-num])를 비교하여 정렬 순서가 맞지 않으면 계속해서 앞으로 보내며 교환합니다

(그 기준 i일떄에 대하여)
 
 
 
 
 
사실 삽입정렬에서 내부반복문에서 j>0인데 j>=1인거랑 같
 
 
 
 
 
 

외곽 루프: 왜 i < n - 1인가? (i < n으로 해도 되나?)

이유: 마지막 하나는 비교할 대상이 없기 때문입니다.