- 정렬에 대해 설명해주세요.
- == 정렬알고리즘은 일정 순서대로 열거하는 알고리즘을 말합니다. 버블정렬, 선택정렬, 삽입정렬, 병합정렬, 힙정렬, 퀵정렬이 있습니다. 정렬알고리즘이 중요한 이유는 탐색을 용이하게 합니다.
- 버블정렬 = 인접한 두 요소를 비교해가면서 정렬. 한번 돌때마다 큰값을 계속 뒤로 보내면서 마지막 요소가 정렬됌. 거품올라오는듯. 시간복잡도는 교환까지 해야돼서 On^2, 정렬되어져 있으면 On
- 선택정렬 = 한번 돌때마다 가장 작은 숫자를 탐색하고, 가장 왼쪽부터 차례대로 정렬채우는 방식. On^2
- 삽입정렬 = 이미 정렬된 배열에서 자기 위치를 찾아 삽입한다. 정렬된 배열 구간의 값들과 전부비교. 최선 On, 최악 On^2, 평균 On^2
- 병합정렬 = 분할 후 병합하는데, 병합하는 과정에서 정렬. 숫자를 물리적으로 만절씩 분리될수없을떄까지 분리 후, 결합할때 양쪽 숫자 덩어리중 작은 숫자를 하나씩 병합하면서 정렬 O(nlogN)
- 힙정렬 =
- 퀵정렬 = 특정 요소를 기준점으로 잡고 기준점보다 작은 요소는 왼쪽, 기준점보다 큰 요소는 오른쪽으로 두고 각각 중앙을 향해 한칸씩 움직이는데, 로우가 피봇보다 크고, 하이가 피봇보다 낮으면 로우와 하이자리를 바꿔주고, 중앙을 향해 나아감, 로우와 하이가 뒤바뀔때 피봇과 하이의 위치를 바꿔줌. 이때 자리바뀐 피봇을 기점으로 왼쪽은 피봇보다 작은값, 오른쪽은 피봇보다 큰값임. 이를 분할해서 위과정을 반복함, 피봇에 따라 성능차이가 심한데, 최악 On^2, 평균 OnlogN
-
정렬코드
- 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬
```jsx
#==========================
#========= 버블정렬 =========
print("============================\n========= 버블정렬 =========\n=============================")
#==========================
arr = [1,10,5,8,7,6,4,3,2,9]; print("정렬 전 =", arr)
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print("정렬 후 =", arr)
#==========================
#========= 선택정렬 =========
print("\n\n============================\n========= 선택정렬 =========\n=============================")
#==========================
arr = [1,10,5,8,7,6,4,3,2,9]; print("정렬 전 =", arr)
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
print("정렬 후 =", arr)
#==========================
#========= 삽입정렬 =========
print("\n\n============================\n========= 삽입정렬 =========\n=============================")
#==========================
arr = [1,10,5,8,7,6,4,3,2,9]; print("정렬 전 =", arr)
for i in range(1, len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j]
else:
break
print("정렬 후 =", arr)
#==========================
#========= 퀵정렬 =========
print("\n\n============================\n========= 퀵정렬 =========\n=============================")
#==========================
arr = [1,10,5,8,7,6,4,3,2,9]; print("정렬 전 =", arr)
def quick_sort(arr, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and arr[left] <= arr[pivot]:
left += 1
while right > start and arr[right] >= arr[pivot]:
right -= 1
if left > right:
arr[right], arr[pivot] = arr[pivot], arr[right]
else:
arr[left], arr[right] = arr[right], arr[left]
quick_sort(arr, start, right-1)
quick_sort(arr, right+1, end)
quick_sort(arr, 0, len(arr)-1)
print("정렬 후 =", arr)
#==========================
#========= 병합정렬 =========
print("\n\n============================\n========= 병합정렬 =========\n=============================")
#==========================
#https://www.youtube.com/watch?v=zo-tz1vGutM
arr = [1,10,5,8,7,6,4,3,2,9]; print("정렬 전 =", arr)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
i = 0
j = 0
k = 0
# left와 right를 비교하면서 arr에 정렬된 값을 넣어준다.
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# left나 right가 남아있는 경우 arr에 넣어준다.
if i == len(left):
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
else:
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
return arr
arr = merge_sort(arr)
print("정렬 후 =", arr)
```
