빠르고 좋다는 Quick 정렬 원리와 구현

QuickSort (퀵정렬)

퀵정렬은 구동방식이 생각보다 간단합니다!

일단 배열의 한 기준점을 기준으로 왼쪽에는 기준점보다 작은 값을, 오른쪽에는 큰 값을 정렬 하는것 입니다.

그리고 나서 왼쪽에는 기준점보다 작은값들이 모여있겠지요?? 다시 왼쪽에 있는 배열 데이터로만 하여금 위 과정을 반복하고 반복하다 보면,

더이상 기준점을 기준으로 비교할 대상이 남아있지 않게 되는겁니다. 그러면 배열정렬 끗!!!

이 방법을 곧 “분할 정복(Divide and Conquer) “ 이라고 합니다.

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 재귀 호출을 이용하여 구현한다.

퀵 정렬의 장단점:

• 장점: 당연히 속도가 빠르고, 시간복잡도가( nlogn) 을 갖는 다른정렬 알고리즘과 비교했을때도 매우 빠릅니다.
• 추가적인 메모리 공간을 필요로 하지않습니다. (퀵 정렬은 O(log n) 만큼의 메모리를 필요로 합니다.
• 단점: 만약에 리스트가 정렬이 되있다면 퀵 정렬의 불균형 분할에 의해 오히려 정렬시간이 더 많이 걸립니다.
• 그래서 최대한 기준점을 선택할때 데이터의 중간값을 설정하면 좋습니다.

---

QuickSort(퀵 정렬) JAVA 구현.

private static void quickSort(int[] arr) {.    // 배열의 정보를 받아서 본격적으로 재귀호출을 준비하는 메소드.
		quickSort(arr,0,arr.length-1); // 밑에 있는 quickSort 메소드로 재귀호출을 진행한다. 매개값은 배열과, 배열의 시작점과 끝 지점을 할당한다.
	}
	
	private static void quickSort(int[] arr, int start, int end) {  
		int part2 = partition(arr,start,end);    // 제일 먼저 분할을 해주는 partition메소드를 재귀호출을 해준다. 그리고 분할이 끝났다면 반환값으로 중앙값을 리턴한다.
		if(start < part2-1) {                    // 만약에 시작점이 중앙지점 보다 작다면 똑같아질때까지 재귀호출로 진행한다.
			quickSort(arr,start,part2-1); //보내준 start의 인덱스가 오른쪽 배열의 첫번째 시작점이기 때문에 -1을 해줬다.
		}
		if(end> part2) {
			quickSort(arr,part2,end);
		}
	}
	
	private static int partition(int[] arr, int start, int end) {   // 여기서 본격적인 swap으로 데이터를 변경시키고 분할 시키는 작업을 한다.
		int pivot = arr[(start+end)/2];      // 중앙인덱스의 데이터값을 피봇변수에 저장한다.
		while(start<=end) {                  // 시작점과 끝점이 서로 교차하지 않을때 까지만 반복한다.
			while(arr[start]<pivot) start ++;  // 시작점에 있는 데이터가 피봇값보다 작다면 계속해서 앞에 인덱스로 옮겨가며 비교해준다. 그러다가 큰 값이 나오면 잠깐 멈춘다.
			while(arr[end]>pivot) end --;      // 끝점에 있는 데이터가 피봇값보다 크다면 계속해서 옮겨가며 비교해주고, 그러다가 작은 값이 나오면 잠깐 멈춘다.
			if(start<=end) {                   // 잠깐 멈춰있는 인덱스번호를 기준으로 서로 swap을 해준다.
				swap(arr,start,end);
				start++;             // swap이 끝나면 계속해서 진행할수 있게 ++ -- 를 다시 시켜준다.
				end--;
			}
		}
		return start;         // 위 반복문을 탈출했다는 소리는 더이상 왼쪽에는 피봇값보다 큰게 없고, 오른쪽에는 작은게 없다는 뜻이다.
	}                       // 새로운 중간 인덱스를 부여하기 위해 start or end를 통해 return해준다. (여기서는 오른쪽 배열의 첫번째 인덱스인 start를 보냈다)
	
	
	private static void swap(int[]arr,int start, int end) {
		int temp=arr[start];
		arr[start]=arr[end];
		arr[end]=temp;
	}
	
	
	public static void disp(int[]arr) {
		for(int i : arr) {
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

처음에 코드 짤때 이걸 어떻게 짜????….

이러고 정말 현타가 와 있었는데 4시간 동안 계속 돌고돌아 짜고 삭제하고 하다보니 이젠 거의 외워질 정도로 이해를 해버렸다…..

아무래도 재귀호출과 리턴값을 부여해서 다시 재귀호출… 이게 좀 헷갈렸던거 같은데 이번에 퀵정렬 구현해보면서

많이 성장한거 같다 🙂