[알고리즘] 삽입 정렬, 퀵 정렬(백준 2750, 1427 -Java)

[알고리즘] 삽입 정렬, 퀵 정렬(백준 2750, 1427 -Java)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

 

 

삽입 정렬

삽입 정렬은 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 입니다.
O(n^2)으로 느린편 이지만 구현하기가 쉽습니다.

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심!

삽입 정렬 동작 방식

 

1) 현재 index에 있는 데이터 값을 선택
2) 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
3) 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행
4) 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행
5) 전체 데이터의 크기만큰 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복

 

적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있습니다.

 

YouTube

백준 2750

2750번: 수 정렬하기
삽입 정렬을 구현해서 문제를 풀어보자!

풀이

public class Quiz2750 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 1; i < n; i++) {
            int index = i;
            int target = arr[index]; // 선택
            while (index > 0 && arr[index-1] > target) {
                arr[index] = arr[index-1]; // shift
                index--;
            }
            arr[index] = target;
        }

        StringBuilder sb = new StringBuilder();
        for(int i : arr) {
            sb.append(i).append("\n");
        }

        System.out.println(sb);
    }
}

백준 1427

1427번: 소트인사이드
삽입정렬을 구현해서 문제를 풀어보자.

풀이

public class Quiz1427 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();

        // 삽입 정렬을 이용하여 내림차순으로 정렬
        char[] ch = n.toCharArray();
        /**
         * 타겟 설정
         * 타켓값과 비교 대상 범위의 값과 비교하며 shift 연산
         */
        for(int i = 1; i < ch.length; i++) {
            int index = i;
            char target = ch[index];
            while (index > 0 && target > ch[index-1]) {
                // [7, 3, 5] -> [7, 5, 3]
                ch[index] = ch[index - 1]; // shift
                index--;
            }
            ch[index] = target;
        }

        StringBuilder sb = new StringBuilder();
        for(char c : ch) {
            sb.append(c);
        }
        System.out.println(sb);
    }
}

퀵 정렬

퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 입니다.
기준값이 어떤 방법으로 선정되는지가 시간 복잡도에 많은 영향을 미치고,
평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2) 입니다.

퀵 정렬 동작 방식

pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심 입니다.

만약에 오름차순으로 정렬을 해야한다면,
2개의 집합을 나눌때 pivot의 왼쪽은 pivot이 가리키는 값보다 작은 값으로
pivot의 오른쪽은 pivot이 가리키는 값보다 큰 값으로 나눕니다.

 

 

 

 

 

이 과정을 재귀를 이용해서 실행하면 됩니다.!!!

 

1) 데이터 분할하는 pivot 설정
2) pivot을 기준으로 아래 과정을 거침
2-1) pivot이 가리키는 데이터 보다 start가 가리키는 데이터가 작으면 start를 오른쪽으로 1칸 이동
2-2) pivot이 가리키는 데이터 보다 end이 가리키는 데이터가 크면 end를 왼쪽으로 1칸 이동
2-3) pivot이 가리키는 데이터 보다 start가 가리키는 데이터가 크고, pivot가 가리키는 데이터 보다 end가 가리키는 데이터가 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸 이동
2-4) start가 end보다 작거나 같을 때 까지 2-1 ~ 2-3 반복(start <= end)
2-5) start가 end보다 크면(start > end) 이면 start를 반환(start는 pivot 기준 왼쪽 배열의 첫번째 index!!!!😯)
3) 분리 집합에서 각각 다시 pivot을 설정(반환 된 start를 이용)
4) 분리 집합이 1개 이하가 될 때까지 과정 1 ~ 3 반복

 

YouTube

백준 2750

2750번: 수 정렬하기
퀵 정렬을 구현해서 문제를 풀어보자!

 

이유는 모르겠으나 pivot을 아래와 같이 설정해서 배열에 index로 활용하면 틀렸습니다로 나옵니다.
고수님들 이유를 아시면 알려주시면 감사하겠습니다..🙇🏻‍♂️

private static int partition(char[] ch, int start, int end) {
    int pivot = (start + end) / 2;
    int pivot = (start + end) / 2;
      // ... //
    return start;
}

 

풀이

