찰떡개발자 코딩

오늘은 Quick Sort에 대해 공부해 보려고한다.

이름에서도 보이는 바와 같이 빠른 정렬이다.

퀵 정렬의 메커니즘은 크게 다음과 같다.

Sorting할 List를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어

하나는 피벗보다 작은 값들의 부분리스트, 

다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬 후 ,

각 부분리스트에 대해 다시 위의 로직을 재귀적으로 수행하여 정렬하는 방법이다.

쉽게 말해 부분을 나눠서 각각 자기가 맡은 부분을 정렬시킨다고 보면 된다.

로직 순서

1. 피벗을 선택

2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다.

   왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.

3. 양 방향에서 찾은 두 원소를 교환

4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.

5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)

6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)

장점

1. 특정 상태가 아닌 이상 평균 시간 복잡도는 NlogN

   다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 

2. 추가적인 별도의 메모리를 필요로하지 않으며 재귀 호출 스택프레임에 의한 공간복잡도는 logN으로 메모리를 적게 소비한다.

단점

1. 특정 조건하에 성능이 급격하게 떨어진다.

2. 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.

참조 :https://st-lab.tistory.com/250

피벗의 위치를 선택하는것에 따라 방법이 달라진다.

피벗을 왼쪽끝, 오른쪽 끝, 중간 세가지로 선택하여 하는 방법이있는데, 본인은 일단 중간으로 하여 코드를 작성해보려고 한다.

피벗의 위치를 최종적으로 들어갈 위치와 교환 =>  그 위치를 반환하는 메소드가 partition메소드고, 반환 된 피벗의 위치를 기준으로 왼쪽과 오른쪽 부분리스트로 나누어 재귀적으로 분할정복을 해준다.

public Class QuickSortAlgorithm{

	public static void main(String[] args){
    
    	//Sorting할 배열 선언
    	int[] arr = {10,7,3,5,77,4,2,8,1};
		//index 0~마지막 까지를 입력한다.        
       	quickSort(arr,0,arr.length-1);
    }

	//정렬할 배열, 배열의 시작점, 배열의 끝점을 파라미터로 받는다.
	static void quickSort(int[] arr , int start, int end){
    	//우선 partitioning을 마치고, 시작점을 반환받는다.
        //여기서 처음 전배열을 한번 파티셔닝(+Sort)을 진행하고, 오른쪽 왼쪽 나눠서 재귀를 반복할 것을 기억하자.
        int partition = partition(arr,start,end);
        
        
        //전달 받은 partition 후의 기준점을 기준으로 앞,뒤 배열을 나누어 다시 재귀 정렬한다.
        //왼쪽배열 Sorting(재귀)
        if(start < partition-1){
        	quickSort(arr,start,partition-1);
        }
        //오른쪽 배열 Sorting(재귀)
        if(end > partition){
        	quickSort(arr,partition,end);
        }
    }
    
    static int partition(int[] arr, int start, int end){
    	//본인은 pivot을 중간으로 둔다.
        int pivot = arr[(start+end)/2];
        
        //이제 start가 end와 만나기 전까지 반복하여 Sorting할 것이다.
        while(start<=end){
        	//start 위치 한칸씩 움직이기
            while(arr[start] < pivot){ start++; }
            //end 위치 한칸씩 움직이기(끝에서 부터니까 --)
            while(arr[end] > pivot){ end--;}
            
            //pivot을 기준으로 start와 end가 다 움직이고 나면, 서로 위치를 바꿀 start와 end가 구해진다.
            if(start <= end){
            	swap(arr, start, end);
                //한칸씩 또 움직이도록 설정
                start++;
                end--;
            }
        }
    }
    
    static void swap(int[] arr, int start, int end){
    	int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }

}

알고리즘의 개념 자체는 간단하지만,

구현하는데 있어 머리를 조금 써야되는 알고리즘 같다...

제발 안까먹길 ~ㅎㅎ