[알고 day2] 퀵정렬

퀵 정렬은 대표적인 '분할 정복'알고리즘으로 평균 속독 0(N * logN)이다. 특정값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반드로 나눈다. 기준 값은 피벗(Pivot)이라고 한다. 보통 첫 번째 원소를 피벗 값으로 설정해서 사용한다. 

'키 값보다 작은 값을 만날 때까지' 반복하게 되므로, j가 Start보다 클때에 한해서 반복문이 수행되도록 처리됨. 이는 항상 왼쪽에 있는 피벗값과 교환되기 때문이다. 퀵 정렬의 평균 시간 복잡도는 0(N*logN) 이다. 

#include <stdio.h>
int number =10;
int data [] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	
    void show() { 
		int i;
		for(i=0; i<number;i++){
			printf("%d", data[i]);
		}
	}

void quickSort(int* data, int start, int end){
	
	if(start >= end) { 
		return; 
	}
	int key = start; 
	int i = start + 1; 
	int j = end;  
	int temp; 
 	while(i <= j){
		while(i <= end && data[i] <= data[key]){ 		
			i++;
		} 
		while(j> start && data[j]>=data[key]){ 
			j--;		
		}
		if(i > j){ 
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;

		}else {   
			temp =  data[i];
			data[i] = data[j];
			data[j] = temp; 
		}
	 }
	quickSort(data, start, j - 1); 
	quickSort(data, j + 1, end);
}
int main(void) { 
	quickSort(data,0,number -1);
	show();
	return 0;
}  

주석버전

#include <stdio.h>
int number =10;
int data [] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};


	void show() { 
		
		printf("\n show 함수 실행\n");
		int i;
		for(i=0; i<number;i++){
			printf("%d", data[i]);
		}
	}
	
	//1, 10, 5, 8, 7, 6, 4, 3, 2, 9
void quickSort(int* data, int start, int end){ //void quickSort()함수가 종료할때까지 아무값도 리턴하지 않겠다. 
	
	if(start >= end) { //원소가 1개인 경우 그대로 두기  
		return; 
	}
	
	int key = start; //시작 기준// [0]값을Pivot 값으로 시작   
	int i = start + 1; 
	int j = end;  
	int temp; 
	
	printf("전체 wile문들어가기전 key값: %d\n",key);
	printf("전체 wile문들어가기전 i값(start값)): %d\n",i);
	printf("전체 wile문들어가기전 j값(end값)): %d\n",j);

 	while(i <= j){
 		
		 //1, 10, 5, 8, 7, 6, 4, 3, 2, 9
 		printf("--------------1번---------------\n");
		while(i <= end && data[i] <= data[key]){ //키 값보다 큰 값을 만날때까지//큰거 만나면 멈추고  
			printf("i:%d <= end:%d && data[i]값:%d <= data[key]:%d\n",i,end,data[i],data[key]);
			i++;
			printf("i값:%d\n",i);
		} 
		
		printf("--------------2번---------------\n");
		while(j> start && data[j]>=data[key]){//키값을 기준으로 오른쪽끝>>key값으로 이동하다 
											// 키보다 작은 값을 만날때까지 값--j 
			printf("j:%d > start:%d && data[j]값:%d >= data[key]:%d\n",j,start,data[j],data[key]);
			j--;		
			printf("j값:%d \n",j);
		}
		
		if(i > j){ //현재 엇갈린 상태(작은값의 인덱스번호<큰값의 인덱스 번호) 작은값을키 값과 교체
			printf("\n엇갈린상태- 키값과 교체\n");
			printf("key:%d, ",key); //처음에 1이 자기 자신과 자리르 바꿈 그래서 그대로 임  
			printf("i:%d, ",i);
			printf("j:%d\n",j);

			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
			
			printf("--현재배열"); 
			show();
			
		}else { //엇갈리지 않으면 i와 j를 교체//Start값이 End값보다 크다 >> 자리바꿈  
			printf("\n엇갈리지 않으면 i와 j를 교체\n"); 
			printf("key:%d, ",key);
			printf("i:%d, ",i);
			printf("j:%d\n",j);

			temp =  data[i];
			data[i] = data[j];
			data[j] = temp; 
		}
		show(); 
		printf("\n\n"); 
		
	 } 
	 
	printf("재귀함수1 시작전값: start:%d,j-1:%d\n",start,j-1); 
	quickSort(data, start, j - 1); //재귀함수  
	printf("**재귀함수1 끝나고 값: start:%d,j-1:%d\n",start,j-1); 
	
	printf("재귀함수2 시작 시작전 값:  j + 1:%d,end:%d\n",j + 1,end); 	 
	quickSort(data, j + 1, end);
	printf("**재귀함수2끝나고 값: j + 1:%d,end:%d\n\n",j + 1,end); 	 
	
}

