정렬 알고리즘 #선택 정렬/삽입정렬/퀵 정렬/계수 정렬

이 글은 이것이 취업을 위한 코딩테스트다를 읽고 개인적으로 공부한 내용을 정리한 글입니다 :>
with .. 내가 만든 그림

👻 정렬 알고리즘이란?

정렬 알고리즘

: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 (ex 오름차순 정렬, 내림차순 정렬

: 이진 탐색의 전처리 과정 -> 정렬 알고리즘으로 데이터를 정렬해야 이진탐색이 가능 !

 

정렬 알고리즘 종류 

• 선택 정렬
• 삽입 정렬
• 퀵 정렬
• 계수 정렬

 

---

 

위 카드를 오름차순으로 정렬할 것이다

컴퓨터가 어떻게 정렬할 수 있을까 ?!

 

1️⃣ 선택 정렬

: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째 데이터와 바꾸는 과정을 반복하는 것 !

 

🧩 선택 정렬 진행 과정

1) 첫번째 단계

전체 데이터 중 가장 작은 0을 맨 앞에 있는 7과 바꾼다. 

 

2) 두번째 단계 

.

.

생략

.

.

 

9) 9번째 단계

 

10) 마지막 단계

 

👩🏻‍💻 선택 정렬 코드 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
	min_index = i
    for j in range(i + 1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] # swap
    
print(array)

 

⏰ 시간 복잡도 

선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨앞으로 보내야한다. 

또한 매번 가장 작은수를 찾기 위한 비교 연산이 필요하다. 

앞선 예시의 연산 횟수는 N + (N - 1) + (N - 2) + ··· + 2 이다. 

따라서 선택 정렬의 시간 복잡도는 O(N^2)이다.

 

선택 정렬은 알고리즘 문제를 풀기에는 다소 느린편이기는 하지만, 문제에서 가장 작은 원소를 찾아야 하는 일이 종종 있으므로 알아두는 것이 좋다 !

---

2️⃣ 삽입 정렬

: 데이터를 하나씩 확인하여, 각 데이터를 적절한 위치에 삽입 -> 선택 정렬과 달리 필요할 때만 위치를 바꿈 

 

🧩 삽입 정렬 진행 과정

1) 첫번째 단계

첫 번째 데이터는 정렬되어있다고 판단하기 때문에, 삽입 정렬은 두 번째 데이터부터 시작한다.  

두 번째 데이터가 정렬되어있는 데이터 '7'보다 작으므로 '7' 왼쪽에 삽입한다. 

 

2) 두번째 단계 

'5'와 '7'이 정렬되어있고, '9'가 삽입될 수 있는 위치는 총 3가지이다. 

'9'는 '7'보다 크므로 지금 위치에 있으면 된다.

 

3) 세번째 단계

'0'의 위치를 찾아보자. 

'0'은 이미 정렬된 '5', '7', '9'와 비교했을 때 가장 작으므로 맨 왼쪽에 삽입하면 된다. 

 

.

.

생략

.

.

 

마지막 단계

다음과 같이 적절한 위치를 삽입하는 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된다. 

 

💡 놓치면 안되는 삽입 정렬의 특징

삽입 정렬에서 정렬되어 있는 원소는 항상 오름차순을 유지하고 있기 때문에, 

정렬되어 있지 않은 원소가 삽입할 위치를 찾을 때 자신보다 작은 데이터를 만나면 그 위치에서 멈춘다.(뒤에 원소가 무엇인지 살펴보지 않음)

 

👩🏻‍💻 선택 정렬 코드 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
	for j in range(i, 0 , -1): # 인덱스 i부터 1까지 감소하며 반복
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else: # 자기보다 작은 데이터를 만나면 그 자리에서 멈춤
                break

        
print(array)

 

⏰ 시간 복잡도 

삽입정렬의 시간 복잡도 또한 O(N^2)이다.

