퀵정렬 (quick sort) 을 간단하게 알아보자.

 

퀵 정렬을 간단하게 설명하면?

분할 정복을 이용한 가장 빠른 정렬!

 

1. 임의의 피봇을 정한 뒤 피봇의 위치를 확정해가며 정렬하는 구조입니다. 
2. 최초의 피봇을 정한 뒤 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 배열합니다.
3. 피봇을 기준으로 왼쪽 퀵 소트, 오른쪽 퀵 소트를 진행합니다.
4. 위의 과정은 분할과정과 정복과정으로 나누어지며 순환적인 형태를 띠고 있습니다.

 

 

 

구현 과정 - 1 (pivot을 end로 설정)

import java.util.*;
public class Main {
	
	static void quicksort(int[] A, int start, int end) {
		if(start<end) {          //start인덱스가 end인덱스보다 작으면 정렬할 배열이 남아있음을 의미.                               
			int index = partition(A, start, end);     //index를 기준으로 작은값과 큰 값으로 나눔.
			quicksort(A, start, index-1);               //index보다 작은 값들을 quicksort
			quicksort(A, index+1, end);                //index보다 큰 값들을 quicksort
		}
		else             //start가 end보다 작지 않은 경우는 더이상 정렬할 배열이 남아있지 않음을 의미.
			return;                 //재귀함수를 빠져나가기 위해 return 
	}
	
	static int partition(int[] A, int start, int end) {
		int pivot=A[end];          //임의로 피봇을 마지막 배열로 설정.
		int index=start;           //인덱스는 시작점으로. pivot보다 작은 값은 index와 스왑됨. index위치에는 마지막에 pivot값이 들어옴.
		int temp;
		
		for(int i=start; i<end; i++) {     //i는 start부터 시작하도록함.  
			if(A[i]<=pivot) {          //start부터 배열을 탐색해서 pivot보다 크지 않을 경우 
				temp=A[i];             //index위치와 스왑한다. 
				A[i]=A[index];
				A[index]=temp;
				index++;         //인덱스 자리에 스왑된 값이 들어왔으므로 index는 다음 칸으로.
			}
		}
		temp= A[index];                     //모든 탐색이 끝면 pivot값(A[end])을 현재 index자리 값과 스왑. 
		A[index]=A[end];                   //현재 index를 기준으로 왼쪽은 pivot보다 작은값, 오른쪽은 큰값으로 정렬이 되어 있기 때문.
		A[end]=temp;                         
		return index;                         //index(현재 pivot값이 들어있는 배열)리턴
	}
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		quicksort(A,0,A.length-1);
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

 

 

구현 과정 - 2 (기본)

import java.util.*;
public class Main {
	
	public static void quicksort(int[] A, int start, int end) {
		if(start<end) {             
			int index = partition(A,start,end);
			quicksort(A,start,index-1);
			quicksort(A,index+1,end);
		}
		else
			return;
	}
	
	public static int partition(int[] A, int start, int end) {
		int pivot = A[start];       //피봇은 start배열의 값으로. 피봇은 아무거나 해도 노상관. 
		
		while(start<end) {      //start가 end보다 작은 동안. =등호가 안 붙은 이유: start와 end위치가 같으면 비교하는 의미가 없음.
			while(A[start]<pivot && start<end)   //start부터 pivot보다 작고 start<end인 경우에만 start를 증가시킨다.
				start++;                        
			while(A[end]>pivot && start<end)     //end부터 pivot보다 크고 start<end인 경우에만 end를 감소시킨다.
				end--;           //start<end가 붙는 이유: 붙지않으면 계속 증가됨. 시간낭비. 
			                                                
			if(start<end) {               //붙지않으면 start==end일때 실행함. 낭비.
			int temp = A[start];          //start와 end위치의 배열을 스왑한다. 
			A[start] = A[end];
			A[end] = temp;
			}
		}
		return start;   //모든 반복이 끝나면 start 반환. (start 왼쪽은 작은 수, 오른쪽은 큰 수로 배열됨.)
	}
	
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		quicksort(A,0,A.length-1);
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

Random Pivot

int ran= start+(int)(Math.random()*10) % (end-start+1);
//start+ : 난수는 최소한 start이상이여야함.
//%(end-start+1) : +1를 해주어야 0~(end-start) 사이의 나머지 값이 나옴.  


//구현과정 -1 
int ran= start+(int)(Math.random()*10) % (end-start+1);
int temp;
temp=A[ran];
A[ran]=A[end];
A[end]=temp;



//구현과정 -2
int ran = start+(int)(Math.random()*10) % (end-start+1);
int pivot = A[ran]; 

 

 

시간 복잡도 

• Worst : O(n^2)
• Average : O(nlogn)
• Best : O(nlogn)