정렬 알고리즘 - 퀵 정렬 [Quick Sort]

정렬 알고리즘 - 퀵 정렬 [Quick sort]

오늘은 정렬 알고리즘 중 하나인 퀵 정렬(Quick Sort)에 관한 내용입니다.

(퀵 정렬을 간단하게 소개하고 예제)

퀵 정렬(Quick Sort)이란?

n개의 데이터를 정렬할 때 최악의 경우 =O(n^2), 평균적으로는 O(nlogn)

정렬을 하기 위한 데이터에서 데이터 하나를 고르고 그 데이터보다 작은 값과 큰 값으로 구분하여 정렬하는 알고리즘

 

알고리즘 코드

• main함수,  Quick_sort함수, Partition함수, SWAP함수로 이루어져 있습니다.
• 중간중간 결과 확인을 위한 print문이 있습니다.
• 해당 블로그에는 코드의 사진만 있습니다.
• 코드의 C파일은 제 Github에서 보실 수 있습니다. 

https://github.com/ykarr/C/blob/master/algorithm/Quick_sort.c

main()

Quick_sort()

partition()

SWAP()

알고리즘 실행 사진

위의 코드를 보시면 알겠지만 partition()부분이 끝난 후 결과를 출력합니다.

Quick sort가 끝나면 그 결과를 보여줍니다.

코드 분석

• main()은 고려하지 않음.
• printf문도 고려하지 않음.

현재 배열의 상태

0	1	2	3	4	5	6	7	8	9	10
987	546	24	56	87	98	45	65	47	68	423

[quicksort(a[],p,r)--> p=0, r=10]

1. Quick_sort에 정렬할 배열과 배열의 처음, 배열의 끝을 입력받습니다(a배열, 처음=0, 끝=10).

2. if(처음<끝)은 0 <10이므로 partition을 실행합니다.

3. partition에서 변수 하나에 기준으로 할 숫자를 하나 정해줍니다.(저는 그냥 맨 마지막 값)

4. 변수 하나를 더 만들고 시작값-1로 해서 저장해줍니다.(여기서는 -1쯤 되겠네요.)

5. 이제 for문에 의해 처음부터 끝-1 까지 돌면서 기준값보다 큰 값과 작은 값을 정렬할 겁니다. (x=정렬 기준 값)

현재 배열 상태

-1	0	1	2	3	4	5	6	7	8	9	10[x]
i값	987	546	24	56	87	98	45	65	47	68	423

6. j가 0일때-> 987<428을 비교합니다. ->거짓이므로  j의 값만 하나 올려줍니다.

7. j가 1일때-> 546<428을 비교합니다. -> 거짓이므로 j의 값만 하나 올려줍니다.

8. j가 2일때-> 24<428을 비교합니다. -> 참이므로 a[++i]와 a[2]를 바꿔줍니다. 그 후 j++

 -8번이 끝나고 현재 배열 상태

0[i]	1	2	3[j]	4	5	6	7	8	9	10[x]
24	546	987	56	87	98	45	65	47	68	423

9. j가 3일때-> 56<428을 비교합니다.-> 참 이므로 a[++i]와 a[3]을 바꿔줍니다. 그 후 j++

 -9번이 끝나고 배열 상태

0	1[i]	2	3	4[j]	5	6	7	8	9	10[x]
24	56	987	546	87	98	45	65	47	68	423

10. j가 4일때-> 87<428을 비교합니다. 참 이므로 a[++i]와 a[4]을 바꿔줍니다. 그 후 j++

 -10번이 끝나고 배열 상태

0	1	2[i]	3	4	5[j]	6	7	8	9	10[x]
24	56	87	546	987	98	45	65	47	68	423

11. j가 5일때->98<428을 비교합니다. 참 이므로 a[++i]와 a[5]를 바꿔줍니다. 그 후 j++

-11번이 끝나고 배열 상태

0	1	2	3[i]	4	5	6[j]	7	8	9	10[x]
24	56	87	98	987	546	45	65	47	68	423

12. j가 6일때-> 45<428을 비교합니다. 참 이므로 a[++i]와 a[6]을 바꿔줍니다. 그 후 j++

-12번이 끝나고 배열 상태

0	1	2	3	4[i]	5	6	7[j]	8	9	10[x]
24	56	87	98	45	546	987	65	47	68	423

13. j가 7일때-> 65<428을 비교합니다. 참 이므로 a[++i]와 a[7]을 바꿔줍니다. 그 후 j++

-13번이 끝나고 배열 상태

0	1	2	3	4	5[i]	6	7	8[j]	9	10[x]
24	56	87	98	45	65	987	546	47	68	423

14. j가 8일때-> 47<428을 비교합니다. 참 이므로 a[++i]와 a[7]을 바꿔줍니다. 그 후 j++

-14번이 끝나고 배열 상태

0	1	2	3	4	5	6[i]	7	8	9[j]	10[x]
24	56	87	98	45	65	47	546	987	68	423

15. j가 9일때-> 65<428을 비교합니다. 참 이므로 a[++i]와 a[7]을 바꿔줍니다. 그 후 j++

-15번이 끝나고 배열 상태

0	1	2	3	4	5	6	7[i]	8	9	10[x][j]
24	56	87	98	45	65	47	68	987	546	423

16. 여기까지 하면 j가 맨 끝까지 왔기 때문에 for문에서 나가게 됩니다. for문에서 나가고 swap을 해줍니다.

