Amenable 2023. 3. 12. 14:57

1. ์ •์˜ ๐Ÿ„โ€โ™‚๏ธ

 

ํž™ ์ •๋ ฌ

  ํž™์ •๋ ฌ์ด๋ž€ ์ž๋ฃŒ๊ตฌ์กฐ ํž™(Heap)์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•˜๋Š” ์ •๋ ฌ ๋ฐฉ์‹์ด๋‹ค. ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์ผ ๊ฒฝ์šฐ ์ตœ๋Œ€ํž™์„ ์ด์šฉํ•˜๊ณ  ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ์ผ ๊ฒฝ์šฐ ์ตœ์†Œํž™์„ ์ด์šฉํ•œ๋‹ค.

  ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด ํž™ ์ •๋ ฌ์€ ๋ฃจํŠธ๋…ธ๋“œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  ์ œ๊ฑฐ๋œ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๋ฐฐ์—ด์˜ ๋’ท๋ถ€๋ถ„๋ถ€ํ„ฐ ์ฑ„์›Œ ๋„ฃ์œผ๋ฉด์„œ ์ •๋ ฌ์ด ์ด๋ฃจ์–ด์ง€๋Š” ๊ฒƒ์ด๋‹ค.

 

2. ๋™์ž‘ ๋ฐฉ์‹ ๐Ÿšฃโ€โ™‚๏ธ

  ์ตœ๋Œ€ํž™์„ ์ด์šฉํ•˜์—ฌ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด ๋ณด์ž. ๊ฐ€์žฅ ์‰ฝ๊ฒŒ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋Š” ๋™์ž‘๋ฐฉ์‹์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  1. ์ •๋ ฌํ•ด์•ผ ํ•˜๋Š” ์›์†Œ๋“ค์„ ํ•˜๋‚˜์”ฉ ํž™์— ๋„ฃ์–ด์ค€๋‹ค.
  2. ์‚ญ์ œ๋ฅผ ํ•˜๋ฉด์„œ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ ธ์˜ค๊ณ  ๊ทธ๊ฒƒ์„ ๋ฐฐ์—ด์˜ ๋’ท๋ถ€๋ถ„๋ถ€ํ„ฐ ์ฑ„์šด๋‹ค.

  ์ด๋ ‡๊ฒŒ ํ•œ๋‹ค๋ฉด ๊ธฐ์กด ๋ฐฐ์—ด๋กœ๋ถ€ํ„ฐ ํž™์„ ๊ตฌ์„ฑํ•˜๋Š” ๋ฐฐ์—ด ํ•˜๋‚˜๋ฅผ ์ถ”๊ฐ€์ ์œผ๋กœ ๋งŒ๋“ค๊ณ (1๋ฒˆ ๊ณผ์ •), ๋’ท๋ถ€๋ถ„๋ถ€ํ„ฐ ์ •๋ ฌ๋œ ์›์†Œ๋“ค์„ ๋„ฃ์„ ๋ฐฐ์—ด์„ ํ•˜๋‚˜ ๋” ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค.(2๋ฒˆ ๊ณผ์ •) ๊ทธ๋Ÿฌ๋ฉด ์ด 2๊ฐœ์˜ ๋ฐฐ์—ด์„ ๋” ๋งŒ๋“ค์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค.

  ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๊ธฐ์กด์˜ ๋ฐฐ์—ด์—์„œ ๋ฐ”๋กœ ์ •๋ ฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ์‹์„ ์•Œ์•„๋ณด์ž. ์ด ๋ฐฉ์‹์€ Heapify ์—ฐ์‚ฐ์„ ์ด์šฉํ•˜์—ฌ ์ถ”๊ฐ€ ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜์ง€ ์•Š๊ณ  ์ •๋ ฌํ•œ๋‹ค. Heapify๋ž€ ํž™ ์ƒ์„ฑ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๋‘ ์ž์‹ ๋…ธ๋“œ ์ค‘ ํฌ๊ธฐ๊ฐ€ ๋” ํฐ ์ž์‹์„ ๋ถ€๋ชจ์™€ ๋ฐ”๊พธ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋™์ž‘ ๋ฐฉ์‹์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  1. ์ตœ๋Œ€ ํž™์„ ๊ตฌ์„ฑํ•œ๋‹ค.
  2. ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ๋งˆ์ง€๋ง‰ ์š”์†Œ์™€ ๋ฐ”๊พผ๋‹ค.
  3. ํž™์˜ ์‚ฌ์ด์ฆˆ๋ฅผ ํ•˜๋‚˜ ์ค„์ด๊ณ  ํž™์„ ๋‹ค์‹œ ๊ตฌ์„ฑํ•œ๋‹ค.
  4. 2~3 ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

  ์ผ๋ฐ˜์ ์ธ ๋ฐฐ์—ด์˜ ๊ฒฝ์šฐ 0๋ฒˆ ์ธ๋ฑ์Šค๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋ฏ€๋กœ ๋ถ€๋ชจ ์ธ๋ฑ์Šค์™€ ์ž์‹ ์ธ๋ฑ์Šค์˜ ๊ด€๊ณ„๋ฅผ ์•„๋ž˜์™€ ๊ฐ™์ด ์ƒ๊ฐํ•œ๋‹ค๋Š” ์ ์„ ์œ ์˜ํ•˜์ž.

