Sort

004 처리

010

012

 

 

001 (Radix sort) 

// 001 
// target 값만 남기기
(F[i] / jarisu) % 10;

// target 자릿수를 1에 위치시키고(target보다 작은 앞 값 삭제)
// 10보다 큰 뒤 값을 삭제시킴으로서 해당 값만 남긴다

 

 

002

// 002
// bucket에 값을 집어넣는게 아닌, 특수값 count로 집어넣는다
for (int i = 0; i < F.length; i++) {
    bucket[(F[i] / jarisu) % 10]++;
}

 

 

003

// 003
// 배열을 합 배열 형태로 변경
for (int i = 1; i < 10; i++) {
    bucket[i] += bucket[i-1];
}

 

004

// bucket에서 빼면서 정렬
// output 배열에 저장하기
for (int i = F.length-1; i >= 0; i--) {
    output[bucket[(F[i] / jarisu % 10) - 1]] = F[i];
    bucket[(F[i] / jarisu) % 10]--;
}

 

 

005

// output에 data 저장하고, 다음 자릿수로 이동
for (int i = 0; i < F.length; i++) {
    F[i] = output[i];
}
jarisu = jarisu*10;
count++;

> Field 데이터를 직접적으로 사용하면서도, 그 데이터값을 사용해서 변경될 때, 새 Box 사용

 

 

006 

// OSC
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < C; i++) {
    bw.write(F[i] + "\n");
}
bw.flush();
bw.close();

> 줄바꿈

> flush와 close 해줄 것

 

 

007

// L2 ~
F = new int[C];
for (int i = 0; i < C; i++) {
    F[i] = Integer.parseInt(br.readLine());
}
br.close();

> Reader도 닫아줘야 함

 

 

-

 

008 (quickSort)

public static void quickSort(int[] F, int S, int E, int T) {
    if (S < E) {
        int pivot = partition(F, S ,E);
        if (pivot == T)
            return;
        else if (T < pivot)
            quickSort(F, S, pivot - 1, T);
        else
            quickSort(F, pivot + 1, E, T);
    }
}

> T번째 값은 0부터 시작하므로 index로 T-1 을 참조해서 외부 모듈로 보내지만, 해당 모듈 안의 T는 data flow 용으로 사용되는 것이므로 헷갈리지 않도록 한다

> 전체 quick sort를 수행하는 것이 아닌, T를 찾는 것이므로, if 체로 pivot 왼쪽 오른쪽 구간을 나눠 진입하는 것

> if (S < E)는 :  

 

 

009

// EM 2 : partition
public static int partition(int[] F, int S, int E) {

    if (S + 1 == E) {
        if (F[S] > F[E])
            swap (F, S ,E);
        return E;
    }
    
    int M = (S + E) / 2;
    swap (F, S, M);
    int pivot = F[S];
    int i = S + 1, j = E;
    
    while (i <= j) {
        while (pivot < F[j] && j > 0) {
            j--;
        }
        while (pivot > F[i] && i < F.length - 1) {
            i++;
        }
        if (i <= j) {
            swap (F, i++, j--);
        }
    }

    F[S] = F[j];
    F[j] = pivot;
    return j;
}

> 미들값을 산정하여 진행하는 통상 시행 전에, 언제나 예외 처리 파이프라인을 둔다(주로 끝이나 시작에서 나타남)

 

 

010