-a[++i]와 a[끝]을 swap해준 배열 상태

0	1	2	3	4	5	6	7	8[i]	9	10[j]
24	56	87	98	45	65	47	68	423	546	987

17. 이렇게 423의 왼쪽은 423보다 작은 값 423의 오른쪽은 423보다 큰 값이 되었습니다. i값을 return 해줍니다.

[quicksort(a[],p,q-1)--> p=0, q-1=7]

18. return 해준 i값을 받아서 다시 Quick_sort를 해줍니다.(a[],0,7) if(0<7)이므로 partition을 실행합니다.

19.x=배열의 끝 값을 해주고 0-1을 해줍니다. 

-현재 초기 배열 상태

-1	0	1	2	3	4	5	6	7[x]
i	24	56	87	98	45	65	47	68

20. j가 0일때-> 24<68을 비교합니다. 참 이므로 a[++i]와 a[0]을 바꿔줍니다. 그 후 j++(사실 이건 그냥 그대로잖..)

-20번이 끝나고 배열 상태

0[i]	1[j]	2	3	4	5	6	7[x]
24	56	87	98	45	65	47	68

21. j가 1일 때-> 56<68을 비교합니다. 참 이므로 a[++i]와 a[1]을 바꿔줍니다. 그 후 j++

-21번이 끝나고 배열 상태

0	1[i]	2[j]	3j	4	5	6	7[x]
24	56	87	98	45	65	47	68

22. j가 2일 때-> 87<68을 비교합니다. ->거짓이므로  j의 값만 하나 올려줍니다.

23 j가 3일 때-> 98<68을 비교합니다. ->거짓이므로  j의 값만 하나 올려줍니다.

24. j가 4일 때-> 45<68을 비교합니다. -> 참 이므로 a[++i]와 a[4]을 바꿔줍니다. 그 후 j++

-24번이 끝나고 배열 상태

0	1	2[i]	3	4	5[j]	6	7[x]
24	56	45	98	87	65	47	68

25. j가 5일 때-> 65<68을 비교합니다. -> 참 이므로 a[++i]와 a[4]을 바꿔줍니다. 그 후 j++

-25번이 끝나고 배열 상태

0	1	2	3[i]	4	5	6[j]	7[x]
24	56	45	65	87	98	47	68

26. j가 6일 때-> 47<68을 비교합니다. -> 참 이므로 a[++i]와 a[6]을 바꿔줍니다. 그 후 j++

-26번이 끝나고 배열 상태

0	1	2	3	4[i]	5	6	7[x][j]
24	56	45	65	47	98	87	68

27. j<r을 만족하지 않으므로 for문에서 나와서 a[++i]와 x를 swap해줍니다. 그 후 i를 리턴해줍니다.

-26번이 끝나고 배열 상태

0	1	2	3	4	5[i]	6	7[x][j]
24	56	45	65	47	68	87	98

28. 5를 리턴 받고 다시 퀵 정렬을 실행합니다. (a[],0,4) x=a[4], i=-1

[quicksort(a[],p,q-1)--> p=0, q-1=4]

-1	0	1	2	3	4[x]
i	24	56	45	65	47

29. j가 1일 때-> 24<47을 비교합니다. -> 참 이므로 a[++i]와 a[0]을 바꿔줍니다. 그 후 j++

0[i]	1[j]	2	3	4[x]
24	56	45	65	47

30. j가 1일 때-> 56<47을 비교합니다. ->거짓이므로  j의값만 하나 올려줍니다.

31. j가 2일 때-> 45<47을 비교합니다. -> 참 이므로 a[++i]와 a[2]을 바꿔줍니다. 그 후 j++

0	1[i]	2	3[j]	4[x]
24	45	56	65	47

32. j가 3일 때-> 65<47을 비교합니다. ->거짓이므로 j++

33.4[j]<4[r]이 되어서 for문을 빠져나와 a[++i]와 a[r]을 swap합니다. i를 리턴합니다.

0	1	2[i]	3	4[x][j]
24	45	47	65	56

이제부터 대충 과정만 작성합니다. 

[quicksort(a[],p,q-1)--> p=0, q-1=1]

34. 리턴 받은 i값으로 quicksort를 실행합니다.(a [], 0, 1)->정렬

이제 이 부분은 다 했습니다.(사진에 빨간색 동그라미 부분)

[quicksort(a[],q+1,r)--> q+1=3, r=4]

35. quicksort를 실행합니다.(a[],3,4)(아래처럼 정렬됨)

0	1
56	65

[quicksort(a[],q+1,r)--> q+1=3, r=4]

36. quicksort를 실행합니다.(a[],6,7)(아래 처럼 정렬됨)

0	1
87	98

[quicksort(a[],q+1,r)--> q+1=3, r=4]

37.quicksort를 실행합니다.(a[],9,10)

0	1
546	987

이렇게 해서 정렬이 모두 완료되었습니다.

0	1	2	3	4	5	6	7	8	9	10
24	45	47	56	65	68	87	98	423	546	987

추가 코멘트

하... 진짜 더럽게 기네요.

위의 표는 모두 명령을 실행한 결과를 나타낸 표입니다.

[프로그래밍/알고리즘] - 정렬 알고리즘 - 삽입 정렬 [Insertion sort]

[프로그래밍/알고리즘] - C자료구조 선택정렬 알고리즘(Selection Sort)

[프로그래밍/C 언어] - c언어 swap함수 문자와 문자 숫자와 숫자 값을 변경