๋ถ€๋ชจ Index = (์ž์‹ Index) / 2 - 1
์™ผ์ชฝ ์ž์‹ Index = (๋ถ€๋ชจ Index) * 2 + 1
์˜ค๋ฅธ์ชฝ ์ž์‹ Index = (๋ถ€๋ชจ Index) * 2 + 2

  '2, 1, 3, 4, 5'๋ฅผ ํž™์ •๋ ฌ์„ ์ด์šฉํ•ด์„œ ์ •๋ ฌํ•ด ๋ณด์ž. size๋Š” 5์ด๋ฏ€๋กœ 1๋ถ€ํ„ฐ ๋ถ€๋ชจ์ธ๋ฑ์Šค๋กœ ํ•˜์—ฌ ์ตœ๋Œ€ํž™์„ ๊ตฌ์„ฑํ•œ๋‹ค. ( 5 / 2 - 1 = 5)(์ฝ”๋“œ์—์„œ ๊ตฌํ˜„๋œ Heapify๋ฅผ ์ฐธ๊ณ ํ•˜๋ฉด ๋™์ž‘ ๋ฐฉ์‹ ์ถฉ๋ถ„ํžˆ ์ดํ•ดํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. ์šฐ์„  ๊ทธ๋ฆผ์„ ํ†ตํ•ด ๋™์ž‘ ๋ฐฉ์‹์„ ํฌ๊ฒŒ ์ดํ•ดํ•ด ๋ณด๋„๋ก ํ•˜์ž.)

  ์™„์„ฑ๋œ ๋ชจ์Šต์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

  ๊ทธ๋ฆฌ๊ณ  ๋ฃจํŠธ ๋…ธ๋“œ์™€ ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋ฐ”๊ฟ”์ฃผ๊ณ  ํž™์„ ์žฌ๊ตฌ์„ฑํ•˜๋Š” ๋™์ž‘์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ถ€ํ„ฐ ํ•ด์„œ ์š”์†Œ๋“ค์ด ์ •๋ ฌ๋œ๋‹ค. ์ •๋ ฌ๋œ ์š”์†Œ๋Š” ํŒŒ๋ž€์ƒ‰์œผ๋กœ ํ‘œ์‹œํ•˜์˜€๋‹ค.

  ์ตœ์ข…์ ์œผ๋กœ ์ •๋ ฌ๋œ ๋ชจ์Šต์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

 

3. ๊ตฌํ˜„(JAVA) ๐ŸŠโ€โ™‚๏ธ

  ๋‹ค์Œ์€ ๊ตฌํ˜„์ฝ”๋“œ์ด๋‹ค. Heapify๊ฐ€ ๊ธฐ๋ณธ์ ์œผ๋กœ ๋™์ž‘ํ•˜๋Š” ๋ฐฉ์‹๊ณผ ์‚ฌ์ด์ฆˆ๋ฅผ ์ค„์—ฌ๊ฐ€๋ฉด์„œ Heapify๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๋ฐฉ์‹์„ ์œ ์˜ํ•ด์„œ ์ฝ”๋“œ๋ฅผ ์ดํ•ดํ•ด ๋ณด์ž.

public static void main(String[] args) {
    int[] array = { 2,1,3,4,5 };

    heapSort(array);
}

public static void heapSort(int[] array) {
    int size = array.length;

    // ํž™์„ ๊ตฌ์„ฑํ•œ๋‹ค. - ๋™์ž‘๋ฐฉ์‹(1)
    int parent = size / 2 - 1;
    for(int i = parent; i >= 0; i--) {
        heapify(array, size, i);
    }

    for(int i = size - 1; i > 0; i--) {
        // ๋ฃจํŠธ๋…ธ๋“œ์™€ ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋ฐ”๊พผ๋‹ค. - ๋™์ž‘๋ฐฉ์‹(2)
        swap(array, 0, i);
        // ํž™์˜ ์‚ฌ์ด์ฆˆ๋ฅผ ํ•˜๋‚˜ ์ค„์ด๊ณ  ํž™์„ ๋‹ค์‹œ ๊ตฌ์„ฑํ•œ๋‹ค. - ๋™์ž‘๋ฐฉ์‹(3)
        heapify(array, i, 0);
    }
}

public static void heapify(int array[], int size, int current) {
    int parent = current;
    int leftChild = current * 2 + 1;
    int rightChild = current * 2 + 2;

    if(leftChild < size 
            && array[parent] < array[leftChild]) {
        parent = leftChild;
    }

    if(rightChild < size 
            && array[parent] < array[rightChild]) {
        parent = rightChild;
    }

    if(current != parent) {
        swap(array, parent, current);
        heapify(array, size, parent);
    }
}

public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

 

4. ์‹œ๊ฐ„๋ณต์žก๋„ ๐Ÿคฝโ€โ™‚๏ธ

  Heapify๋ฅผ ํ•˜๋Š”๋ฐ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(log N)์ด๋‹ค. ํž™ ์ •๋ ฌ์„ ํ•˜๋Š”๋ฐ Heapify๋ฅผ N๋ฒˆ ํ˜ธ์ถœํ•ด์•ผ ํ•˜๋ฏ€๋กœ ์ด ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(N logN)์ด ๋˜๊ฒŒ ๋œ๋‹ค.

  ์ตœ์„ (BEST) ํ‰๊ท (AVERAGE) ์ตœ์•…(WORST)
์‹œ๊ฐ„๋ณต์žก๋„ O(N logN) O(N logN) O(N logN)

 

ํ•ด๋‹น ๊ธ€์€
Gyoogle๋‹˜์˜ ํž™ ์ •๋ ฌ(Heap Sort),
๋‚˜๋™๋นˆ๋‹˜์˜ ํž™ ์ •๋ ฌ(Heap Sort)
์„ ์ฐธ๊ณ ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

๋Œ“๊ธ€์ˆ˜0