int main(void) { 
	quickSort(data,0,number -1);
	show();
	return 0;
}  

실행순서

전체 wile문들어가기전 key값: 0
전체 wile문들어가기전 i값(start값)): 1
전체 wile문들어가기전 j값(end값)): 9
--------------1번---------------
--------------2번---------------
j:9 > start:0 && data[j]값:9 >= data[key]:1
j값:8
j:8 > start:0 && data[j]값:2 >= data[key]:1
j값:7
j:7 > start:0 && data[j]값:3 >= data[key]:1
j값:6
j:6 > start:0 && data[j]값:4 >= data[key]:1
j값:5
j:5 > start:0 && data[j]값:6 >= data[key]:1
j값:4
j:4 > start:0 && data[j]값:7 >= data[key]:1
j값:3
j:3 > start:0 && data[j]값:8 >= data[key]:1
j값:2
j:2 > start:0 && data[j]값:5 >= data[key]:1
j값:1
j:1 > start:0 && data[j]값:10 >= data[key]:1
j값:0

엇갈린상태- 키값과 교체
key:0, i:1, j:0
--현재배열
 show 함수 실행
11058764329
 show 함수 실행
11058764329

재귀함수1 시작전값: start:0,j-1:-1
**재귀함수1 끝나고 값: start:0,j-1:-1
재귀함수2 시작 시작전 값:  j + 1:1,end:9
전체 wile문들어가기전 key값: 1
전체 wile문들어가기전 i값(start값)): 2
전체 wile문들어가기전 j값(end값)): 9
--------------1번---------------
i:2 <= end:9 && data[i]값:5 <= data[key]:10
i값:3
i:3 <= end:9 && data[i]값:8 <= data[key]:10
i값:4
i:4 <= end:9 && data[i]값:7 <= data[key]:10
i값:5
i:5 <= end:9 && data[i]값:6 <= data[key]:10
i값:6
i:6 <= end:9 && data[i]값:4 <= data[key]:10
i값:7
i:7 <= end:9 && data[i]값:3 <= data[key]:10
i값:8
i:8 <= end:9 && data[i]값:2 <= data[key]:10
i값:9
i:9 <= end:9 && data[i]값:9 <= data[key]:10
i값:10
--------------2번---------------

엇갈린상태- 키값과 교체
key:1, i:10, j:9
--현재배열
 show 함수 실행
19587643210
 show 함수 실행
19587643210

재귀함수1 시작전값: start:1,j-1:8
전체 wile문들어가기전 key값: 1
전체 wile문들어가기전 i값(start값)): 2
전체 wile문들어가기전 j값(end값)): 8
--------------1번---------------
i:2 <= end:8 && data[i]값:5 <= data[key]:9
i값:3
i:3 <= end:8 && data[i]값:8 <= data[key]:9
i값:4
i:4 <= end:8 && data[i]값:7 <= data[key]:9
i값:5
i:5 <= end:8 && data[i]값:6 <= data[key]:9
i값:6
i:6 <= end:8 && data[i]값:4 <= data[key]:9
i값:7
i:7 <= end:8 && data[i]값:3 <= data[key]:9
i값:8
i:8 <= end:8 && data[i]값:2 <= data[key]:9
i값:9
--------------2번---------------

엇갈린상태- 키값과 교체
key:1, i:9, j:8
--현재배열
 show 함수 실행
12587643910
 show 함수 실행
12587643910

재귀함수1 시작전값: start:1,j-1:7
전체 wile문들어가기전 key값: 1
전체 wile문들어가기전 i값(start값)): 2
전체 wile문들어가기전 j값(end값)): 7
--------------1번---------------
--------------2번---------------
j:7 > start:1 && data[j]값:3 >= data[key]:2
j값:6
j:6 > start:1 && data[j]값:4 >= data[key]:2
j값:5
j:5 > start:1 && data[j]값:6 >= data[key]:2
j값:4
j:4 > start:1 && data[j]값:7 >= data[key]:2
j값:3
j:3 > start:1 && data[j]값:8 >= data[key]:2
j값:2
j:2 > start:1 && data[j]값:5 >= data[key]:2
j값:1

