5. 퀵 정렬(quick sort)

안녕하세요.

공상 개발입니다.

 

오늘은 분할 정복 알고리즘의 일종인 퀵 정렬에 대해 알아보는 시간을 가지겠습니다.

퀵 정렬은 정렬 알고리즘 중 제일 까다롭다고 생각합니다. 

---

 

1. 퀵 정렬(quick sort) 2. 퀵 정렬 알고리즘 실행 과정

 

---

 

# 퀵 정렬(quick sort)

 

퀵 정렬은 분할 알고리즘으로 분할된 부분 배열을 재귀적으로 정렬하는 알고리즘입니다.

피벗을 정한 뒤 피벗의 위치를 확정해가며 정렬이 이루어집니다.

특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.

 

퀵 정렬 로직 분할 : 분할 원소를 중심으로 두 부분 배열로 분할 정복 : 분할 원소를 제외한 나머지 두 부분 배열에 퀵 정렬을 재귀 호출하여 정렬 통합 : 필요 없음

 

 

퀵 정렬 예시

 

이때, 분할(partition) 알고리즘과 퀵 정렬(quickSort) 알고리즘으로 나누어서 구현할 수 있습니다.

 

QuickSort 함수

 

QuickSort 함수는 요소가 1개가 될 때까지 재귀를 하는 재귀 함수이며, 분할 역할을 담당합니다.

 

QuickSort 함수 로직 예시 이미지

 

 

Partition 함수

Partition 함수는 pivot보다 작은 아이템은 왼쪽 배열로, 큰 아이템은 오른쪽 배열로 분할합니다.

조건에 맞춰 위치를 바꾸어주는 함수이며, 정복 역할을 담당합니다.

 

소스 코드

출력 값

 

---

 

# 퀵 정렬 알고리즘 실행 과정

 

배열 a [] ={100,34,189,56,150,140,9,123}에 대하여 퀵 정렬을 사용하여 알고리즘 정렬이 실행되는 과정입니다.

병합 정렬 업로드 편에서도 말했듯이, 실행 과정을 직접 그려보는 편이 가장 이해하기 편하다고 생각합니다.

 

 

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시기 바랍니다.

좋은 하루 보내세요.