퀵 정렬(Quick Sort), 퀵 셀렉트

public class QuickSort {
	public static void main(String[] args) {
		int[] a = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		quickSort(a, 0, a.length - 1);
		System.out.println(Arrays.toString(a));
		System.out.println("-----------------------------");
		int[] b = {10,70,20,30,40};
		int p=quickSelect(b, 1, 0, b.length-1);
		System.out.println("정렬되지 않는 배열에서 두번째로 작은 값 : " + p);
	}

	public static void quickSort(int[] a, int left, int right) {
		if (right - left <= 0) {
			return;
		}
		int pivot_position = partition(a, left, right);

		quickSort(a, left, pivot_position - 1);
		quickSort(a, pivot_position + 1, right);
	}

	public static int quickSelect(int[]a,int kth_lowest_value,int left,int right) {
		if(right-left<=0) {
			return a[left];
		}
		int find=0;
		int pivot_position=partition(a, left, right);
		if(kth_lowest_value<pivot_position) {
			find=quickSelect(a, kth_lowest_value, left, pivot_position-1);
		}else if(kth_lowest_value>pivot_position) {
			find=quickSelect(a, kth_lowest_value, pivot_position+1, right);
		}else {
			return a[pivot_position];
		}
		return find;
	}
	public static int partition(int[] a, int left, int right) {
		int pivot_position = right;
		int pivot = a[pivot_position];

		right -= 1;
		while (true) {
			while (a[left] < pivot) {
				left++;
			}
			while (a[right] > pivot) {
				right--;
				if(right<0) {
					break;
				}
			}
			if (left >= right) {
				swap(a, left, pivot_position);
				break;
			} else {
				swap(a, left, right);
			}
		}
		return left;
	}

	private static void swap(int[] a, int left, int right) {
		int tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
	}
}

퀵 정렬은 이전 포스트에서 다루었고

 

퀵 셀렉션을 설명

 

책에는 루비로 되어 있어 헷갈렸다.

 

루비에서는 int find=0이런 변수를 두지 않고 재귀를 빠져나오면서 

 

마지막 return 값을 써두지 않아도 에러가 나지 않는가보다. 

 

자바에서는 find에 값을 저장해주고 기저조건으로 재귀를 나오게 될 때 find에 값을 저장시켜두고 그걸 리턴시켜 

 

값을 얻어낸다. 

 

		int find=0;
		int pivot_position=partition(a, left, right);
		if(kth_lowest_value<pivot_position) {
			find=quickSelect(a, kth_lowest_value, left, pivot_position-1);
		}else if(kth_lowest_value>pivot_position) {
			find=quickSelect(a, kth_lowest_value, pivot_position+1, right);
		}else {
			return a[pivot_position];
		}
		return find;

이 부분이 어려웠는데 간단했다. find변수에 찾은 값을 계속 저장시켜서 return하면 된다. 

 

다만 문제점이 있다. 이거는 아직 해결을 못 했는데, 배열에 중복된 데이터가 있는 경우 무한 반복에 빠지게 된다. 

 

책을 잘 옮기지는 못한 거 같다. 

https://twinparadox.tistory.com/160