[LeetCode] Sort an Array (버블, 삽입, 선택, 퀵, 병합, 힙 정렬)

leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2944/

Explore - LeetCode

---

1. 버블 정렬 Bubble Sort

i번째 와 i+1번째 요소를 비교하여 배열 순차탐색
조건에 맞는 요소를 가장 뒤로 밀어내는 개념 (버블처럼 해당 수를 위로 보냄)
시간복잡도 O(n^2)
Time Limit Exceeded

class Solution {
    public int[] bubbleSortArray(int[] nums) {
        int size = nums.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = i+1; j < size ; j++) {
                if (nums[i] > nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        return nums;
    }
}

2. 삽입 정렬 Insertion Sort

배열의 두번 째 데이터를 기준 오른쪽으로 이동하며 순차 탐색
기준보다 큰 수는 오른쪽으로 밀어내고, 왼쪽 요소와 계속 비교 (기준의 왼쪽은 정렬되어 있음)
이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.
시간복잡도 O(n^2)

class Solution {
    public int[] insertionSortArray(int[] nums) {
        int size = nums.length;
        for (int i = 1; i < size; i++) {
            int standard = nums[i]; // 기준
            int index = i - 1;  // 비교

            // 비교대상이 기준보다 크다면
            while (index >= 0 && standard < nums[index]){
                nums[index + 1] = nums[index];  //오른쪽으로 밀어냄
                index--;
            }
            nums[index + 1] = standard; // 기준
        }
        return nums;
    }
}

3. 선택 정렬 Selection Sort

주어진 데이터 중 최소값을 찾음
최소값을 맨 앞에 위치한 값과 교환
정렬된 데이터를 제외한 나머지 데이터를 같은 방법으로 정렬
시간복잡도 O(n^2)

class Solution{
    public int[] selectionSortArray(int[] nums) {
        int size = nums.length;
        int min;
        int temp;
        for (int i = 0; i < size - 1; i++) {
            min = i;
            for (int j = i + 1; j < size; j++) {
                if(nums[min] > nums[j]){
                    min = j;
                }
            }
            temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
        return nums;
    }
}

4. 퀵 정렬 Quick Sort

리스트 가운데서 하나의 원소를 고름(pivot 선정)
리스트를 둘로 분할 >> pivot 앞에는 pivot 보다 작은값, 뒤에는 큰 값
분할된 두개의 리스트에 해당 방식을 재귀함수로 반복
시간복잡도 최악 : O(n^2), 평균 : O(NlogN)

class Solution {
    public int[] quickSortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void sort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];

        do{
            while(data[left] < pivot) {
                left++;
            }
            while(data[right] > pivot) {
                right--;
            }
            if(left <= right){
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);

        if(l < right) {
            sort(data, l, right);
        }
        if(r > left) {
            sort(data, left, r);
        }
    }
}

5. 합병(병합) 정렬 Merge Sort

binary tree 형태로 원소가 하나 남을 때까지 분할한다.

각 분할 된 요소를 정렬하고, 정렬된 리스트를 병합하는 방식

시간복잡도 : O(nlogn)

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    public void mergeSort(int [] nums, int start, int end){
        if (start < end) {
            int mid = (start + end) / 2;    // 중간지점 찾기
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, start, mid, end);
        }
    }

    // 정렬된 두 리스트 배열을 합병(병합)
    // nums[start...mid] 와 nums[mid+1...end]
    // 정렬된 하나의 배열 nums[start...end] 로 만들기
    public void merge(int [] nums, int start, int mid, int end){
        int i = start;
        int j = mid + 1;
        int k = start;
        int [] temp = new int [nums.length];

        while (i <= mid && j <= end){
            if (nums[i] < nums[j]){
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid){
            temp[k++] = nums[i++];
        }
        while (j <= end){
            temp[k++] = nums[j++];
        }

        for (int index=start; index < k; index++) {
            nums[index] = temp[index];
        }
    }
}

6. 힙 정렬 Heap Sort

힙 자료구조를 기반으로 한 정렬방식 (힙은 완전이진트리 형태의 자료구조)

최대 힙 : 부모노드의 값이 자식노드의 값보다 항상 큰 힙

최소 힙 : 부모노드의 값이 자식노드의 값보다 항상 작은 힙

시간 복잡도 : O(nlogn)

 

정렬 방식

1. 최대 or 최소 힙을 만든다. (swap 사용)

2. 만들어진 힙이 최대/최소 힙을 구성할 수 있도록 반복 정렬한다.

 

✅ 완전 이진 트리의 부모 자식 관계

부모노드 : arr[i] 일 때
arr[i]의 왼쪽 자식 노드 = arr[i*2 + 1]
arr[i]의 오른쪽 자식 노드 = arr[i*2 + 2]

class Solution {
    public int[] heapSortArray(int[] nums) {
        // 1. max heap 만들기
        // i의 초기값은 배열의 제일 끝 자식노드의 부모노드부터 시작
        for (int i = nums.length/2 - 1; i >= 0; i--) {
            heapify(nums, nums.length, i);
        }

        // 2. 정렬하기
        for (int i = nums.length - 1; i >= 0; i--) {
            swap(nums, i, 0);   //최상단 노드와 최하단 노드의 값 교환
            heapify(nums, i, 0);  //루트노드를 기준으로 최대힙 생성
        }
        return nums;
    }

    public void heapify(int [] arr, int size, int pNode){
        int parent = pNode;     // 부모 노드
        int lNode = pNode * 2 + 1;  // 왼쪽 자식노드
        int rNode = pNode * 2 + 2;  // 오른쪽 자식노드

        // size > lNode : 인덱스 범위를 넘어서는지 확인하기 위해
        if (size > lNode && arr[parent] < arr[lNode]){
            parent = lNode;
        }

        if (size > rNode && arr[parent] < arr[rNode]){
            parent = rNode;
        }

        // parent에 저장된 값보다 큰 자식노드 값이 있다면 해당 인덱스로 교환
        if (parent != pNode){
            swap(arr, pNode, parent);
            // 노드와 자리를 바꾸면 최대 힙 기준에 맞지 않을 수 있기 때문에
            // 바뀐 자식노드 아래 최대힙으로 맞춘다.
            heapify(arr, size, parent);
        }

    }
    
    public void swap(int [] arr, int big, int small){
        int temp = arr[small];
        arr[small] = arr[big];
        arr[big] = temp;
    }
}

 

 

참고 : 

hmkim829.tistory.com/9