public class Quiz2750 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        quickSort(arr, 0, arr.length-1);
        StringBuilder sb = new StringBuilder();
        for(int i : arr) {
            sb.append(i).append("\n");
        }

        System.out.println(sb);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if(start >= end) return;
        int mid = partitionSort(arr, start, end); // 오른쪽 그룹의 첫 번째 index
        /**
         * 오른쪽 파티션이 시작점 바로 다음에서 시작한다면
         * 왼쪽 파티션의 데이터가 1개 뿐이니 정렬할 필요가 없음
         * 따라서 오른쪽 파티션의 시작점(mid)이 왼쪽 파티션의 시작점(start)보다 최소 2는 커야함
         */
        if(mid > start + 1) {
            quickSort(arr, start, mid - 1); //왼쪽 그룹
        }
        /**
         * 오른쪽 파티션이 1개 이상일 때만 호출해야함
         * 오른쪽 파티션의 시작점(mid)이 끝점(end) 보다 작을때만 호출한다.
         */
        if(mid < end) {
            quickSort(arr, mid, end); // 오른쪽 그룹
        }
    }

    private static int partitionSort(int[] arr, int start, int end) {
        // 리스트의 가운데 있는 pivot 값을 선택
        int pivot = arr[(start + end) / 2];

        // 시작 인덱스(start)는 계속 증가 시키고,
        // 끝 인덱스(end)는 계속 감소 시키기위한 while 루프를
        // 두 인덱스가 서로 교차해서 지나칠 때까지 반복
        while (start <= end) {
            // 시작 인덱스(start)가 가리키는 값과 pivot 값을 비교해서
            // 더 작은 경우 반복해서 시작 인덱스 값을 증가
            // (pivot 값보다 큰데 좌측에 있는 값을 찾기 위해)
            while (arr[start] < pivot) start++;

            // 끝 인덱스(end)가 가리키는 값과 pivot 값을 비교해서
            // 더 작은 경우 반복해서 끝 인덱스 값을 감소
            // (pivot 값보다 작은데 우측에 있는 값을 찾기 위해)
            while (arr[end] > pivot) end--;

            // 두 인덱스가 아직 서로 교차해서 지나치치 않았다면
            // 시작 인덱스(start)가 가리키는 값과 끝 인덱스(end)가 가리키는 값을 swap
            // (잘못된 위치에 있는 두 값의 위치를 바꾸기 위해)
            if(start <= end) {
                // swap 후, 다음 값을 가리키기 위해 두 인덱스를 각자 진행 방향으로 한 칸씩 이동
                swap(arr, start++, end--);
            }
        }
        // 두 인덱스가 서로 교차해서 지나치게 되어 while 루프를 빠져나왔다면
        // 다음 재귀 호출의 분할 기준점이될 시작 인덱스를 리턴합니다.
        return start;
    }

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

백준 1427

1427번: 소트인사이드
퀵 정렬을 구현해서 문제를 풀어보자.

 

아직까지 이유는 잘 모르겠으나, 아래와 같이 하면 틀렸습니다로 나온다.. ㅠ
이유를 아시는 분은 댓글로 말씀주시면 감사하겠습니다. 🙇🏻‍♂️

private static int partition(char[] ch, int start, int end) {
    int pivot = (start + end) / 2;
    while (start <= end) {
        while (ch[pivot] < ch[start]) start++;
        while (ch[pivot] > ch[end]) end--;
        if(start <= end) {
            swap(ch, start++, end--);
        }
    }
    return start;
}

 

풀이

public class Quiz1427 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();

        // 퀵 정렬을 이용하여 내림차순으로 정렬
        char[] ch = n.toCharArray();

        int start = 0;
        int end = ch.length - 1;
        qucikSortReverse(ch, start, end);

        StringBuilder sb = new StringBuilder();
        for(char c : ch) {
            sb.append(c);
        }
        System.out.print(sb);
    }

    private static void qucikSortReverse(char[] ch, int start, int end) {
        if(start >= end) return;
        int mid = partition(ch, start, end);
        qucikSortReverse(ch, start, mid - 1);
        qucikSortReverse(ch, mid, end);
    }

    private static int partition(char[] ch, int start, int end) {
        char pivot = ch[(start + end) / 2];
        while (start <= end) {
            while (pivot < ch[start]) start++;
            while (pivot > ch[end]) end--;
            if(start <= end) {
                swap(ch, start++, end--);
            }
        }
        return start;
    }

    private static void swap(char[] ch, int start, int end) {
        char temp = ch[start];
        ch[start] = ch[end];
        ch[end] = temp;
    }
}