하지만 삽입 정렬은 현재 리스트의 데이터가 조금 정렬되어 있는 상태라면 매우 빠르게 동작할 것이다. 

 

알고리즘 문제를 풀기에는 다소 느린편이 맞지만, 거의 정렬되어 있는 상태의 입력이 주어진다면 강력한 정렬 알고리즘이다 !

---

3️⃣ 퀵 정렬

: 기준을 설정한 후 큰 데이터와 작은 데이터의 위치를 바꾸고, 리스트를 반으로 나누는 방식으로 동작
이때 설정한 기준을 피벗(pivot)이라고 한다 !

 

🧩 퀵 정렬 진행 과정

그림에서 핑크색이 피벗입니다 

1) 첫번째 단계

리스트에서 첫번째 데이터를 피벗으로 정한다. 따라서 위 그림에서 피벗은 '5'이다.
이후에 왼쪽에서부터 '5'보다 큰 데이터는 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 고르면 '4'이다. 
이제 이 두 데이터의 위치를 변경해준다. 

 

2) 두번째 단계 

그다음 피벗보다 큰 값과 작은 값을 찾았다. '9'와 '5'이다. 이 둘의 자리를 변경해준다. 

 

3) 세번째 단계

그다음 피벗보다 큰 값과 작은 값은 '6'와 '1'이다.

이렇게 큰 값과 작은 값의 위치가 엇갈린 경우에는 피벗과 작은 값의 위치를 변경해준다.  

그러면 이제 피벗을 기준으로 분할하여 정렬하면 된다. 

 

4) 피벗 기준 왼쪽 정렬하기

새로운 피벗을 설정하고 동일한 방식으로 정렬을 수행해주면 된다. 

 

5) 피벗 기준 오른쪽 정렬하기

오른쪽도 마찬가지로 새로운 피벗을 설정해주고 정렬해주면된다. 

 

 

👩🏻‍💻 퀵 정렬 코드 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
	# 리스트가 하나 이하의 원소를 담고 있다면 종료 
    if len(array) <= 1:
    	return array
       
    pivot = array[0]
    tail = array[1:] # 피벗을 제외한 리스트 
    
    left = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right = [x for x in tail if x > pivot ] # 분할된 오른쪽 부분
    
    # 분할 후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    

print(quick_sort(array))

 

⏰ 시간 복잡도 

퀵 정렬의 시간 복잡도는 O(NlogN)이다.

하지만 가장 왼쪽에 있는 데이터를 피벗으로 삼을 때, 이미 정렬되어 있는 경우에는 O(N^2)도 가능

 

 

---

4️⃣ 계수 정렬

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠름 -> but 정수형 데이터만 사용 가능 

일반적으로 가장 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적 ex) 0~100점 사이의 성적 데이터 정렬

-> 왜?! 

모든 범위를 담을 수 있는 크기의 배열을 선언해야하기 때문 

 

🧩 계수 정렬 진행 과정

 

👩🏻‍💻 계수 정렬 코드 

array = [0, 4, 3, 5, 6, 2, 4, 1, 6, 8, 5, 5, 6, 8, 2, 9]

count = [0] * (max(array) + 1) # 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)

for i in range(len(array)):
	count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
    
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
	for j in range(count[i]):
    	print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

⏰ 시간 복잡도 

데이터가 양의 정수인 상황에서 데이터의 개수는 N, 데이터 중 최대값의 크기를 K라 할 때 계수 정렬의 시간 복잡도는 O(N + K)이다.

-> 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 인덱스의 값을 1씩 증가시킬 뿐 아니라, 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복하기 때문!

 

---

🎓 정리

문제에서 별도의 요구가 없다면 기본 정렬 라이브러리를 사용하자 

정렬 알고리즘의 원리를 묻는다면 선택 정렬, 삽입정렬, 퀵 정렬 등등등 을 사용하자

데이터의 범위가 한정되어 있으며 빠르게 동작해야 할 때는 계수 정렬을 사용하자