[알고리즘] 기본 정렬 ( 버블 정렬, 삽입 정렬, 선택 정렬)

Sort

• 데이터를 임의의 순서대로 나열하는 것

대표적인 정렬

1. 버블 정렬 (Bubble Sort)
2. 삽입 정렬 (Insertion Sort)
3. 선택 정렬 (Select Sort)

버블 정렬 (Bubble Sort) 

https://visualgo.net/en/sorting

• 두 인접한 데이터를 앞의 데이터가 더 크다면 두 데이터의 자리를 바꾸는 정렬 알고리즘

https://en.wikipedia.org/wiki/Bubble_sort

코드

def bubble_sort(num_list):
    for i in range(len(num_list)):
        for j in range(len(num_list)-i-1):
            if num_list[j] > num_list[j+1]:
                num_list[j], num_list[j+1] = num_list[j+1], num_list[j]
                
    return num_list
    
-------------------------------------------------------------------------
    
import random
a = random.sample(range(100),10)
print(a)
print('bubble',bubble_sort(a))

[5, 79, 95, 9, 67, 34, 75, 61, 39, 74]
bubble [5, 9, 34, 39, 61, 67, 74, 75, 79, 95]

시간복잡도

• 반복문이 2개 있기 때문에 \( O(n^{2}) \)
• 최선 \( n \)
• 최악 \( \frac{n(n-1)}{n} \)

---

삽입 정렬 (Insertion Sort)

https://visualgo.net/en/sorting

• 두번째 index부터 시작함
• 해당 index 앞에 있는 data 부터 비교하여 해당 data 값이 앞의 data보다 크면, data의 index를 앞의 index 뒤로 보냄

코드

def insertion_sort(num_list):
    
    for i in range(len(num_list)-1):
        for j in range(i+1, 0, -1):
            if num_list[j] < num_list[j-1]:
                num_list[j], num_list[j-1] = num_list[j-1], num_list[j]
            else:
                break
    return num_list
    
    -----------------------------------------------------------------------
    
import random
a = random.sample(range(100),10)
print(a)
print('insertion',insertion_sort(a))

[60, 74, 54, 44, 84, 19, 47, 40, 94, 63]
insertion [19, 40, 44, 47, 54, 60, 63, 74, 84, 94]

---

시간복잡도

• 반복문이 2개 있기 때문에 \( O(n^{2}) \)
• 최선 \( n \)
• 최악 \( \frac{n(n-1)}{n} \)

---

선택 정렬 (Selection Sort)

https://visualgo.net/en/sorting

• 주어진 데이터중 최소값을  찾아 앞의 값과 교체함

코드

def selection_sort(num_list):
    for i in range(len(num_list)):
        lowest = i
        
        for j in range(i, len(num_list)):
            if num_list[lowest] > num_list[j]:
                lowest = j
                
        num_list[lowest], num_list[i] = num_list[i], num_list[lowest]
        
    return num_list
    
----------------------------------------------------------------------

import random
a = random.sample(range(100),10)
print(a)
print('insertion',selection_sort(a))

[44, 34, 75, 29, 24, 38, 21, 36, 82, 22]
insertion [21, 22, 24, 29, 34, 36, 38, 44, 75, 82]

---

시간복잡도

• 반복문이 2개 있기 때문에 \( O(n^{2}) \)
• 최선 \( n \)
• 최악 \( \frac{n(n-1)}{n} \)

 

시각복잡도를 보면 위의 3개가 기본 정렬인 이유를 볼 수 있음