📍 Bubble Sort
🔍 About Bubble Sort
버블 정렬의 Key Concept은 현재 원소가 그다음 원소의 값보다 크면 바꾸는 것이다. 이 작업을 정렬이 완료될 때까지 반복하면 된다.
Key Concept
- 현재 원소(A[i])와 다음 원소(A[i+1])를 비교한다.
- 현재 원소가 다음 원소 보다 크면 서로의 자리를 바꾼다.
⛏️ Implementation
def bubble_sort(list):
list_length = len(list)
for try_count in range(0, list_length-1):
sorted = False
for index in range(1, list_length - try_count):
if list[index-1] > list[index]:
list[index-1], list[index] = list[index], list[index-1]
sorted = True
if sorted == False:
break
return list📍 Insertion Sort
🔍 About Insertion Sort
삽입 정렬의 Key Concept은 카드를 정렬하는 방법과 동일하다.
생각해 보자. 카드를 일렬로 펼쳐서 카드 배열을 만든다. 그 다음 두번째 카드를 선택하고 첫 번째 카드와 비교한다. 만약, 두번째 카드가 값이 작으면 첫번째 자리에 두번째 카드를 삽입한다. 이제 이 카드 배열은 두 번째 카드까지 정렬되었다. 다음에는 세번째 카드를 선택한다. 그리고 앞으로 가면서 값을 비교하여, 세번째 카드의 값이 작다면 그 앞에 카드를 삽입한다. 첫 번째 카드까지 이 동작을 반복한다. 이제 세번째 카드 위치까지 정렬되었다. 다음은 네 번째 카드, 다섯 번째 카드, 그리고 마지막 카드까지 이 동작을 반복한다.
Key Concept
- 선택한 원소(A[i+1])의 왼쪽(from A[i-1] to A[0]) 은 정렬되어 있다.
- 왼쪽의 정렬된 배열의 정렬된 상태가 유지될 수 있도록 선택한 원소의 위치를 찾아 삽입한다.
⛏️ Implementation
def insert_sort(list):
for standard in range(1, len(list)-1):
for index in range(standard, 0, -1):
if list[index] < list[index-1]:
list[index-1], list[index] = list[index], list[index-1]
return list📍 Selection Sort
🔍 About Selection Sort
선택정렬의 Key Concept은 배열에서 최소값을 찾아 맨 앞에 위치한 값과 교체하는 것이다.
Key Concept
- 가장 작은 값부터 정렬시켜 나가는 전략을 취한다.
- 배열의 정렬되지 않은 부분에서 가장 작은 값을 찾는다. ( 회가 거듭할 수록 배열의 왼쪽 부분은 정렬되어 간다. 반면, 오른쪽은 정렬되어 있지 않은 상태를 유지한다. )
- 가장 작은 값을 정렬되지 않은 부분의 맨 앞의 값과 교체한다.
⛏️ Implementation
def selection_sort(list):
for stage in range(0, len(list)):
min_index = stage
for index in range(stage+1, len(list)):
if list[min_index] > list[index]:
min_index = index
list[stage], list[min_index] = list[min_index], list[stage]
return list