Python - 알고리즘 (버블정렬,삽입정렬,선택정렬)

버블정렬

처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서
큰 숫자를 가장 끝으로 옮기는 알고리즘이다.

nums = [10, 2, 7, 21, 0]을 순서대로 정렬하는 문제

nums = [10, 2, 7, 21, 0]
print(f'not sorted nums : {nums}')

length = len(nums) -1 # 마지막 index를 얻기 위해
for i in range(length):
​​​​for j in range(length - i): # 이미 정렬된 부분은 다시 검사할 필요 x , -i를 통해 이미 정렬된 끝 부분 제외
​​​​​​​​if nums[j] > nums[j+1]: #앞뒤 비교하고 
​​​​​​​​​​​​nums[j], nums[j+1] = nums[j+1],nums[j] # 자리 바꾸기

​​​​​​​​print(nums)
​​​​print()
print(f'sorted nums : {nums}')

---

삽입정렬

정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는 것
(정렬이 이미 되어있는 앞 부분과 나 자신을 비교해서 나 자신이 어디에 삽입되면 되는지 찾는 것)

예제: nums = [5, 10, 2, 1, 0]을 순서대로 정렬하는 과정

# ascending

nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)): # 시작 인덱스를 1로 하여, 배열의 두 번째 요소부터 시작.
​​​​i2 = i1 - 1 # 현재 요소의 이전 요소의 인덱스
​​​​cNum = nums[i1] # 현재 요소의 값을 cNum에 저장

​​​​# 현재 요소(cNum)보다 이전 요소의 값이 더 크고 인덱스가 0 이상인 동안 반복
​​​​# 이는 삽입될 위치를 찾기 위해 이미 정렬된 배열 부분을 역순으로 탐색.
​​​​while nums[i2] > cNum and i2 >= 0: 
​​​​​​​​nums[i2 + 1] = nums[i2] # 이전 요소를 한 칸 뒤로 밀어냄
​​​​​​​​i2 -= 1 # 비교할 이전 위치로 인덱스를 이동

​​​​nums[i2 + 1] = cNum # 찾은 위치에 현재 요소를 삽입

​​​​print(f'nums : {nums}') 

---

# descending

nums = [5,10,2,1,0]


for i1 in range(1, len(nums)):
​​​​i2 = i1 - 1
​​​​cNum = nums[i1]

​​​​while nums[i2] < cNum and i2 >= 0: # 작다로 변경
​​​​​​​​nums[i2 + 1] = nums[i2]
​​​​​​​​i2 -= 1

​​​​nums[i2 + 1] = cNum

​​​​print(f'nums : {nums}')

---

선택정렬

주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘.

nums = [4, 2, 5, 1, 3]

for i in range(len(nums) - 1): # 전체 배열을 순회. 마지막 요소는 자동으로 정렬되므로 len(nums) - 1까지
​​​​minIdx = i # 가장 작은 요소의 인덱스를 현재 위치로 초기화

​​​​for j in range(i+1, len(nums)): # 현재 위치 다음부터 배열의 끝까지 순회
​​​​​​​​if nums[minIdx] > nums[j]: # 현재 선택된 최소값보다 더 작은 값을 찾으면
​​​​​​​​​​​​minIdx = j # 최소값의 인덱스를 업데이트

​​​​nums[i], nums[minIdx] = nums[minIdx], nums[i] # 현재 위치의 요소와 찾은 최소값을 교환
print(f'final nums : {nums}') # 최종 정렬된 배열을 출력