[백준,BOJ 2751] 수 정렬하기 2( JAVA 구현)

-내 생각

  우선 이 문제를 풀게 된 계기는 11004번 문제인 k번째 수 문제를 풀려고 했는데, 이러한 방식은 Quick Selection이라는 별도의 알고리즘을 사용한다고 해서 찾아보니, 해당 알고리즘은 기존의 퀵 정렬 알고리즘을 활용한 방식이라고 하여서 퀵 정렬 알고리즘을 우선적으로 공부해보고자 해서 풀게 되었다. 이전에 동영상 강의를 보면서 병합 정렬을 사용해서 풀었던 문제였는데, 한 달이라는 시간이 지나서 기억이 나지 않아서 우선 퀵 정렬을 이용해 풀어보기로 했다. 그러나 혼자 힘으로 구현해보려 했지만 잘 되지 않아서 마이구미님의 블로그를 참고하게 되었다. 아래에 설명이 자세히 나와있다.

https://mygumi.tistory.com/308

퀵소트 알고리즘 :: 마이구미

 

-해법

  우선 퀵 정렬 알고리즘의 경우 pivot을 어떤 방식으로 설정하느냐에 따라서 시간 복잡도에 차이가 발생한다고 한다. 왜냐하면 퀵 정렬의 경우 평균적으로 O(nlog n)의 시간 복잡도를 가지지만, 최악의 경우 O(n^2)의 시간 복잡도를 가지기 때문이라고 한다. 그러나 필자는 단순히 퀵 정렬만을 구현해보고자 하여서 pivot값을 중앙으로 설정하는 방식을 고집하여 여러 블로그를 확인하면서 구현해봤지만, 많은 분들이 pivot을 제일 첫 번째 원소로 설정하여 푸는 방식을 확인할 수 있었고, 그러한 글들 중 마이구미님의 블로그 글이 유익하다 하여서 학습하게 되었다.

 

  해당 글에서 핵심 내용은 기본적인 퀵 정렬 알고리즘에서 pivot값과 left, right의 활용은 동일하나 pivot의 설정에 따라 시간 복잡도의 차이가 존재한다는 사실이었다. 대표적인 최악의 경우가 입력된 값들이 역순으로 입력될 경우인데, 이 경우에는 O(n^2)의 시간 복잡도를 가지게 된다고 한다. 이러한 문제를 해결하기 위해서는 단순히 입력 값들 중 중앙값을 첫 번째 요소와 교환하여서 첫 번째 요소를 피봇으로 잡으면 해결할 수 있다고 한다. 또한 이러한 방식은 여타 다른 O(n log n)의 시간 복잡도를 가지는 정렬 방식들에 비해 빠르다고 한다. 실제로 필자는 퀵 정렬을 별도로 구현해보지 못해서 확인하지는 못해서 자바에서 일반적으로 사용하는 정렬 메서드인 Arrays.sort()와 비교하였을 때, 시간 초과가 발생했지만, 위의 방식은 정답처리를 받을 수 있는 걸 확인할 수 있었다.

 

	
import java.util.Scanner;

public class Quick_Sort {
	
	public static int partition(int[] array, int left, int right) { // 구분점을 만드는 메소드
	    int mid = (left + right) / 2; // 원소의 중앙값을 첫 번째 원소와 교환하기 위함
	    swap(array, left, mid); // 중앙 값을 첫 번째 요소로 이동
	 
	    int pivot = array[left]; // 첫 번째 인덱스가 pivot이 된다.
	    
        int i = left, j = right;
	 
	    while (i < j) { // left < right 즉, 교차하기 전 까지 반복한다.
	        while (pivot < array[j]) { // j는 오른쪽에서 왼쪽으로 피봇보다 작거나 같은 값을 찾는다.
	            j--;
	        }
	 
	        while (i < j && pivot >= array[i]) { // i는 왼쪽에서 오른쪽으로 피봇보다 큰 값을 찾는다.
	            i++;
	        }
	        swap(array, i, j); // 찾은 i와 j를 교환
	    }
	    // 반복문을 벗어난 경우는 i와 j가 만난경우
	    // 피봇과 교환
	    array[left] = array[i]; // 어차피 i와 j가 만나기 때문에 i 또는 j를 사용하면 된다.
	    array[i] = pivot; // array[left]값을 담아 둔 pivot을 구분점의 요소에 저장
	    return i; // 구분점이 되는 인덱스를 반환한다.
	}
	 
	public static void swap(int[] array, int a, int b) { // 단순 swap 메소드
	    int temp = array[b];
	    array[b] = array[a];
	    array[a] = temp;
	}
	 
	public static void quicksort(int[] array, int left, int right) { // 실질적인 quickSort 재귀호출을 이룬다.
	    if (left >= right) { // 이 경우는 비교할 요소가 한 개일 경우이므로 메소드를 종료한다.
	        return;
	    }
	 
	    int pi = partition(array, left, right); // 위의 메소드를 통해서 구한 구분점을 저장
	    quicksort(array, left, pi - 1); // left부터 구분점 전까지 다시 한 번 재귀호출
	    quicksort(array, pi + 1, right); // 구분점 다음부터 right까지 다시 한 번 재귀호출
	}


	
	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(int i=0;i<n;i++) {
			 System.out.println(arr[i]);
			 
		 }
	     
		
			
	       
	      
	}

}

 

  다음에는 최악의 경우에도 O(nlog n)의 시간 복잡도를 가지는 합병 정렬을 이용해서 풀어봐야겠다.

정렬의 경우 암기가 어느 정도 필요하기 때문에 자주 복습해야겠다.