# ๋ณ‘ํ•ฉ ์ •๋ ฌ(Merge Sort)



ํ•ฉ๋ณ‘ ์ •๋ ฌ์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ, ๋ถ„ํ•  ์ •๋ณต ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด ๊ตฌํ˜„

๋ถ„ํ•  ์ •๋ณต์ด๋ž€?

ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ฌธ์ œ ๋‹จ์œ„๋กœ ์ชผ๊ฐœ๋ฉด์„œ ํ•ด๊ฒฐํ•ด๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹

๋น ๋ฅธ ์ •๋ ฌ๋กœ ๋ถ„๋ฅ˜๋˜๋ฉฐ, ํ€ต์†ŒํŠธ์™€ ํ•จ๊ป˜ ๋งŽ์ด ์–ธ๊ธ‰๋˜๋Š” ์ •๋ ฌ ๋ฐฉ์‹์ด๋‹ค.

ํ€ต์†ŒํŠธ์™€๋Š” ๋ฐ˜๋Œ€๋กœ ์•ˆ์ • ์ •๋ ฌ์— ์†ํ•จ

์‹œ๊ฐ„๋ณต์žก๋„

ํ‰๊ท  ์ตœ์„  ์ตœ์•…
ฮ˜(nlogn) ฮฉ(nlogn) O(nlogn)

์š”์†Œ๋ฅผ ์ชผ๊ฐ  ํ›„, ๋‹ค์‹œ ํ•ฉ๋ณ‘์‹œํ‚ค๋ฉด์„œ ์ •๋ ฌํ•ด๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹์œผ๋กœ, ์ชผ๊ฐœ๋Š” ๋ฐฉ์‹์€ ํ€ต์ •๋ ฌ๊ณผ ์œ ์‚ฌ

  • mergeSort
public void mergeSort(int[] array, int left, int right) {
    
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
    
}

์ •๋ ฌ ๋กœ์ง์— ์žˆ์–ด์„œ merge() ๋ฉ”์†Œ๋“œ๊ฐ€ ํ•ต์‹ฌ

ํ€ต์†ŒํŠธ์™€์˜ ์ฐจ์ด์ 

ํ€ต์ •๋ ฌ : ์šฐ์„  ํ”ผ๋ฒ—์„ ํ†ตํ•ด ์ •๋ ฌ(partition) โ†’ ์˜์—ญ์„ ์ชผ๊ฐฌ(quickSort)

ํ•ฉ๋ณ‘์ •๋ ฌ : ์˜์—ญ์„ ์ชผ๊ฐค ์ˆ˜ ์žˆ์„ ๋งŒํผ ์ชผ๊ฐฌ(mergeSort) โ†’ ์ •๋ ฌ(merge)

  • merge()
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

์ด๋ฏธ ํ•ฉ๋ณ‘์˜ ๋Œ€์ƒ์ด ๋˜๋Š” ๋‘ ์˜์—ญ์ด ๊ฐ ์˜์—ญ์— ๋Œ€ํ•ด์„œ ์ •๋ ฌ์ด ๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋‹จ์ˆœํžˆ ๋‘ ๋ฐฐ์—ด์„ ์ˆœ์ฐจ์ ์œผ๋กœ ๋น„๊ตํ•˜๋ฉด์„œ ์ •๋ ฌํ•  ์ˆ˜๊ฐ€ ์žˆ๋‹ค.

โ˜…โ˜…โ˜…ํ•ฉ๋ณ‘์ •๋ ฌ์€ ์ˆœ์ฐจ์ ์ธ ๋น„๊ต๋กœ ์ •๋ ฌ์„ ์ง„ํ–‰ํ•˜๋ฏ€๋กœ, LinkedList์˜ ์ •๋ ฌ์ด ํ•„์š”ํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋ฉด ํšจ์œจ์ ์ด๋‹ค.โ˜…โ˜…โ˜…

LinkedList๋ฅผ ํ€ต์ •๋ ฌ์„ ์‚ฌ์šฉํ•ด ์ •๋ ฌํ•˜๋ฉด?

์„ฑ๋Šฅ์ด ์ข‹์ง€ ์•Š์Œ

ํ€ต์ •๋ ฌ์€, ์ˆœ์ฐจ ์ ‘๊ทผ์ด ์•„๋‹Œ ์ž„์˜ ์ ‘๊ทผ์ด๊ธฐ ๋•Œ๋ฌธ

LinkedList๋Š” ์‚ฝ์ž…, ์‚ญ์ œ ์—ฐ์‚ฐ์—์„œ ์œ ์šฉํ•˜์ง€๋งŒ ์ ‘๊ทผ ์—ฐ์‚ฐ์—์„œ๋Š” ๋น„ํšจ์œจ์ ์ž„

๋”ฐ๋ผ์„œ ์ž„์˜๋กœ ์ ‘๊ทผํ•˜๋Š” ํ€ต์†ŒํŠธ๋ฅผ ํ™œ์šฉํ•˜๋ฉด ์˜ค๋ฒ„ํ—ค๋“œ ๋ฐœ์ƒ์ด ์ฆ๊ฐ€ํ•˜๊ฒŒ ๋จ

๋ฐฐ์—ด์€ ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•ด์„œ ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•˜์ง€๋งŒ, LinkedList๋Š” Head๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•ด์•ผ ํ•จ

๋ฐฐ์—ด[O(1)] vs LinkedList[O(n)]

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    mergeSort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
 
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}
 
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
 
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
 
    while (i < ll && j < rl) {
        if (L[i] <= R[j]) {
            array[k] = L[i++];
        } else {
            array[k] = R[j++];
        }
        k++;
    }
 
    while (i < ll) {
        array[k++] = L[i++];
    }
 
    while (j < rl) {
        array[k++] = R[j++];
    }
}
์ตœ์ข… ์ˆ˜์ • : 11/15/2021, 1:31:19 PM