[JAVA] Quick 정렬을 사용한 오름 차순 정렬

알고리즘 공부를 시작하자마자 난관이다. ㅎㅎ 그래도 잘 정리하고 공부하다보면 언젠가는 된다고 생각한다.

일단 정리해보자.

 

Quick 정렬은 값을 두 부분으로 나누어 각각 함수를 적용해 정렬을 한 다음 결과를 합치는 방식이다.

그렇기 때문에 속도는 데이터가 복잡하게 얽혀있을 수록 훨씬더 빠르게 처리하는 효과를 볼 수 있다.

만일 데이터가 정렬이 잘 되있는데 잘못된 한, 두개를 찾는다면 이 정렬방식은 오히려 불필요한 연산을 더 하게 되므로 적합하지 않다.

 

오늘은 복잡하게 엉킨 숫자를 오름차순으로 깔끔하게 정렬하는 알고리즘을 공부해 보겠다.

 

먼저 아래와 같은 배열이 있다고 가정하고, 배열안에 숫자를 정렬해보자.

int[] array={2,5,4,6,8,10,1,7,9,3};

 

이제 함수를 정의하고, 필요한 변수들을 정의해 준다.

• 먼저 Quick 정렬은 두 부분으로 나누기 위한 기준값(pivot)이 필요한데 이 기준값은 주어진 배열에 맨 처음값으로 잡는다.
• 그리고, 기준값 바로 뒤의 값(start+1)부터 기준값과 비교해야 함으로 이를 위한 인덱스용 변수 i를 정의하고,
• 기준값과 맨 뒤(end)에서부터 시작해서 왼쪽으로 하나씩 비교할 인덱스용 변수 j를 정의한다.
• 마지막으로 값의 크기를 비교해서 앞에 값이 뒤에값보다 클 경우 서로 바꿔줘야 함으로 바꿀때 잠시 담아줄 temp값을 정의해준다. 

public void quickSort(int[] data, int start, int end){

int pivot = start;
int j = end;
int i = start + 1;
int temp;

}

그리고, 시작 인덱스가 끝 인덱스보다 커지면 안되기 때문에 조건을 걸어주자.

public void quickSort(int[] data, int start, int end){

	if(start >= end){
		return;
	}
    
    int pivot = start;
    int j = end;
    int i = start + 1;
    int temp;

}

그리고 앞의 값과 끝에서의 값을 읽어들이면서 값이 엇갈릴 때까지 반복하도록 while문 처리를 해준다.

public void quickSort(int[] data, int start, int end){

	if(start >= end){
		return;
	}
    
    int pivot = start;
    int j = end;
    int i = start + 1;
    int temp;
	
    while(i <= j) {
    	
    }
}

이제 기준값과 다음값이 큰값이 올때 까지 비교하도록 아래와같이 while문 처리를 해준다. 

이때, 비교하는 앞의값 인덱스 i 가 배열의 끝의값 인덱스 end보다 작거나 같을때까지로 처리를 해주지 않으면, i의 값은 기존 배열에 존재하는 인덱스 값보다 커지게되고, data[i]에서 에러를 발생시킨다. 

 

그리고, 기준값보다 끝에 값이 작을때까지 비교하도록 while문 처리를 해준다.

이때, 끝에서 비교해 내려오는 인덱스값 j가 시작인덱스보다 작아지면 비교하는 값을 넘어서 내려가게 되므로 조건문에 추가로 넣어줘야 한다.

public void quickSort(int[] data, int start, int end){

	if(start >= end){
		return;
	}
    
    int pivot = start;
    int j = end;
    int i = start + 1;
    int temp;
	
    while(i <= j) {
    	while(data[i] < data[pivot] && i <= end){
        	i++;
        }
        while(data[pivot] < data[j] && j > start){
        	j--;
        }
    }
}

값을 체크하면서 인덱스의 숫자가 서로 엇갈릴때 기준값과 작은값의 위치를 바꿔주고, 아닐때는 큰값과 작은 값을 바꿔준다.

public void quickSort(int[] data, int start, int end){

	if(start >= end){
		return;
	}
    
    int pivot = start;
    int j = end;
    int i = start + 1;
    int temp;
	
    while(i <= j) {
    	while(data[i] < data[pivot] && i <= end){
        	i++;
        }
        while(data[pivot] < data[j] && j > start){
        	j--;
        }
    	//값이 엇갈리면 키값과 교체
        if(i > j) {
            temp=data[j];
            data[j]=data[key];
            data[key]=temp;
        }else {
            temp=data[j];
            data[j]=data[i];
            data[i]=temp;
        }
    }
}

마지막으로 엇갈려서 기준값의 위치를 바꿧으므로 바뀐 위치의 인덱스를 기준으로 좌, 우 측 분할하여 같은 작업을 수행해야 하므로, 아래와같이 함수안에 함수를 호출하는 재귀함수문을 사용하고, start와 end 는 j값을 기준으로 지정해 주면 된다.

public void quickSort(int[] data, int start, int end){

	if(start >= end){
		return;
	}
    
    int pivot = start;
    int j = end;
    int i = start + 1;
    int temp;
	
    while(i <= j) {
    	while(data[i] < data[pivot] && i <= end){
        	i++;
        }
        while(data[pivot] < data[j] && j > start){
        	j--;
        }
    	//값이 엇갈리면 키값과 교체
        if(i > j) {
            temp=data[j];
            data[j]=data[key];
            data[key]=temp;
        }else {
            temp=data[j];
            data[j]=data[i];
            data[i]=temp;
        }
    }
    	quickSort(data,start,j-1);
	quickSort(data,j+1,end);
}

값을 테스트 해보자. 

public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] data = {1,10,5,8,7,6,4,3,2,9};
		quickSort(data,0,9);
		
		for(int i=0; i<10; i++) {
			System.out.print(data[i]+",");
			
		}
		
	}

 

결과값