JAVA 정렬 알고리즘 모음

선택정렬

선택정렬 설명

시간 복잡도 : Θ(n2)

    public int[] solution(int[] phone_book) {
        for(int i=0; i<phone_book.length-1; i++) {
            for(int j=i+1; j<phone_book.length; j++) {
                if(phone_book[i]>phone_book[j]) {
                    int set = phone_book[i];
                    phone_book[i] = phone_book[j];
                    phone_book[j] = set;
                }
            }
        }
        return phone_book;
    }

버블정렬

버블정렬 설명

시간 복잡도 : Θ(n2)

    public int[] solution(int[] phone_book) {
        for(int i=0; i< phone_book.length; i++) {
            for(int j=0; j<phone_book.length-i-1; j++) {
                if(phone_book[j]>phone_book[j+1]) {
                    int set = phone_book[j];
                    phone_book[j] = phone_book[j+1];
                    phone_book[j+1] = set;
                }
            }
        }
        return phone_book;
    }

삽입정렬

삽입정렬 설명

시간 복잡도 : Θ(n2)

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

---

어떠한 경우에서도 선택 정렬은 버블 정렬보다 우수하며 삽입 정렬은 선택정렬과 다르게 K+1 번째 요소를 배치하는데 필요한 만큼의 요소를 탐색 하기 때문에 선택 정렬에 비해 삽입 정렬이 더 효율적이다.

결론)

위 세가지중 우수한 알고리즘은 삽입 > 선택 > 버블 이다.

퀵정렬

퀵정렬 설명

시간 복잡도
- 평균 : Θ(n log n)
- 최악 : Θ(n2)

    public int[] solution(int[] phone_book,int start, int end) {
        int left = start;
        int right = end;

        int pivot = phone_book[(start+end)/2];

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

        if(start < right) solution5(phone_book,start,right);
        if(left < end) solution5(phone_book,left,end);

		return phone_book;
    }