Algorithm & Data Structure/Theory

[Java] 정렬(Sort)

ju_young 2023. 11. 6. 12:31
728x90
Algorithm Time Complexity Memory stability
Bubble Sort O(n) 1 O
Insertion Sort O(n) 1 O
Selection Sort O(n) 1 X
Merge Sort O(nlogn) n O
Heap Sort O(nlogn) 1 X
Quick Sort O(n) logn X
Radix Sort O(dn) 1 n + k
Counting Sort O(n + k) n + k O
Shell Sort O(n) 1 X

Bubble Sort

  • 인접한 데이터를 비교하며 자리를 바꾸는 방식
  • 시간 복잡도: O(n)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        for (int i=1; i<arr.length; i++) {
            for (int j=0; j<arr.length; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }
}

Insertion Sort

  • 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식
  • 시간 복잡도: O(n)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i=1; i<arr.length; i++) {
            for (int j=i; j>0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                } else {
                    break;
                }
            }
        }
    }
}

Selection Sort

  • 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식
  • 시간 복잡도: O(n)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        for (int i=0; i<arr.length - 1; i++) {
            int min = i;
            for (int j=i+1; j<arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

Merge Sort

  • 배열을 계속 분할해서 길이가 1이 되도록 만들고 인접한 부분끼리 정렬하면서 합병하는 방식
  • 시간 복잡도: O(nlogn)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            merge(arr, tmp, left, right, mid);
        }
    }

    public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
        int p = left;
        int q = mid + 1;
        int idx = p;

        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {
                if (arr[p] <= arr[q]) {
                    tmp[idx++] = arr[p++];
                } else {
                    tmp[idx++] = arr[q++];
                }
            } else if (p <= mid && q > right) {
                temp[idx++] = arr[p++];
            } else {
                tmp[idx++] = arr[q++];
            }
        }

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

Heap Sort

  • 힙 자료구조 형태의 정렬 방식
  • 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행
  • 시간 복잡도: O(nlogn)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        for (int i=arr.length/2-1; i>=0; i--) {
            heapify(arr, i, arr.length);
        }

        for (int i=arr.length-1; i>0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    public static void heapify(int[] arr, int parentIdx, int size) {
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;
        if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }
        if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }
        if (parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            heapify(arr, maxIdx, size);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Quick Sort

  • 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식
  • 시간 복잡도: O(n)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = partition(arr, left, right);

        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, left, i);

        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

평균 시간 복잡도는 O(nlogn)이지만 기준 값이 최소값 또는 최대값으로 지정되는 경우 worst case가 되어 O(n)을 가진다.

Radix Sort

  • 낮은 자리 수부터 정렬하는 방식
  • 각 원소 간의 비교 연산을 하지 않아 빠은 대신 Radix Table을 위한 메모리가 필요
  • 시간 복잡도: O(dn) (d: 최대 자릿수)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        List<Queue<Integer>> list = new ArrayList<>();
        for (int i=0; i<10; i++) {
            list.add(new LinkedList<>());
        }

        int idx = 0;
        int div = 1;
        int maxLen = getMaxLen(arr);

        for (int i=0; i<maxLen; i++) {
            for (int j=0; j<arr.length; j++) {
                list.get((arr[j] / div) % 10).offer(arr[j]);
            }
            for (int j=0; j<10; j++) {
                Queue<Integer> queue = list.get(j);
                while (!queue.isEmpty()) {
                    arr[idx++] = queue.poll();
                }
            }

            idx = 0;
            div *= 10;
        }
    }

    public static int getMaxLen(int[] arr) {
        int maxLen = 0;
        for (int i=0; i<arr.length; i++) {
            int len = (int) Math.log10(arr[i]) + 1;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }
}

Counting Sort

  • 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
  • 카운팅을 위한 메모리 필요
  • 시간 복잡도: O(n + k) (k: 정렬 대상 데이터 중 최대값)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void countingSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cntArr = new int[max + 1];

        for (int i=0; i<arr.length; i++) {
            cntArr[arr[i]]++;
        }

        int idx = 0;
        for (int i=0; i<cntArr.length; i++) {
            while (cntArr[i] > 0) {
                arr[idx++] = i;
                cntArr[i] -= 1;
            }
        }
    }
}

Shell Sort

  • 삽입 정렬의 약점 보완한 정렬 방식
  • 삽입 정렬에서는 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하여 모두 교환이 필요
  • 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교
  • 시간 복잡도: O(n)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;

        for (int g=gap; g>0; g/=2) {
            for (int i=g; i<arr.length; i++) {
                int temp = arr[i];
                int j = 0;
                for (int j=i-g; j>=0; j-=g) {
                    if (arr[j] > tmp) {
                        arr[j + g] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + g] = tmp;
            }
        }
    }
}

간격 설정에 따라 worst case는 삽입 정렬과 동일하고 일반적인 데이터 기준으로는 삽입 정렬에 비해 빠르다.

안정 정렬 vs 불안정 정렬

  • 안정 정렬 (Stable Sort): 중복된 값을 입력 순서와 동일하게 정렬되는 특성
  • 불안정 정렬 (Unstable Sort): 중복된 값이 입력 순서와 동일하지 않게 정렬되는 특성

[reference]
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

728x90

'Algorithm & Data Structure > Theory' 카테고리의 다른 글

[Java] 투 포인터  (0) 2023.11.08
[Java] 이진 탐색  (0) 2023.11.07
[Java] Heap (힙)  (1) 2023.10.21
[Java] Array (배열)  (0) 2023.10.18
[Java] Queue (큐)  (0) 2023.10.17

'Algorithm & Data Structure/Theory'의 다른글

  • 현재글[Java] 정렬(Sort)

관련글

댓글

티스토리툴바