08-03 퀵 정렬(Quick Sort)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

1.정렬(Sorting)

 1)정의

 -기준에 따라 데이터를 순서대로 체계적으로 정리하는 알고리즘.

 -정렬의 목적은 데이터의 탐색을 용이하기 위한 목적이 있다.

 

 

2.퀵 정렬(Quick Sort)

 1)정의

 -분할 정복(Divide and Conquer) 알고리즘을 기반으로한 정렬 알고리즘.

 -분할 정복이란 크고 방대한 문제를 풀기 용이하게  조금씩 나누고 풀이한 다음

 다시 합쳐 해결하는 방법.

 -퀵 정렬은 데이터를 기준 요소를 정하고 전체 데이터를 분할하고 반복하는 방식이다.

 2)동작과정:오름차순 정렬

5

1

6

4

8

3

7

9

2

  -위와 같은 정렬되지 않는 자료구조가 있다.

  자료구조에서 기준이 될 데이터를 선정하고 데이터보다 작은 데이터와 큰 데이터 그룹을 분류한다

 

5

1

6

4

8

3

7

9

2

 

  -5를 기준요소로 정하고 5보다 작은 데이터 그룹(1,4,3,2)을 5의 왼쪽에 큰 그룹(6,8,7,9)을

   오른쪽에 배치한다.

 

1

4

3

2

5

6

8

7

9

  -작은 데이터 그룹을 다시 기준요소를 선정한다.

 

1

4

3

2

5

6

8

7

9

 -만약 4를 기준 요소로 잡았다면 그 기준으로 다시 작은 데이터는 왼쪽 큰 데이터는 오른쪽으로 재배치한다.

 -

1

3

2

4

5

6

8

7

9

 

 -이러한 분류 및 배치를 반복함으로써 그룹의 크기가 1이하(더 이상 분할 수 없을)까지 반복.

3.퀵 정렬 예제

  -퀵 정렬 함수

 

 

-테스트