[정렬] 퀵 정렬(Quick Sort)

☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다.

 

■ 퀵 정렬

원리 ) 중심점(Pivot Point)을 임의로 고른 후
       이 중심점보다 작은 수를 한 쪽으로 분류하고, 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법
       * 분할과 정복

- 중앙값 정렬 방식을 확장하여 개발한 방식.

- 평균 정렬 결과가 필요할 때 사용하는 것이 좋다.

- 퀵 정렬은 멀리 있는 값을 서로 비교하고 교환하기 때문에 안정성은 떨어진다.

- 시간 복잡도 O(n log n) 

 

※ 피벗을 중간 또는 마지막을 잡는 이유 :

- 피벗은 첫번째, 중간, 마지막 인덱스나 랜덤으로 선정 가능하다.

- 무엇을 피벗으로 잡느냐에 따라 처리 시간이 달라진다.

- 피벗 값이 중간 크기일 수록 더 균등하게 리스트를 분할 할 수 있다.

 

■ 재귀적인 퀵 정렬 (배열 사용)

package _02_정렬;

import java.util.Arrays;

public class _00_QuickSort3_안보고구현하기 {
	
	//오름차순 퀵소트 메소드를 구현하라
	private static void quickSortAsc(int[] arr, int left, int right) {
		int pl = left;
		int pr = right;
		int pivot = arr[(pl + pr)/2];
		
		//피봇 값을 기준으로 좌우를 정렬
		while (pl <= pr) {
			while (arr[pl] < pivot) pl++; //큰값이 나올때까지
			while (arr[pr] > pivot) pr--; //작은값이 나올때까지
			
			if (pl <= pr) {
				swap(arr, pl, pr); //교환하고
				pl++; //다시 커서 이동
				pr--;
			}
		}
		
		//재귀를 사용해 분할&정렬을 반복한다. (이 시점에서 pr < pl)
		if (left < pr) { //1개 이상일 때 
			quickSortAsc(arr, left, pr);
		}
		
		if (pl < right) {
			quickSortAsc(arr, pl, right);
		}
		
	}
	
	//내림차순 퀵소트 메소드를 구현하라
	private static void quickSortDes(int[] arr, int left, int right) {
		int pl = left;
		int pr = right;
		int pivot = arr[(pl + pr)/2];
		
		//피봇 값을 기준으로 좌우를 정렬
		while (pl <= pr) {
			while (arr[pl] > pivot) pl++; //작은값이 나올때까지
			while (arr[pr] < pivot) pr--; //큰값이 나올때까지
			
			if (pl <= pr) {
				swap(arr, pl, pr); //교환하고
				pl++; //다시 커서 이동
				pr--;
			}
		}
		
		//재귀를 사용해 분할&정렬을 반복한다. (이 시점에서 pr < pl)
		if (left < pr) { //1개 이상일 때 
			quickSortDes(arr, left, pr);
		}
		
		if (pl < right) {
			quickSortDes(arr, pl, right);
		}
	}
	
	//교환 메소드
	static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}
	
	//랜덤 메소드
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		quickSortAsc(arr, 0, arr.length-1);
		
		System.out.println(Arrays.toString(arr));
		
		quickSortDes(arr, 0, arr.length-1);
		
		System.out.println(Arrays.toString(arr));
		
	}

}

>> 결과

[1, 7, 5, 10, 2, 4, 3, 8, 9, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

//엔지니어 대한민국 방식
private static void quickSort(int[] arr) {
    quickSort(arr,0,arr.length-1);
}

private static void quickSort(int[] arr, int start, int end) {
    int part2 = partition(arr, start, end);
    if (start < part2 - 1) { //오른쪽 파티션이 왼쪽 파티션보다 1개 보다 더 많이 차이날때
        quickSort(arr, start, part2 - 1);
    }
    if (start < end) { //오른쪽 파티션이 1개 이상일 때
        quickSort(arr, part2, end);
    }
}

private static int partition(int[] arr, int start, int end) {
    int pivot = arr[(start + end) / 2];
    while (start <= end) {
        while (arr[start] < pivot) start++;
        while (arr[end] > pivot) end--;
        if (start <= end) {
            swap (arr, start, end);
            start++;
            end--;
        }
    }
    return start;
}

private static void swap(int[] arr, int start, int end) {
    int tmp = arr[start];
    arr[start] = arr[end];
    arr[end] = tmp;
}

private static void printArray(int[] arr) {
    for (int data : arr) {
        System.out.print(data + ",");
    }
    System.out.println();
}

 

■ 비재귀적인 퀵 정렬 (ArrayList or Stack 사용)

//알고리즘과 자료구조 방식
public static <T extends Comparable<? super T>> List<T> quicksort(List<T> list)
{
    if (list.size() <= 1) return list;

    int pivot = list.size() / 2;

    List<T> a = new ArrayList<T>(); //lesser
    List<T> b = new ArrayList<T>(); //greater

    int c = 0; //same

    for (T number : list) {
        if (list.get(pivot).compareTo(number) < 0) //-1, number > pivot
            b.add(number);
        else if (list.get(pivot).compareTo(number) > 0) //+1, number < pivot
            a.add(number);
        else
            c++;
    }

    a = quicksort(a);
    for (int i = 0; i < c; i++) {
        a.add(list.get(pivot));
    }

    b = quicksort(b);

    List<T> sorted = new ArrayList<T>();
    sorted.addAll(a);
    sorted.addAll(b);
    return sorted;

}

 

 

[출처]

- 부스트코스, 자바로 구현하고 배우는 자료구조

- 유투브, 엔지니어 대한민국, 퀵정렬에 대해 알아보고 자바로 구현하기

- 책, [그림으로 정리한 알고리즘과 자료구조], 조민호 지음

- 책, [do it 자료구조와 함께 배우는 알고리즘 입문]