퀵정렬 설명과 함께 작성한 코드

수업 중 설명드렸던 퀵정렬 코드와 함께 설명을 추가한 버전

둘 중 편한 버전으로 보셔요 같은 내용입니다.

package test;

public class Loop {
	
	 public static void main(String[] args) {
	      int[] list = new int[10];//

	      for(int i = 0 ; i < 10 ; i++ ) {
	         list[i] = (int) (Math.random()*100)+1;//임의의수 10개를 고름
	         System.out.print(list[i]+" ");
	      }
	      sort(null, 0, list.length-1);
	      System.out.println("\n===========================");
	      for(int i = 0 ; i < 10 ; i++ ) {
	         System.out.print(list[i]+" ");
	      }
	 }


	      private static void sort(int[] num,int l, int r) {

	          int pivot = num[(r+l) / 2];						// 배열의 중간 인덱스의 "값"(value)가 비교값(pivot)으로 할거에요.

	          while(l<=r) {										// 투 포인터로 l(left), r(right)를 사용할거에요.
	        	  												// left는 right를 넘어가면 의미가 없어져요. 그렇다면 제외할거에요.
	        	  												// left는 right와 교환하는 것이 역할이에요. right도 그렇구요. 그러니까 둘은 위치가 바뀌면 의미가 없어져요.
	        	  												// while문의 조건은 true일때 내부의 반복문이 수행돼요. l은 시작부터 시작하니 0으로 시작하고, 조건에 맞는 값까지 내부에서 증가시킬거에요.
	        	  												// while은 false가 나면 loop가 종료되지만, loop의 시작시점에 판단하고 이후에 값이 바뀐다고 중간에 종료되지 않아요.

	        	 while(pivot>=num[l] && num.length-1>=l) {		// 특정한 값으로 설정한 pivot과 비교해, l(left)포인터가 가리키는 값이 pivot보다 크면 r(right)포인터가 가리키는 값과 바꿀 준비를 해요.
	        		 											// pivot은 값을 루프전에 세팅하고, 그 값과 비교해 더 작은값과(left) 더 큰 값(right)을 바꾸면
	        		 											// 결과적으로 전체 배열은 어느 시점을 기준으로 pivot을 기준으로 더 작은 값과 더 큰값으로구분되게 돼요.
	        		 											// ex) pivot이 임의의 기준으로 5일때, 3 2 1 5 9 처럼 순서는 보장되지 않아도 기준값으로 구분돼요 ( 물론, 몇 개 뽑아 평균을 내면 요소(elemnet)중에 일치하는 값이 없을수도 있어요
	        		 											// l(left)이 특수한 상황에 따라 배열의 끝값까지 갈 수 있어야 하기 때문에 ( 0 0 0 0 0 )
	        		 											// 배열의 끝 ( num.length-1 ) 까지 갈 수 있어야해요
	        		 											// 그리고 r(right)와 바꿔야하는 순간이 올때는 지금의 바깥루프 ( while(l<=r) ) 의 한 루프안에서는 바깥으로 나가야하기 때문에
	        		 											// pivot(기준값)보다 크면 r과 바꿔야 하기때문에 l(left)가 가리키는 값을 pivot(기준값)보다 작거나 같아야 해요
	        		 											/*
																	3 2 3 으로 배열이 있어요. 이때 pivot을 3으로 한다면
																	L   R 일때,
																	L을 다루는 while에서는 pivot과 같을경우 처음의 3을 통과하고, 다음 2는 left에 있어야하니 통과하고, 마지막칸인 3에 멈출거에요.
																	R을 다루는 while에서도 pivot과 같은 경우인 3을 통과하고, 2는 left로 가야하기때문에 멈출거에요.
																	
																	3 2 3
																	  R L
																	이렇게 될거에요. 그렇다면 이때는 두 값을 바꾸면 안돼요. 2는 pivot인 3보다 작으니까 왼쪽으로 가야하는데 L은 3이고, 2보다 크기때문에 결국 요건이 안맞아요
																	이땐 가장 바깥의 while(l<=r)처럼 l이 더 커지면 교환을 하면 안돼요.
																	그렇다고 R, L에서 값을 따로 비교해서 이걸 다음 분할의 분기로 삼기 명확하지 않아요.
																	
																	그러면 R을 다루는 while에서 pivot과 같은 경우 통과하지 않는다면 처음의 3에 멈출거니
																	3 2 3
																	    L
																	    R
																	이렇게 되고, 이때의 L과 R의 index를 다음 분기의 분기점 (pivot)으로 하면 이 3을 기준으로 왼쪽은 같거나 작은 값들이 존재하게 되고, 여기서 정렬하게 되면 이후에 2 3 3이 성립하게 될거에요.       
																	
																																	    
																	반대로,
																	3 4 3 으로 배열이 있어요, 이때도 pivot을 3으로 한다면
																	L   R 일때,
																	L을 다루는 while에서는 pivot과 같을경우 통과하니 처음 3을 통과하고, 4에서 멈출거에요.
																	R을 다루는 while에서는 pivot과 같을경우 통과하면 처음의 3을 통과하고, R은 pivot보다 작은값에 멈출테니 배열의 끝인 왼쪽의 3에서 멈추게 될거에요
																	
																	3 4 3
																	R L 
																	이렇게 되고, 이땐 값을 바꾸면 더 큰값인 4가 왼쪽으로 가고 그렇다고 멈추기에는 다음 분기의 pivot을 정하기도 불확실해져요.
																	
																	대신, R을 다루는 while에서 pivot과 같은경우 멈추게 설정하면
																	3 4 3
																	  L
																	    R
																	이 되고, 둘의 요건이 맞으므로 ( L은 pivot보다 더 큰값, R은 pivot    
																	
																
	        		 											 */
	                //피벗을 기준으로 피벗보다 오른쪽을 포인터 하지 못하도록 조건을 걸어줌
	                l++;
	             }
	             while(pivot<=num[r] && r>=0) {//피벗의 왼쪽에는 피벗보다 작은 값이 정렬되도록 하기위해서, 피벗보다 큰 값이 나올때까지 반복(같으면 넘어감)
	                r--;
	             }

	             swap(num, l, r);

	          }




	       }

	       public static void swap(int[] num,int l, int r) {
	          //피벗을 기준으로 오른쪽 값고 왼쪽값을 바꾸는 함수
	          int temp = num[l];
	          num[l] = num[r];
	          num[r]= temp;

	       }

	       public static void partition() {


	       }

	      
}