idea

엇갈리지 않으면, 큰 놈과 작은놈을 바꾸어 준다 -> 큰쪽과 작은 쪽을 분리해준다. 그래서 좌우에 대해서 recurse를 걸어준다.

-> 왼쪽에서부터 큰놈, 오른쪽에서부터 작은놈을 찾는다. index가 엇갈리면 정렬이 됐다는 얘기이므로 작은 놈의 값과 pivot값을 바꾸어준다.

헷갈렸던 점

１. quick function의 return 값을 array로 잡을지 void로 잡을지 헷갈렸다. main에서 void quick에 data array를 넘겨주었을 때 data의 값이 바뀌는지 바뀌지 않는지 헷갈렸다.

   public static void main(String args[]){
        int[] data = {3,2};

        test(data,232,433);
        System.out.println(data[0] + " " + data[1]);
    }

    static void test(int[] data,int a,int b){
        data[0] = a;
        data[1] = b;
    }

-->바뀐다. array와 method에 대해서 헷갈리지 않으면 당연한 얘기.

２. 멈추기

3 5 2 1 6

-> 큰놈 , -> 5, 작은놈 2 발견하면 멈추어야 하는데 어떻게 멈추지? 그래서 stack을 사용해서 멈춰야겠다 라고 생각했는데 복잡해지고, 작동도 하지 못했음. 그 이유는 for loop만 사용해서 구현하려고 했어서 그런 것. for loop는 한 변수에 대해서만 조건을 표시할 수 있지만, while은 while loop 안에 다른 변수의 증감도 조건에 영향을 줄 수 있음.

ex) While data[left]<= data[pivot]
          left ++

３. start, end 값이 왜 필요하지 하고 안 썼었는데, 코드를 짜다보니 재귀를 이용하려면 start와 end값이 필요했음. 설계 -> 수도코드 -> 코드구현 에서 설계단계에서 정확히 짜지 못한 원인이라고 생각한다.

while / if

４. while / if

while(i<N)
i++

위와 같은 while loop가 있다면 i가 N보다 작을 때 까지만 돌리라 는 말로 해석하면 된다.
i가 N보다 클때까지 라고 해서 i>N 이라고 하면 안된다.
i가 N보다 클때까지 돌려야 하니까 i가 N보다 작을때까지만 돌려야 한다. while loop는 언제동안 돌릴 것인지에 대한 조건을 써주는 위치다.
ex)

while(i<10)
i++
--> i가 10보다 클때까지 i을 키우고 싶다. 
그러므로 i가 10보다 작을 때까지만 돌려라

즉 while 은 언어적 해석과 한 번 반대로 뒤집어서 생각하게 되는 것. 반대로 if는 직역이다.

if(i>10)
i++
--> i가 10보다 크다면. ( 직역 )

While -> i가 10보다 클때까지 돌리게 하고 싶다 : 반대
while(i<10)

５. 수학에서와 마찬가지로, 지나온 풀이에 대한 믿음이 있게 pseudo code를 짜야한다.

if N condition  <-- 일정 수준 이상의 값만 받는다
 while M condition <-- sort 해준다
  while J condition <-- 최대값을 추출해준다
   function X() <-- 값을 섞어준다
      --> [this turn]

위와 같이 코드를 짰다고 했을 때, 화살표 방향에서 코드를 짠다고 치면, 코드를 짜는 현재의 순서에서는 위의 단계가 다 됐다고 가정을 하고 코드를 짜야 한다. 그리고 혹시 무언가 잘못됐을 때 검증을 해야 하므로 기능별로 정리를 깔끔하게 해놓아야한다.

６. while loop, for loop는 기본적으로 거짓이면 빠져나오는 것이다. 참일 때는 계속 돈다.

while (data[pivot] > data[left] && left <= end) {
    left++;
}
while (data[pivot] < data[right] && right > pivot) {
    right--;
}

코드를 처음에 이렇게 짰었는데, 이러면 같은 값을 집어넣으면 거짓일때가 없어서 loop를 빠져나오지 못한다. 고로 =을 넣어주어야 한다.

pseudo code

pseudo code장으로 쓰기에 Dev C++이 아주 좋다. PlasticCodeWrap 테마 좋다.

quick(array data, int start, int end) {
	
	if(start>=end)
		return ;
	
Define left,right,temp,pivot

left=start+1
right=end
pivot=start

while left<right 
	while data[left] <= data[pivot] (A1)
		left++
	while data[right] >= data[pivot] (A2)
		right++
	if(left<right)
		switch data[left] data[right]
	else
		switch data[left] data[pivot]

Recurse quick(data,start,right-1)
Recurse quick(data,right+1,end)
	
}

--> A1, A2 위치에 left<end , right>start 같은 증감조건문에 대한걸 적어주지 않았다. 그리고 Recurse는 초기에 종료조건을 명시해주지 않으면 무한 loop를 돈다는걸 명심하자.

Code

package SortSeries;

public class QuickSortTry2 {
    public static void main(String args[]) {
        int[] data = {4, 112,23, 2412, 23, 43, 5, 7};
        quick(data, 0, data.length-1);
        for(int i:data){
            System.out.print(i + " ");
        }
    }

    static void quick(int data[], int start, int end) {

        if(start>=end){
            return ;
        }
        int left, right, temp, pivot;

        left = start + 1;
        right = end;
        pivot = start;

        while (left <= right) {
            while (data[pivot] >= data[left] && left <= end) {
                left++;
            }
            while (data[pivot] <= data[right] && right > pivot) {
                right--;
            }
            if (left < right) {
                temp = data[left];
                data[left]=data[right];
                data[right]=temp;
            }else{
                temp = data[pivot];
                data[pivot] = data[right];
                data[right] = temp;
            }
        }
        quick(data,start,right-1);
        quick(data,right+1,end);
    }
}