Job Boot Camp : Week 01 Report

codesver·2022년 10월 14일
job boot camp
0

Job Boot Camp

목록 보기
2/6
post-thumbnail

📌 Sortings

Question. Insertion / Merge / Quick 정렬을 구현하고, 아래의 데이터를 만들어서 시간 비교

📍 Insertion Sort

public void sort() {
    for (int i = 1; i < array.length; i++) {
        int value = array[i];
        int index = i - 1;
        while (index >= 0 && value < array[index]) {
            array[index + 1] = array[index];
            index--;
        }
        array[index + 1] = value;
    }
}

📍 Merge Sort

private void merge(int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        merge(left, center);
        merge(center + 1, right);

        int leftIndex = left, rightIndex = center + 1, index = left;

        while (leftIndex <= center || rightIndex <= right) {
            if (rightIndex > right || 
            		(leftIndex <= center && array[leftIndex] < array[rightIndex])) {
                temp[index++] = array[leftIndex++];
            } else {
                temp[index++] = array[rightIndex++];
            }
        }

        for (int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
}

@Override
public void sort() {
    temp = new int[array.length];
    merge(0, array.length - 1);
}

📍 Quick Sort

private void quick(int left, int right) {
    int value = partSort(left, right);
    if (left < value - 1) quick(left, value - 1);
    if (right > value) quick(value, right);
}

private int partSort(int left, int right) {
    int pivot = array[(left + right) / 2];
    while (left <= right) {
        while (array[left] < pivot) left++;
        while (array[right] > pivot) right--;
        if (left <= right) {
            int temp = array[right];
            array[right] = array[left];
            array[left] = temp;
            left++;
            right--;
        }
    }
    return left;
}

@Override
public void sort() {
    quick(0, array.length - 1);
}

📍 Performance measure

  • 1,000 미만
Enter size of array to measure = 10
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 0ms
Duration of sorting descend array by insertion sorting is 0ms
Duration of sorting random array by insertion sorting is 0ms
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 0ms
Duration of sorting descend array by merge sorting is 0ms
Duration of sorting random array by merge sorting is 0ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 0ms
Duration of sorting descend array by quick sorting is 0ms
Duration of sorting random array by quick sorting is 0ms
===========================================================================
  • 1,000
Enter size of array to measure = 1000
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 0ms
Duration of sorting descend array by insertion sorting is 6ms
Duration of sorting random array by insertion sorting is 1ms
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 1ms
Duration of sorting descend array by merge sorting is 1ms
Duration of sorting random array by merge sorting is 0ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 0ms
Duration of sorting descend array by quick sorting is 0ms
Duration of sorting random array by quick sorting is 1ms
===========================================================================
  • 10,000
    Enter size of array to measure = 10000
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 0ms
Duration of sorting descend array by insertion sorting is 60ms
Duration of sorting random array by insertion sorting is 25ms
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 5ms
Duration of sorting descend array by merge sorting is 4ms
Duration of sorting random array by merge sorting is 4ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 2ms
Duration of sorting descend array by quick sorting is 1ms
Duration of sorting random array by quick sorting is 2ms
===========================================================================
  • 100,000
Enter size of array to measure = 100000
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 4ms
Duration of sorting descend array by insertion sorting is 3524ms
Duration of sorting random array by insertion sorting is 1675ms
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 30ms
Duration of sorting descend array by merge sorting is 26ms
Duration of sorting random array by merge sorting is 26ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 33ms
Duration of sorting descend array by quick sorting is 17ms
Duration of sorting random array by quick sorting is 48ms
==========================================================================
  • 1,000,000
Enter size of array to measure = 1000000
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 9ms
Duration of sorting descend array by insertion sorting is 1499021ms
Duration of sorting random array by insertion sorting is 207359ms
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 124ms
Duration of sorting descend array by merge sorting is 139ms
Duration of sorting random array by merge sorting is 266ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 47ms
Duration of sorting descend array by quick sorting is 24ms
Duration of sorting random array by quick sorting is 185ms
===========================================================================
  • 10,000,000
Enter size of array to measure = 10000000
=================================INSERTION=================================
Duration of sorting ascend array by insertion sorting is 14ms
Duration of sorting descend array by insertion sorting is too long to measure
Duration of sorting random array by insertion sorting is too long to measure
===========================================================================
===================================MERGE===================================
Duration of sorting ascend array by merge sorting is 1236ms
Duration of sorting descend array by merge sorting is 1145ms
Duration of sorting random array by merge sorting is 2866ms
===========================================================================
===================================QUICK===================================
Duration of sorting ascend array by quick sorting is 287ms
Duration of sorting descend array by quick sorting is 276ms
Duration of sorting random array by quick sorting is 1917ms
===========================================================================

📌 Heap Sorting

📍 Heap Sorting & Priority Queue

  • Priority Queue

일반적인 Queue는 FIFO라는 특징을 가집니다. First In First Out으로 먼저 삽입된 원소가 먼저 나오는 것입니다. 여기에 우선순위를 넣은 것이 우선순위 queue 입니다. 우선순위 queue는 삽입된 순서와 상관 없이 우선순위가 높은 원소가 우선해서 나옵니다. 우선순위 queue를 구현하기 위해서는 우선순위에 맞게 정렬해주는 자료구자 필요한데 이것이 바로 heap 입니다.

  • Heap

Heap은 기본적으로 완전 이진 트리의 형태입니다.

또한 최대힙과 최소힙이 있는데 최대힙은 부모 node가 자식 node보다 값이 큰 경우이고 최소힙은 반대의 경우입니다.

  • Heap Sorting
  • Heap 정렬의 기본은 heapify입니다. 특정 node에서 heapify를 시작하면 node와 자식 node들을 비교하여 최댓값을 현재 node에 저장합니다. 자식 node와 교환을 했다면 해당 자식 node에서 다시 heapify를 하고 이를 반복합니다. 이러한 heapify를 반복하여 최대힙과 최소힙을 만드는 것이 최대힙이나 최소힙을 구성하는 것이 heap 정렬입니다.

📌 Min Heap

Question. Heap sorting PDF의 4번째 슬라이드를 최소힙으로 그리기

📍 Max Heap

📍 Min Heap

  • Start Node Index(value)

Untitled

  • Step 1 Node 5(7)

Untitled

  • Step 2 Node 4(8)

Untitled

  • Step 3 Node 3(10)

Untitled

  • Step 4 Node 2(14)

Untitled

  • Step 5 Node 1(16) MIN HEAP

Untitled

profile
codesver
Hello, Devs!
이전 포스트

Job Boot Camp : Week 01 Lecture

다음 포스트

Job Boot Camp : Week 02 Report

0개의 댓글