[알고리즘] Quick Sort 코드 및 풀이

KEY WORD

 

1. pivot: 중심

2. Divide: 분할

3. Conquer: 정복

4. recurrence: 재귀 (=> 순환 호출의 의미)

   - 주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식.

   - 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어 나가는 알고리즘으로, 이를 이용하기 위해서는 스택을 사용한다. (출처: 네이버사전_우리말샘)

   - 간단한 루틴을 풀 수 있지만, 처리 속도가 느리고 횟수가 지나치게 많으면 프로그램이 정지하기도 한다. (출처: 네이버사전_우리말샘)

5. subarray: 부분 배열

6. Pseudocode: 의사 코드

- 프로그래밍 언어에 무관하게 간략하게 표현한 코드, 참고하여 코드 작성

---

 

Qcuick Sort 란?

 

▶ Divide and Conquer방법 중 하나

- 배열을 2개의 조각으로 나눈 후 각각을 정렬하고 그 조각들을 다시 모아 원래 배열을 정렬시키는 방법

- 대개 순환 호출을 이용하여 구현

 

▶ Merge Sort(합병정렬)과 달리 비균등한 크기로 나눔

- Pivot 값을 기준으로 값이 더 작은 원소들과 큰 원소들로 나눔

 

 

< Step >

 

Step 1 Pivot 값 설정

→ 배열의 끝 값을 pivot 값으로 지정

 

Step 2 Divide

→ Pivot 값을 기준으로 값이 더 작은 원소와 큰 원소로 나눔

(ex. 위 사진에서 밑에서 두 번째 배열)

→ 마지막에 Pivot 값을 중간으로 보내 줌

(ex. 위 사진에서 마지막 배열 )

​

Step 3 Conquer

→ 부분 배열을 정렬한다 (순환 호출 이용)

 

Step 4 Combine

→ 정렬된 부분 배열들을 하나의 배열로 합병

 

※ 순환 호출을 통해 부분 배열의 크기가 충분히 작아지도록 계속해서 쪼개고, 정렬하고, 합병하는 방법을 반복하여 원래 배열이 모두 정렬되도록 함

※ 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 판단

​

---

 

Pseudocode

 

Pseudocode를 같이 첨부하니 전체 코드를 보기 전 참고하여 직접 코드를 짜보는 것을 추천!

( cf. 이 의사 코드에서는 배열의 인덱스가 1에서부터시작,

C언어와 같이 배열의 인덱스가 0부터 시작하는 언어를 이용할 때 주의 필요)

 

< Quick Sort > - Recurrunce

 

< Partitioning >

 

---

 

Code

 

< main 함수 > - 배열 설정 및 출력

- 8개의 원소 값을 가지기 때문에 →A[8]

- C언어에서 index( i )값은 0부터 시작하기 때문에 index 범위는 0~7

   →quicksort(A, 0, 7)

 

< quciksort 함수 > - Recurrunce

 

< partition 함수 > - Divide and Conquer

- i : pivot 값을 기준으로 반으로 나눈 후 중간점을 구분하기 위한 index

- j : pivot 값과 비교해나가는 원소의 index

- swap 함수 : 정렬 과정에서 두 값의 위치를 편하게 바꿔주기 위해 함수로 만듦

- swap(&A[ i+1 ], &A[ r ])

   → A[i+1]와 A[r]을 바꿈으로써 pivot 값을 중간으로 이동

   → index i 까지는 pivot보다 작은 값

   → A[i+1]은 pivot 값

   → A[ i+2]부터 끝까지는 pivot 보다 큰 값

 

---

 

Result

 

 

---

수업 자료를 토대로 작성한 것이니 혹시라도 copy는자제 부탁드립니다.

​

이해가 안 가는 부분은 부담 없이 댓글 남겨 주시고

도움이 되셨다면 공감 부탁드립니다 :)