[JAVA] 퀵 정렬 구현

---

구현 코드

원래 백준의 2751번 문제를 풀려고 구현한 퀵정렬이지만, 정작 이 코드로는 메모리 초과로 통과하지 못한다...

아마도 재귀이기 때문에 그런것 같다...

결국 풀이 방법은 따로 있지만, 오랜만에 퀵 정렬을 구현해 보았기 때문에 포스팅 하기로 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class B2751_수정렬하기2 {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        quickSort(arr, 0, n-1);
        StringBuilder sb = new StringBuilder();
        Arrays.stream(arr).forEach(i-> sb.append(i + "\n"));
        System.out.println(sb);
    }



    static void quickSort(int[] arr, int start, int end) {

        if(start >= end)
            return;

        int middle = arr[(start + end) / 2];

        int left = start;
        int right = end;

       while (left <= right) { //=조건이 없으면 left와 right가 겹쳐진 이후로 계속 quickSort 무한호출에 빠짐
            while(arr[left] < middle) left++;
            while(arr[right] > middle) right--;

            if (left <= right) { //=조건이 없으면 left와 right가 겹쳐진 이후로 계속 quickSort 무한호출에 빠짐
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }

        quickSort(arr, start, right);
        quickSort(arr, left, end);
    }
}

 

퀵정렬의 가장 중요한 점은

1. 피봇값 선정

2. left, right 인덱스를 이용하여 left 위치엔 pivot보다 작은값 right에는 pivot 보다 큰 값을 저장한다

3. 피봇 기준으로 정렬 된 수열을 좌 우측으로 분할하여 퀵정렬을 각각 수행

4. 최종적으로 정렬대상인 수열의 길이가 0또는 1개일때 까지 재귀

 

위 내용들이다.

 

그리고 코드에서 보이는것과 같이

해당 조건에 "=" 조건이 들어가 주지 않으면 무한 루프에 빠지는 상황이 발생한다.

그리고 해당 테스트 케이스는 아래와 같다.

//무한루프 발생 가능한 상황
5
1
2
35
8
9

 

아래는 일반적인 상황이다.

//기본적인 상황
6
12
13
7
6
4
1