// Exceptional Pipeline
if (S + 1 == E) {
    if (F[S] > F[E])
        swap (F, S ,E);
    return E;

> 왜 피벗으로 E를 리턴하는지?

 

 

011

// Pre
int M = (S + E) / 2;
swap (F, S, M);
int pivot = F[S];
int i = S + 1, j = E;

> quicksort 준비 시, pivot을 중간값으로 하지만 while문의 커서 이동의 편리를 위해 시작값이랑 교환한다(i = S+1);

> pivot value는 F[M] 으로 먼저 계산하지 않고, S와 M을 swap한 후 값을 받는다'

 

 

012

// quicksorting & pivot cursor return
while (i <= j) {
    while (pivot < F[j] && j > 0) {
        j--;
    }
    while (pivot > F[i] && i < F.length - 1) {
        i++;
    }
    if (i <= j) {
        swap (F, i++, j--);
    }
}

F[S] = F[j];
F[j] = pivot;
return j;

> 커서 이동 조건으로 pivot과의 비교 + "양 끝에 도달하지 않았다는 것" 을 전제로 한다

> 이 때 양 끝에 도달하는 게 아닌, (0 + 1) + (Capacity보다 한칸 작게) 락을 걸어 마지막 이동을 남겨둔다

> while문에서 exit 되었다는 건, 커서 조건을 충족시키는 상황에서, j에서 피벗보다 작은 게 발견되었다는 뜻이다

> 왜 i와 j 스왑이 아닌 i++와 j-- 스왑인가?

> 결국 i와 j는 만난다

> pivot 커서를 리턴하는 것

 

 

-

 

013 (Merge Sort 1)

// EP
// 최소 피스를 2로 잡는다
if (e - s < 1)
    return;

> EP

> 최소 피스는 2

 

 

014

// Pre > 피스 준비하기 위해 recursive
int m = s + (e - s) / 2;
merge_sort(s, m);
merge_sort(m+1, e);

> 미들값을 (e - s) / 2; 인 경우는 맨 처음 왼쪽 조각일떄 뿐

> 나머지는 시작값에서 더 움직여줘야 하므로 앞에 s+를 추가한다

> 조각들이 최솟값으로 다 분해되면, 두개씩 정렬되어 다음 현재 단계로 올라옴

 

 

015

// 복제해서 Field에 바로 갱신
for (int i = s; i <= e; i++) {
    dp[i] = F[i];
}

> Field 값을 바로 사용하기에 혼선이 올 때(값 swap 등으로), 복제하여 바로 원래 Field에 덮어 씌움

 

 

016

// Merging
int k = s;
int p1 = s;
int p2 = m+1;
while (p1 <= m && p2 <= e) {
    if (dp[p1] > dp[p2]) {
        F[k] = dp[p2];
        k++;
        p2++;
    } else {
        F[k] = dp[p1];
        k++;
        p1++;
    }
}

> 총 4개의 필드를 사용

> value를 사용하기 위한 dp[]

> 재귀 후 리턴된 왼쪽(s~m) + 오른쪽(m+1 ~ e) // 커서만 사용, 결국 변경되는 것은 F[] 뿐이다

> 최종 완성본을 담을 F[] 

> 왼쪽에서 오른쪽으로 p와 k 커서가 1:1로 움직이면서 F에 작성됨

 

 

017

while (p1 <= m) {
    F[k] = dp[p1];
    k++;
    p1++;
}
while (p2 <= e) {
    F[k] = dp[p2];
    k++;
    p2++;
}

> 하나가 끝에 도달했다면, 나머지도 몰아서 작성(소진)

 

 

018(merge 2)

while (p1 <= m && p2 < e) {
    if (dp[p1] > dp[p2]) {
        F[k] = dp[p2];
        marker += p2 - k;
        k++;
        p2++;
    } else {
        F[k] = dp[p1];
        k++;
        p1++;
    }
}

> 다른 내용은 merge 1번과 다 동일하나, bubble이 일어날 때마다

> 즉, 오름차순으로 정렬하기 위해, 오른쪽이 더 클때 마킹이 따라옴

> bubble은 한칸 단위로 일어나지만, 병합은 그 이상 쭉 당겨오는 거기 때문에 당겨온 인덱스의 차이만큼 마킹해준다

 

 

-

 

019(bubble sort1)

// i == Shrinker
for (int i = 0; i < C-1; i++) {
    
    // j == 버블 가동 범위
    for (int j = 0; j < C-1-i; j++) {
        if (F[j] > F[j+1]) {
            int cont = F[j];
            F[j] = F[j+1];
            F[j+1] = cont;
        }
    }
}

> (if로 phaser를 커버) bubble을 가동한다는 것은 언제나 두가지 가동이 들어간다 : swap함, swap하지 않음

> 오름차순으로 exit할 때

> 왼쪽에서 오른쪽으로 시행할 때 max값이 맨 오른쪽으로 몰리기에, 맨 오른쪽이 정렬완료가 쌓임(오른쪽에서 -1씩 shrink)

> 반대로 내림차순일 때 오른쪽에서 왼쪽으로 작은값을 찾아 swap, 맨 왼쪽이 정렬완료가 쌓임(왼쪽에서 +1씩 shrink)

 

 

020(bubble 2)

// L2~
mData[] F = new mData[C];
for (int i = 0; i < C; i++) {
    F[i] = new mData(Integer.parseInt(br.readLine()), i);
}
Arrays.sort(F);

> value 기준 정렬을 사용하기 위해 i - value 쌍이 아닌, i - value, i 쌍을 사용한다

> Wrapper를 바깥이 아닌, value값에 넣어야 함에 주의

 

 

021

class mData implements Comparable<mData> {
    int value;
    int index;

    public mData(int value, int index) {
        super();
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(mData o) {
        return this.value - o.value;
    }
}

> 접근제어자 없이 바로 class

> Comarable<> 상속

> super();

> compareTo(mData o) 로 오름차순 정렬 가능하게 하기

 

 

022

// Comparing
int max = 0;
for (int i = 0; i < C; i++) {
    if (max < F[i].index - i)
        max = F[i].index - i;
}

// OEC
System.out.println(max+1);

> 논지 : 정렬 전 정렬 후 index가 최대로 차이나면 정렬이 완료

> 이 index는 안쪽 for문이 몇번 일어났는지에 관한 것

> 거기다 change가 한번도 일어나지 않음을 확인하기 위해 한번 더 사이클을 돌려야 함으로, max+1 출력

 

 

023 (selection)

// Setup
int[] F = new int[line.length()];
for (int i = 0; i < line.length(); i++) {
    F[i] = Integer.parseInt(line.substring(i, i+1));
}

substring 

 

024

// Selection sort
for (int i = 0; i < line.length(); i++) {
    int max = i;
    for (int j = i+1; j < line.length(); j++) {
        if (F[j] > F[max])
            max = j;
    }
    if (F[i] < F[max]) {
        int cont = F[i];
        F[i] = F[max];
        F[max] = cont;
    }
}

> i+1 ~ 나머지에서 Max를 고르고, i와 비교하면 됨

> 추가적으로 생각해 볼 수 있는 경우의 수 4가지 : 오름차순인데 max로, 오름차순인데 min으로, 내림차순인데 max로, 내림인데 min으로

 

 

025 (Insertion)

 

// Insertion
for (int i = 1; i < C; i++) {

    int cursor = i;
    int value = F[i];

    // cursor
    for (int j = i-1; j <= 0; j--) {
        if (F[i] > F[j]) {
            cursor = j+1;
            break;
        }
        if (j == 0) {
            cursor = 0;
        }
    }
    for (int j = i; j > cursor; j--) {
        F[j] = F[j-1];
    }
    F[cursor] = value;
    
    }