정렬 알고리즘 ① 버블정렬, 선택 정렬 , 삽입 정렬

정렬이란?

정렬은 데이터를 특정 기준에 따라 오름차순이나 내림차순으로 재배열하는 작업을 말한다.

 

정렬은 크게 내부 정렬과 외부 정렬 두 가지로 나뉜다

- 내부 정렬(Internal Sorting)

데이터양이 비교적 적을 때 주기억 장치(RAM)안에서 바로 정렬하는 방법이다.

 

※ RAM : 처리 속도는 매우 빠르지만, 용량이 상대적으로 작은 편이다.

- 외부 정렬 (External Sorting)

데이터양이 매우 많아서 RAM 안에 한 번에 올릴 수 없을 때, SSD나 HDD 같은 보조기억장치를 활용해 정렬하는 방식이다.

 

※ 보조기억장치(SSD/HDD) : 저장 용량은 크지만, RAM에 비해 속도가 느린 편이다.

---

내부 정렬

우리가 흔히 아는 정렬 알고리즘은 대부분 내부 정렬이다. 버블 정렬, 선택 정렬, 삽입 정렬 같은 기본 정렬 알고리즘도 내부 정렬에 포함된다.

사실 컴퓨터에서 프로그램 성능을 크게 좌우하는 건 대부분 RAM 안에서 얼마나 효율적으로 처리하느냐에 달려 있다.

 

그래서 우리가 배우는 기본 정렬 알고리즘도 대부분 내부 정렬을 기준으로 설명된다.

또 외부 정렬 역시 완전히 새로운 개념이기보다, 내부 정렬 알고리즘을 조금 변형해서 활용하는 방식에 가깝다.

 

내부 정렬은 정렬 방식에 따라 크게 다음과 같이 나눌 수 있다.

 

• 삽입법 : 삽입 정렬(Insertion Sort)
• 교환법. : 버블 정렬(Bubble Sort) ,선택 정렬(Selection Sort), 퀵 정렬(Quick Sort)
• 선택법 : 힙정렬 (Heap Sort)
• 병합법 : 합병 정렬 (Merge Sort)
• 분배법 : 기수 정렬 (Radix Sort)

---

버블 정렬(Bubble Sort)

버블 정렬 알고리즘은 가장 단순한 정렬 알고리즘이다.

버블 정렬은 인접한 두 원소를 서로 비교하면서, 순서가 올바르지 않다면 서로 자리를 바꾸는 방식으로 동작한다.

 

예를 들어 오름차순 정렬이라면,
앞의 값 > 뒤의 값 👉 두 값을 서로 교환(swap)

 

다만, 버블 정렬은 데이터 개수가 많아질수록 효율이 떨어지는 편이다. 왜냐하면 인접한 값들을 계속 비교해야 하기 때문에 비교 횟수가 많아지기 때문이다.

그래서 평균 시간 복잡도와 최악의 시간 복잡도 모두 O(n²)으로 비교적 높은 편이다.

🔽 아래 예시를 먼저 보면서 버블 정렬이 어떤 방식으로 동작하는 지 살펴보자.

---

버블 정렬의 동작 방식

버블 정렬은 총 (데이터의 개수 -1)만큼의 회전을 한다.

1️⃣ 한 회전(Pass)이 끝나면 가장 큰 값이 맨 뒤로 이동

버블 정렬은 여러 번의 회전을 반복하면서 정렬한다.

 

첫 번째 회전이 끝나면 가장 큰 값이 맨 뒤 로 이동한다 ➡️ 두 번째 회전이 끝나면 두 번째로 큰 값이 뒤에서 두 번째 위치 로 이동한다.

이런 식으로 정렬이 반복된다.

2️⃣ 이미 정렬된 뒤쪽은 다시 비교하지 않는다

한 번 올바른 자리를 찾은 요소는 이후로 비교 대상에 포함되지 않는다.

 

예를 들어 첫 번째 회전이 끝나서 가장 큰 값이 맨 뒤로 갔다면, 다음 회전에서는 맨 뒤 값을 제외한 나머지 부분만 비교한다.

