[알고리즘] Java로 정렬 알고리즘 구현해보기

선택 정렬

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

    // 선택 정렬
    private static int[] selectionSort(int[] numbers) {
        // 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복
        // 시간복잡도 O(n^2)
        // 공간복잡도 O(1)

        for (int i = 0; i < numbers.length; i++) {
            int minIndex = i;

            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[minIndex] > numbers[j]) {
                    minIndex = j;
                }
            }

            int temp = numbers[minIndex];
            numbers[minIndex] = numbers[i];
            numbers[i] = temp;
        }

        return numbers;
    }

 

 

삽입 정렬

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

    // 삽입 정렬
    private static int[] insertionSort(int[] numbers) {
        // 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입하는 과정을 반복
        // 시간복잡도 O(n^2) 이미 정렬되어 있는 경우는 O(n)
        // 공간복잡도 O(1)

        for (int i = 1; i < numbers.length; i++) {
            for (int j = i; j > 0; j--) {
                if (numbers[j] >= numbers[j - 1]) {
                    break;
                }

                int temp = numbers[j];
                numbers[j] = numbers[j - 1];
                numbers[j - 1] = temp;
            }
        }

        return numbers;
    }

 

 

버블 정렬

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

    // 버블 정렬
    private static int[] bubbleSort(int[] numbers) {
        // 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
        // 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
        // 시간복잡도 O(n^2)
        // 공간복잡도 O(1)

        for (int i = 0; i < numbers.length; i++) {
            for (int j = 1; j < numbers.length - i; j++) {
                if (numbers[j - 1] > numbers[j]) {
                    int temp = numbers[j - 1];
                    numbers[j - 1] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }

        return numbers;
    }

 

 

합병 정렬

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

    // 합병 정렬
    private static int[] mergeSort(int[] numbers) {
        // 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
        // 시간복잡도 O(NlogN)
        // 공간복잡도 O(N)

        if (numbers.length < 2) {
            return numbers;
        }

        int mid = numbers.length / 2;
        int[] low = mergeSort(Arrays.copyOfRange(numbers, 0, mid));
        int[] high = mergeSort(Arrays.copyOfRange(numbers, mid, numbers.length));

        return sort(low, high);
    }

    private static int[] sort(int[] low, int[] high) {
        int[] result = new int[low.length + high.length];

        int lowPoint = 0;
        int highPoint = 0;

        for (int i = 0; i < result.length; i++) {
            if (lowPoint == low.length) {
                result[i] = high[highPoint];
                highPoint++;
                continue;
            }

            if (highPoint == high.length) {
                result[i] = low[lowPoint];
                lowPoint++;
                continue;
            }

            if (low[lowPoint] < high[highPoint]) {
                result[i] = low[lowPoint++];
            } else {
                result[i] = high[highPoint++];
            }
        }

        return result;
    }

 

 

퀵 정렬

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

    // 퀵 정렬
    private static int[] quickSort(int[] numbers, int start, int end) {
        // 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
        // 시간복잡도 O(NlogN) 최악의 경우(pivot값이 편향적일 경우) O(N^2)
        // 공간복잡도 O(logN)

        if (start >= end) {
            return numbers;
        }

        int left = start + 1;
        int right = end;
        int pivot = start;

        while (left <= right) {
            while (left <= end && numbers[left] <= numbers[pivot]) {
                left++;
            }
            while (right > start && numbers[right] >= numbers[pivot]) {
                right--;
            }

            if (left > right) {
                int temp = numbers[pivot];
                numbers[pivot] = numbers[right];
                numbers[right] = temp;
                continue;
            }

            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }

        quickSort(numbers, start, right - 1);
        quickSort(numbers, right + 1, end);

        return numbers;
    }

 

 

힙 정렬

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

    // 힙 정렬
    private static int[] heapSort(int[] numbers) {
        // 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
        // 시간 복잡도 O(NlogN)
        // 공간 복잡도 O(1)

        for (int i = numbers.length / 2 - 1; i >= 0; i--) {
            heapify(numbers, numbers.length, i); // 최대힙
        }

        System.out.println();
        print(numbers);

        for (int i = numbers.length - 1; i >= 0; i--) {
            int temp = numbers[0];
            numbers[0] = numbers[i];
            numbers[i] = temp;

            heapify(numbers, i, 0);
            print(numbers);
        }

        return numbers;
    }

    private static void heapify(int[] numbers, int size, int node) {
        int parent = node;
        int leftChild = node * 2 + 1;
        int rightChild = node * 2 + 2;

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

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


        if (parent != node) {
            int temp = numbers[node];
            numbers[node] = numbers[parent];
            numbers[parent] = temp;

            heapify(numbers, size, parent);
        }
    }

 

정렬 알고리즘 시간 복잡도 비교

 

 

 

[참고]

https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html

[기술 면접 질문] 기술 면접 예상 질문 대비하기 - 알고리즘(Algorithm)편 - Heee's Development Blog