알고리즘 - 퀵정렬

 

- 호어 파티션 방식

import java.util.Arrays;

public class 퀵정렬_호어파티션 {
	static int[] arr;
	static boolean[] flag;
	public static void main(String[] args) {
		arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5};	
		flag = new boolean[arr.length];
		
		hoare(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		}
		
	public static void hoare(int[]arr, int left, int right) {
		//피봇 정하기(이 경우 제일 왼쪽값으로 정한 것.)
		int pivot = arr[left];
        //왼쪽 포인터 인덱스 지정 : pivot보다 큰 값을 찾아가는 포인터
		int l = left +1;
        //오른쪽 포인터 인덱스 지정 : pivot보다 작은 값을 찾아가는 포인터
		int r = right;
		int finish = 0;
        
        //왼쪽과 오른쪽이 교차되지 않은 동안만 동작
		while(l<=r) {
        	//왼쪽포인터는 pivot보다 작으면 지나침
			while(l<=r && arr[l]<=pivot) {
				l++;
			}
            //오른쪽 포인터는 pivot보다 크면 지나침
			while(l<=r && arr[r]>pivot) {
				r--;
			}
            //위 while문을 다 돌고도 l<r이면 l과 r의 arr원소 바꾸고 또 while문 반복
			if(l<r) swap(l, r);
		}
		
        //위 while문이 끝났다는건 l과 r이 교차됐다는 뜻이자, 
        //배열이 pivot보다 (작거나 같은 값들)(큰값들)의 묶음으로 정렬되었다는 뜻.
        //pivot은 맨 앞에 있으므로 자기보다 작은애랑 자리를 바꿔야 위의 묶음 정렬을 해치지 않으며
        //pivot보다 작은 값을 찾던 pointer는 r이므로 r과 swap
		swap(left, r);
	
	
        //r이 left+1보다 크거나 같다는 건 왼쪽에 더 정렬할 원소가 2개 이상 남았다는 뜻이므로 정렬
		if(r>=left+1) hoare(arr,left,r-1);
        //오른쪽에 정렬할 원소가 남았는지 체크하고 정렬
		if(r<=right-2) hoare(arr,r+1, right);
		
	}
	
	
	public static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

- 로무토 파티션 방식1

package Silver5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_24090퀵2 {
	static int N;
	static int K;
	static int[] arr;
	static int cnt;
	static boolean flag;
	static String answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		cnt = 0;
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		sort(0, N - 1);
		if (!flag) {
			System.out.println(-1);
		}else {
			System.out.println(answer);
		}

	}

	public static void sort(int left, int right) {
		if(left<right) {
			int q = partition(left, right);
			sort(left, q-1);
			sort(q+1, right);
		}
	}
	public static int partition(int left, int right) {
		int pivot = arr[right];
		int i = left - 1; // pivot보다 작거나 같은 원소들의 끝지점을 가리킬 포인터
		for (int j = left; j < right; j++) {
			if (arr[j] <= pivot) {
				i++;
				swap(i, j);

			}
		}
		if (i + 1 != right) {
			swap(i+1, right);
		}
		return i + 1;

	}

	public static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		cnt++;
		if (cnt == K) {
			if (arr[i] <= arr[j]) {
				answer = String.valueOf(arr[i]) + " " + String.valueOf(arr[j]);
			} else {
				answer = String.valueOf(arr[j]) + " " + String.valueOf(arr[i]);
			}
			flag = true;

		}
	}
}

- 로무토파티션 방식2

import java.util.Arrays;

public class 퀵정렬_로무토파티션 {
	
	static int[] arr;
	static boolean[] flag;
	public static void main(String[] args) {
		//언제? //
	arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5};	
	flag = new boolean[arr.length];
	
	lomuto(arr, 0, arr.length-1);
	System.out.println(Arrays.toString(arr));
	}
	
	
	public static void lomuto(int[] arr, int left, int right) {
		int pivot = arr[right];
		int i = left -1;
		int finish =0; 
		for(int j=left; j<right; j++) {
			if(arr[j]<=pivot) {
				i ++;
				swap(i, j);
			}
		}
		swap(i+1, right);
		flag[i+1] = true;
		for(int k=0; k<flag.length; k++) {
			if(flag[k]) finish++;
			
		}
		if(finish == flag.length) return;
		finish = 0;
		
		if(i>left) lomuto(arr, left, i);
		if(i+1<=right-2) lomuto(arr, i+2, right);
		
	}
	
	public static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
 }