엇갈린상태- 키값과 교체
key:1, i:2, j:1
--현재배열
 show 함수 실행
12587643910
 show 함수 실행
12587643910

재귀함수1 시작전값: start:1,j-1:0
**재귀함수1 끝나고 값: start:1,j-1:0
재귀함수2 시작 시작전 값:  j + 1:2,end:7
전체 wile문들어가기전 key값: 2
전체 wile문들어가기전 i값(start값)): 3
전체 wile문들어가기전 j값(end값)): 7
--------------1번---------------
--------------2번---------------

엇갈리지 않으면 i와 j를 교체
key:2, i:3, j:7

 show 함수 실행
12537648910

--------------1번---------------
i:3 <= end:7 && data[i]값:3 <= data[key]:5
i값:4
--------------2번---------------
j:7 > start:2 && data[j]값:8 >= data[key]:5
j값:6

엇갈리지 않으면 i와 j를 교체
key:2, i:4, j:6

 show 함수 실행
12534678910

--------------1번---------------
i:4 <= end:7 && data[i]값:4 <= data[key]:5
i값:5
--------------2번---------------
j:6 > start:2 && data[j]값:7 >= data[key]:5
j값:5
j:5 > start:2 && data[j]값:6 >= data[key]:5
j값:4

엇갈린상태- 키값과 교체
key:2, i:5, j:4
--현재배열
 show 함수 실행
12435678910
 show 함수 실행
12435678910

재귀함수1 시작전값: start:2,j-1:3
전체 wile문들어가기전 key값: 2
전체 wile문들어가기전 i값(start값)): 3
전체 wile문들어가기전 j값(end값)): 3
--------------1번---------------
i:3 <= end:3 && data[i]값:3 <= data[key]:4
i값:4
--------------2번---------------

엇갈린상태- 키값과 교체
key:2, i:4, j:3
--현재배열
 show 함수 실행
12345678910
 show 함수 실행
12345678910

재귀함수1 시작전값: start:2,j-1:2
**재귀함수1 끝나고 값: start:2,j-1:2
재귀함수2 시작 시작전 값:  j + 1:4,end:3
**재귀함수2끝나고 값: j + 1:4,end:3

**재귀함수1 끝나고 값: start:2,j-1:3
재귀함수2 시작 시작전 값:  j + 1:5,end:7
전체 wile문들어가기전 key값: 5
전체 wile문들어가기전 i값(start값)): 6
전체 wile문들어가기전 j값(end값)): 7
--------------1번---------------
--------------2번---------------
j:7 > start:5 && data[j]값:8 >= data[key]:6
j값:6
j:6 > start:5 && data[j]값:7 >= data[key]:6
j값:5

엇갈린상태- 키값과 교체
key:5, i:6, j:5
--현재배열
 show 함수 실행
12345678910
 show 함수 실행
12345678910

재귀함수1 시작전값: start:5,j-1:4
**재귀함수1 끝나고 값: start:5,j-1:4
재귀함수2 시작 시작전 값:  j + 1:6,end:7
전체 wile문들어가기전 key값: 6
전체 wile문들어가기전 i값(start값)): 7
전체 wile문들어가기전 j값(end값)): 7
--------------1번---------------
--------------2번---------------
j:7 > start:6 && data[j]값:8 >= data[key]:7
j값:6

엇갈린상태- 키값과 교체
key:6, i:7, j:6
--현재배열
 show 함수 실행
12345678910
 show 함수 실행
12345678910

재귀함수1 시작전값: start:6,j-1:5
**재귀함수1 끝나고 값: start:6,j-1:5
재귀함수2 시작 시작전 값:  j + 1:7,end:7
**재귀함수2끝나고 값: j + 1:7,end:7

**재귀함수2끝나고 값: j + 1:6,end:7

**재귀함수2끝나고 값: j + 1:5,end:7

**재귀함수2끝나고 값: j + 1:2,end:7

**재귀함수1 끝나고 값: start:1,j-1:7
재귀함수2 시작 시작전 값:  j + 1:9,end:8
**재귀함수2끝나고 값: j + 1:9,end:8

**재귀함수1 끝나고 값: start:1,j-1:8
재귀함수2 시작 시작전 값:  j + 1:10,end:9
**재귀함수2끝나고 값: j + 1:10,end:9

**재귀함수2끝나고 값: j + 1:1,end:9


 show 함수 실행
12345678910

 

참조: 

https://m.blog.naver.com/ndb796/221226813382