정렬 알고리즘 중 기본 정렬 알고리즘에 해당하는 선택정렬(Selection sort), 버블정렬(Bubble Sort), 삽입정렬(Insertion sort)를 파이썬 언어로 구현해 보겠습니다.
선택 정렬
알고리즘
배열 A[1~n] 에서 가장 큰 원소 를 찾고 그 원소와 이 배열의 마지막 인덱스 원소 의 자리를 바꿉니다.
자리가 바뀌게 되면 마지막 인덱스는 이미 정렬이 완료되었기 때문에 더 이상 신경쓰지 않고, 남은 배열 A[1~n-1]로 같은 과정을 반복합니다.
파이썬 코드
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import random def selectionSort(arr): for i in range(len(arr), 0, -1): max = 0 # 가장 큰 원소의 인덱스 for j in range(0, i): if arr[j] > arr[max]: max = j arr[max], arr[j] = arr[j], arr[max] # 자리 바꿈 return arr arr = random.sample(range(1, 50), 7) # 랜덤 배열 선언 print(arr) # 정렬 전 print(selectionSort(arr)) # 정렬 후 |
결과
|
1 2 |
[4, 30, 38, 14, 3, 45, 41] [3, 4, 14, 30, 38, 41, 45] |
버블 정렬
알고리즘
버블정렬도 선택정렬과 마찬가지로, 가장 큰 원소를 궁극적으로 배열의 마지막 인덱스로 보내는 것이 목적입니다. 그러나 다른점은, 선택정렬은 모든 원소 비교 후 가장 큰 원소 마지막 인덱스 원소와 자리를 바꾸지만, 버블 정렬은 이웃한 원소를 비교할 때마다, 정렬이 되어 있지 않으면 바꾸기를 반복합니다.
파이썬 코드
|
1 2 3 4 5 6 7 8 9 10 11 12 |
import random def bubbleSort(arr): for i in range(len(arr)-1, 0, -1): for j in range(0, i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # 자리 바꿈 return arr arr = random.sample(range(1, 50), 7) # 랜덤 배열 선언 print(arr) # 정렬 전 print(bubbleSort(arr)) # 정렬 후 |
결과
|
1 2 |
[25, 47, 9, 24, 34, 8, 30] [8, 9, 24, 25, 30, 34, 47] |
삽입 정렬
알고리즘
삽입 정렬은 이미 정렬이 되어 있는 배열에 다음 인덱스의 원소를 추가하여 정렬하는 과정을 반복하는 정렬 방법이다.
선택 정렬과 버블 정렬은 배열의 크기를 하나씩 줄여가며 정렬을 했지만, 삽입 정렬은 그 반대로 하나씩 늘리는 정렬이다.
파이썬 코드
|
1 2 3 4 5 6 7 8 9 10 11 12 |
import random def insertionSort(arr): for i in range(1, len(arr)): while i > 0 and arr[i] < arr[i-1]: arr[i], arr[i-1] = arr[i-1], arr[i] # 자리 바꿈 i -= 1 return arr arr = random.sample(range(1, 50), 7) # 랜덤 배열 선언 print(arr) # 정렬 전 print(insertionSort(arr)) # 정렬 후 |
결과
|
1 2 |
[32, 23, 44, 36, 12, 18, 37] [12, 18, 23, 32, 36, 37, 44] |
마무리
다음 알고리즘 관련 포스팅은 고급 정렬 알고리즘을 다룰 예정입니다.