정렬 알고리즘(2) - 퀵 정렬, 계수 정렬

본 포스팅에서는 정렬 알고리즘에 대한 정리 내용을 담고있습니다.

(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)

 

 

https://www.youtube.com/@dongbinna

동빈나

 

 

---

 

 

지난 포스팅에서는 선택 정렬, 삽입 정렬에 대해서 알아보았습니다.

2023.02.22 - [백준 알고리즘] - [알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬

[알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬

 

 

① 퀵 정렬

- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

- 기본적으로 퀵 정렬은 첫 번째 데이터를 그 기준 데이터(피벗, Pivot)로 설정

 

아래의 예시를 통해 퀵 정렬의 동작 과정을 살펴보겠습니다. 

처음 동작할때는 첫 번째 데이터인 '5'를 그 기준 데이터로 삼게 된다. 

위의 이미지에 써있는 것처럼 왼쪽에서 부터 기준 데이터 '5'보다 큰 데이터인 '7'을 선택하고,

오른쪽에서 부터는 기준 데이터 '5'보다 작은 데이터인 '4'를 선택해,

두 데이터의 위치를 변경한다. 

 

 

그 다음도 동일한 방식으로 한번 더 반복한다. 

왼쪽에서부터는 5보다 큰 값인 '9'

오른쪽에서부터는 5보다 작은 값인 '2'를 선택해 서로 자리 변경

 

 

그러다보면 이처럼 위치가 서로 엇갈리는 경우가 생기게 된다. 

이처럼 위치가 엇갈리는 경우에는 기준 데이터(피벗)과 작은 데이터의 위치를 서로 변경한다. 

즉, 기준 데이터인 '5'와 작은 데이터인 '1'의 위치를 서로 변경한다. 

그럼 다음과 같은 결과 값이 나오게 된다.

 

 

위에서 알 수 있듯이 이처럼 피벗을 기준으로

데이터들을 나누는 작업을 분할이라고 한다. 

 

 

피벗 5를 기준으로 왼쪽에 있는 데이터 묶음들에 대해서 동일한 방식으로 정렬을 수행한다.

이 과정을 반복하게 되면, 전체 데이터에 대한 정렬이 수행된다. 

 

 

이러한 퀵 정렬을 파이썬으로 구현하면 다음과 같습니다. 

정렬을 위해 quick_sort라는 함수를 정의해주는데

가장 처음부분에 if start >= end 를 통해 arr의 원소가 1개인 경우 바로 종료하도록 한다. 

 

 

조금 더 간단한 방식으로 위와 같은 코드로도 퀵정렬이 구현 가능하다. 

역시나 짧고 간단한 것이 내 취향에는 더 맞다. 

 

 

---

 

② 계수 정렬

- 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용이 가능하다. (성적같은거)

 

계수 정렬의 동작 과정은 다음과 같다. 

위와 같은 데이터가 주어졌다고 했을때, 가장 작은 데이터는 0이고 가장 큰 데이터는 9이다.

이 0부터 9까지의 범위가 모두 담길 수 있도록 리스트를 생성하고, 

각각의 데이터가 몇번 등장하는지 그 개수를 세어주는 방식으로 동작한다고 보면된다. 

 

가장 첫번째 데이터는 7이므로

인덱스 7의 값을 1 증가해준다. 

이 과정을 반복하게 되면

 

위와 같이 각 데이터가 총 몇번 등장하게 되었는지 횟수가 기록된다. 

이렇게 횟수를 기록한 리스트를 바탕으로 

첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력하면 된다.

 

 그럼 위와 같이 정렬된 형태로 결과를 출력하게 된다. 

 

 

 

이런 계수정렬을 파이썬을 이용해 구현하게 되면 아래와 같다.