2024.05.14.화

여러가지 정렬을 구현해 보았다.

 

삽입 정렬

import java.util.Scanner;

public class Sort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];

        for(int i=0;i<count;i++)
        {
            arr[i] = sc.nextInt();
        }

        for (int i = 1; i < count; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }

        for(var index : arr)
        {
            System.out.println(index);
        }

    }
}

 

 

버블 정렬

import java.util.Scanner;

public class BubbleSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("n :"+n);
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            System.out.println(i+" : "+arr[i]);
        }

        for (int i = 0; i < n; i++) {
            while (i < n - 1) {
                int temp = arr[i];
                if (arr[i] > arr[i + 1]) {
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
                i++;
            }
        }

        for (var index : arr) {
            System.out.print(index+" ");
        }

    }
}

 

 

이진트리 정렬

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 중위순회
public class BinarySearchSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        BinaryTree tree = new BinaryTree();
        for(var index : arr)
        {
            tree.insert(index);
        }
        List<Integer> sortList = new ArrayList<>();
        tree.inorderTree(tree.root,sortList);

        for (var index : sortList) {
            System.out.println(index+" ");
        }


    }

    // 트리
    static class BinaryTree {
        BinaryTreeNode root;

        public void insert(int val) {
            root = insertTree(root, val);
        }

        private BinaryTreeNode insertTree(BinaryTreeNode root, int val) {
            if (root == null) {
                root = new BinaryTreeNode(val);
            }
            if (val < root.val) {
                root.left = insertTree(root.left, val);
            } else if (val > root.val) {
                root.right = insertTree(root.right, val);
            }
            return root;
        }

        public void inorderTree(BinaryTreeNode root, List<Integer> list) {
            if (root != null) {
                // 중위 순회 돌리기
                inorderTree(root.left, list);
                list.add(root.val);
                inorderTree(root.right, list);
            }
        }
    }

    // 노드
    static class BinaryTreeNode {
        int val;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }
}

 

 

퀵 정렬

import java.util.Scanner;

public class QuickSort {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        quickSort(arr,0,n-1);

        for (var index : arr) {
            System.out.println(index+" ");
        }

    }

    static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);

            // pivot을 기준으로 좌우 부분 나눠서 재귀정렬
            quickSort(arr, left, pivot - 1);
            quickSort(arr, pivot + 1, right);
        }
    }

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

        for(int h=left;h<right;h++){
            // 현재 요소가 pivot보다 작다면 전부 왼쪽으로 옮기기
            if (arr[h] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[h];
                arr[h] = temp;
            }
        }

        // pivot 옮기기
        int temp = arr[i+1];
        arr[i+1] = arr[right];
        arr[right]=temp;
        // pivot반환
        return i+1;
    }
}

 

 

네 가지 방법으로 구현해 봤는데, 각 정렬의 장단점을 정리하면 아래와 같다.

 

	장점	단점	평균	최악	최선
삽입 정렬	구현이 쉬우며, 데이터가 이미 어느정도 정렬되어 있는 경우 빠르게 정렬	입력할 데이터가 역순이면 최악의 경우 O(n²)의 성능을 보인다.	O(n ² )	O(n ² )	O(n)
버블 정렬	구현이 매우 쉽다.	성능이 안좋다. 항상 O(n²)의 성능을 보인다.	O(n ² )	O(n ² )	O(n )
이진트리 정렬	입력 시 값에 따라 곧바로 위치가 지정되기 때문에 데이터 검색 속도가 빠르다.  따라서 숫자 값 검색이 잦을 경우에 유리하다.	최악의 경우에 한 쪽으로만 이어질 수 있다. (이를 보완한 트리로 AVL tree, red black tree .. 등이 있다.) 메모리 공간을 좀 더 차지한다.	O(nlogn)	O(n ² )	O(nlogn)
퀵 정렬	평균적으로 가장 빠른 속도. 추가적인 메모리 공간을 필요로 하지 않는다.	최악의 경우, O(n ² )의 성능을 보이며, pivot을 어떻게 선택하느냐에 따라 성능이 달라진다.	O(nlogn)	O(n ² )	O(nlogn)

 

다음에는 Heap정렬과 병합정렬도 구현해 보자