3️⃣ 인접한 두 값을 비교하며 순서가 틀리면 교환한다

한 회전 동안 남아있는 값들을 차례대로 비교한다.

 

앞의 값  >  뒤의 값  ➡️  서로 자리를 바꾼다. (오름차순 기준)

---

선택 정렬(Selection Sort)

선택 정렬은 특정 구간 중 가장 작은 값을 하나를 선택해서 앞쪽에 배치하는 것을 반복하는 방법이다. 

쉽게 말해, 가장 작은 원소를 찾아서 맨 앞으로 보내기를 반복하는 정렬 알고리즘이다.

 

🔽 아래 예시를 먼저 보면서 선택 정렬이 어떤 방식으로 동작하는 지 살펴보자.

---

선택 정렬의 동작 방식

1️⃣ 전체 데이터 중에서 가장 작은 값을 찾는다

그 값을 맨 앞의 원소와 자리 바꾸기(swap)를 한다.

👉 (위의 예시) 1회전 종료 후 가장 작은 값인 2 가 0번 인덱스로 이동

👉 2회전 : 0번 인덱스를 제외하고 그 뒤의 

 

2️⃣ 가장 앞의 원소는 이미 정렬 완료

➡️ 1번 인덱스부터 나머지 데이터 중에서 가장 작은 값을 찾는다
➡️ 찾은 값은 두번째 원소와 swap한다

3️⃣ 이과정을 반복하면서 앞에서부터 데이터가 정렬된다.

---

삽입 정렬

 

🔽 아래 예시를 먼저 보면서 삽입 정렬이 어떤 방식으로 동작하는 지 살펴보자.

삽입 정렬의 동작 방식

1️⃣ 첫 번째 원소는 이미 정렬되었다고 가정

삽입 정렬은 두번째 원소부터 비교를 시작한다.

 

2️⃣ 현재 원소를 앞의 값들과 비교한다

👉 현재 원소를 바로 앞의 값부터 역순으로 비교한다.

👉 비교를 하면서 현재 값보다 작은 값을 만나면 비교를 멈춘 뒤 그 값 바로 뒤에 현재 원소를 삽입한다.

3️⃣ 인덱스 2의 요소와 비교 ... ➡️ 가장 마지막 인덱스의 요소와 앞의 요소들과 비교

 

 

---

💻 구현

오름차순 /내림차순 정렬

unsorted_arr = [8,9,24,6,7,10,20,28]

 

위의 정렬되지 않은 리스트를 앞에서 다뤄봤던 알고리즘들로 오름차순/ 내림차순으로 정렬해보자.

---

1️⃣ 버블 정렬

def bubble_sort(arr,reverse=False): 
  n= len(arr) # 리스트의 총 길이

  for i in range(n): # 총 회전 수 

    for j in range(n -1 -i): # 인접한 두 요소들의 크기를 비교

      # 오름차순 정렬
      if arr[j] > arr[j+1]: # 앞의 요소가 뒤의 요소보다 크면 
        arr[j] , arr[j+1] = arr[j+1] , arr[j] # 둘의 자리를 swap 

  if reverse == True: # 내림차순을 하고 싶다면
    return arr[::-1]
  return arr 

print('버블 정렬 오름차순 결과:',bubble_sort(unsorted_arr))
print('버블 정렬 내림차순 결과:',bubble_sort(unsorted_arr,True))

실행 결과

 

---

2️⃣ 선택 정렬

def selection_sort(arr, reverse=False):
  n= len(arr)


  for i in range(n-1) : # 총 회전 수 ->  N 개의 데이터에 대해서 N-1번 회전

    min = arr[i] # 최소값으로 arr[i] 로 일단 초기화한다
    min_idx = i   # 현재 위치를 최소값 위치라고 초기화

    for j in range(i+1,n): # 현재 위치 이후의 데이터를 순회하면서 비교

      if arr[j] < arr[i] : # min 과 비교했을 때 더 작으면 
        min_idx =j # min_idx 업데이트

    arr[i] , arr[min_idx] = arr[min_idx] , arr[i] # arr[i] 와 arr[j] swap 



  if reverse == True: # 내림차순 정렬이면
    return arr[::-1]

  return arr # 오름차순 정렬일 때 

