정렬이란?
정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미함
정렬 알고리즘은 상당히 다양함
구현 시 꼭 알아야 하는 swap
- swap → 아래와 같이 하면, 중간에 temp라는 변수를 사용하지 않고 할 수 있음
#### 일반적으로 swap를 하기위해서는 아래와 같은 temp를 사용해서 처리를 해야한
arr = [3,10]
print(arr)
print("--------")
temp = arr[0]
arr[0] = arr[1]
arr[1] = temp
print(arr)[3, 10]
--------
[10, 3]
# temp 없이 바로 바꾸기 위해서는 아래와 같은 형식을 사용
arr = [3, 10]
print(arr)
print("------")
arr[0], arr[1] = arr[1], arr[0]
print(arr)
선택 정렬
- 기본 아이디어 : 정렬되지 않은 그룹에서 하나씩 들어다가 다른 곳으로 옮기는 과정에서 순서에 맞게 중간중간 삽입을 하는 방법
- key 기준에 맞는 것으로 해서 차례대로 제일 부합하는 것을 찾아서 → 차례대로 하나씩 하게 되면 자연히 정리가 되는 것
- 일단 주어진 것에서 제일 작은것 or 제일 큰 값을 먼저 찾기!!!
→ 그 값을 맨 앞의 값과 교환해서 가서 제일 작은 것 배치 완료(제일 큰것, 맨 오른쪽)
→ 남은 것들을 대상으로 다시 제일 작은 or 제일 큰 것을 찾아서 반복 수행
기본 과정 : 작은 순서로 한다고 하면
(1) 위에서 일단 제일 작은 값을 찾기 위해서 앞에서 부터 비교를 하면서 진행을 해나간다.
→ 어디에 있는 것이 제일 작은지 정보를 가지고 있어야 할 것
→ 맨 마지막에 있는 2가 제일 작다는 것을 찾아냄
위의 과정에 대해서 좀 더 자세히 나타내면
(2) 주어진 것들에서 제일 작은 것을 찾았으니, 맨 앞의 20과 서로 교체
(3) 이제 위의 주어진 과정을 남은 것들을 대상으로 다시 반복 수행
참고) 기준이 큰 값으로 하느냐, 작은 값으로 하느냐의 차이
선택정렬 구현
arr = [ 20, 12, 10, 15 ,2]
for i_step in range(len(arr)):# 5개 원소 --> 0~4까지 5단계 롤링
# 1) 지금 i_step에서 제일 작은 값이 어디에 있는지 기록
# ==> 초기 값은 제일 앞에 있는 값으로 설정
min_step = i_step #--> 앞으로 계속 갱신
# 2) i_step +1 위치의 값부터 끝까지 다 비교
for i in range(i_step +1 , len(arr) ):
if arr[i] < arr[min_step]: # 더 작은 값이 등장하면 해당 자리 위치를 min_step에 저장
min_step = i
else:
pass
### --> i_step에서 제일 작은값에 대한 정보 min_step
arr[min_step], arr[i_step] = arr[i_step], arr[min_step] # 자리 교환 swap
print(arr)[2, 10, 12, 15, 20]
