[ 정렬 알고리즘 ] 퀵 정렬 java

백준 문제를 풀다가 정렬을 할 떄 내가 아는 버블 정렬이나, 삽입 정렬을 하게되면 시간 초과가 떠서 정렬 알고리즘에 대해 한 번 공부해보았다.

 

정렬 알고리즘 시간 복잡도

 

[1] 퀵 정렬

피벗값을 임의로 정해, 이보다 작은 수들은 왼쪽, 큰 수는 오른쪽으로 나눈 후,

나눠진 파트 안에서 또 피벗을 정하고, 작은 수 큰 수 모음으로 나누기.

각각 낱개로 하나씩으로 나눠질때까지 이를 반복.

 

퀵 정렬 하는 법 및 예시

 

 

 

 

★참고영상

[자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기

https://www.youtube.com/watch?v=7BDzle2n47c 

 

 

퀵 정렬 Java로 구현하기

public class Sort {
	
	public static void QS(int a[], int l, int r) {
		
		int pl=l;
		int pr=r;
		int p=a[(pl+pr)/2];
		
		do {
			while(a[pl]<p) pl++;
			while(a[pr]>p) pr--;
			
			if(pl<=pr) {
				//스왑
				int temp=a[pl];
				a[pl]=a[pr];
				a[pr]=temp;
				
				pl++;
				pr--;
			}
		} while(pl<=pr);
		
		if(l<pr) QS(a,l,pr);
		if(r>pl) QS(a,pl,r);
	}
	
	public static void main(String[] args) {
		
		int [] a = {1,4,2,5,6};
        int n = a.length;
		
		QS(a, 0, n-1);	
		
		
		for(int i=0; i<n; i++) {
			System.out.println(a[i]);
		}
		
		
		
	}

}

 

(다른 방법)

public class QuickSort {
    
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n-1);
        System.out.println("Sorted array:");
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
    }
    
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex-1);
            quickSort(arr, pivotIndex+1, high);
        }
    }
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j=low; j<high; ++j) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        return i+1;
    }
}