print('선택 정렬 오름차순 결과:',selection_sort(unsorted_arr))
print('선택 정렬 내림차순 결과:',selection_sort(unsorted_arr,True))

실행 결과

 

---

3️⃣ 삽입 정렬

def insertion_sort(arr, reverse=False):
  n=len(arr)

  for i in range(1,n):
    key= arr[i] # 이 key 값이 이 리스트의 최솟값이라고 일단 생각하고 저장 
    min_idx= i

   # i 뒤의 인덱스부터 역순으로 순회하면서 key값과 비교하고 순회할 때의 현재 값이 key보다 크면 계속 역순으로 순회하고 해당 요소가 key보다 작으면 순회를 멈추고 그 요소와 이전 요소 사이에 insert한다 

    j = i -1 # key 바로 왼쪽 요소의 인덱스 j 

    while j>=0 and key < arr[j]: # j가 0 이상이고 arr[j] 가 key 보다 클 때까지만 순회
      j-=1

    # while문을 다 돌고 나오면 j 는 key보다 더 작은 값을 가진 요소의 인덱스를 가지게 된다

    # 이제 그 자리 보다 한 칸 뒤에 insert(key)를 해야 하는데 그전에 일단 key값을 가지고 있던 요소를 삭제하고 다시 넣기로 하자

    arr.pop(min_idx)
    arr.insert(j+1,key)

  if reverse == True:
    return arr[::-1]
  return arr 

print('삽입 정렬 오름차순 결과:',insertion_sort(unsorted_arr))
print('삽입 정렬 내림차순 결과:',insertion_sort(unsorted_arr,True))

실행 결과

 

---

random 데이터 생성 후 각 알고리즘 성능 비교

1️⃣ 무작위 배열 만들기

import random 
DATA_SIZE = 5000

# 1부터 10000 사이의 무작위 숫자 DATA_SIZE개 생성해서 random_data 리스트에 저장
random_data = [random.randint(1, 10000) for _ in range(DATA_SIZE)]

 

크기가 5000인 무작위 원소를 가진 배열을 만들어보았다.

2️⃣ 성능 비교 함수  compare_performance

각 정렬 함수를 실행했을 때의 시간을 재는 방식으로 성능을 비교해보기 위한 함수를 사용했다

 

여기서 파이썬의 time 라이브러리의 내장 함수 중 perf_counter()를 사용했다. (GPT 참고)

 

※ perf_counter() : 파이썬에서 실행시간을 정확하게 측정할 때 사용하는 함수

import time # 타이머 이용위해

def compare_performance(sort_function, data, reverse=False):

    start_time = time.perf_counter()       # 타이머 시작
    sort_function(data, reverse)      # test 데이터를 넣고 정렬하기
    end_time = time.perf_counter()         # 타이머 종료

    return end_time - start_time           # 걸린 시간 return

---

3️⃣ 성능 비교 실행

print(f"=== 무작위 배열에 대한 정렬 성능 비교  ===")

# 오름차순 기준으로 각 정렬의 성능 테스트해보기

bubble_time = compare_performance(bubble_sort, random_data, reverse=False)
selection_time = compare_performance(selection_sort, random_data, reverse=False)
insertion_time = compare_performance(insertion_sort, random_data, reverse=False)

print(f"1. 버블 정렬: {bubble_time:.5f} 초")
print(f"2. 선택 정렬: {selection_time:.5f} 초")
print(f"3. 삽입 정렬: {insertion_time:.5f} 초")

실행 결과

실행 결과를 보니 위 세가지 정렬 알고리즘 중 성능은

삽입 정렬 ➡️ 선택 정렬 ➡️ 버블 정렬 순으로 낮아짐을 확인할 수 있었다.

---

✚ 내림차순으로 정렬했을 때의 결과

 

 

👉 내림차순 정렬에 대해서도 성능은 위의 순서와 마찬가지로 삽입 정렬이 가장 높고 선택 정렬 그 다음 버블 정렬 순으로 낮아짐을 확인할 수 있었다.