알고리즘 Basic -2-
- 단순 선택 정렬은 '정렬되지 않은 부분'안의 최소 값(또는 최대 값)을 선택해서 '정렬된 부분'의 끝으로 옮긴다. 시간 복잡도는 O(n^2).
nums = [35, 80, 21, 54, 11, 45, 92, 39]
def simpleSelect(idx, arr):
if idx == (len(arr) - 1):
# 정렬되지 않은 부분의 요소 수가 1이 되면 종료
return arr
else:
# arr 의 idx 값과 최소값 위치 교환
minNum = min(arr[idx:])
temp = arr[idx]
arr[arr.index(minNum)] = temp
arr[idx] = minNum
idx += 1
return simpleSelect(idx, arr)
ans = simpleSelect(0, nums)
- 단순 교환 정렬(버블 정렬)은 이웃한 데이터 두 개의 크고 작음을 비교한 뒤, 정렬조건에 맞추어 이동시킨다. 정렬할 배열은 "정렬되지 않은 부분(앞부분)"과 "정렬된 부분(뒷부분)"으로 나뉜다. "정렬되지 않은 부분"의 데이터가 두 개만 남을 때까지 비교 & 교환 을 반복한다.
arr = [19, 80, 77, 11, 54]
def BubbleSort(arr):
for i in range(len(arr) - 1, 1, -1):
for j in range(i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)
return arr
ans = BubbleSort(arr)
- 단순 삽입 정렬은 배열 안의 "정렬된 부분" 안에 "정렬되지 않은 부분"의 데이터를 정렬 조건에 맞추어 삽입해 나가는 알고리즘이다.
def InsertionSort(arr):
for i in range(1, len(arr)):
for j in range(a, 0, -1):
if arr[j] < arr[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
return arr
- 셸 정렬은 정렬할 데이터 배열을 일정 길이의 그룹으로 나누고, 그 그룹 안에서 정렬조건에 맞추어 정렬한다.
1단계: 그룹 간격 SPAN을 N/2(몫의 정수 부분)로 초기화한다.
2단계: SPAN 이 1 이상이라면 다음 3~5 단계를 반복한다.
3단계: 데이터 열을 SPAN 만큼의 길이로 나눈다.
4단계: 나누어진 그룹들을 단순 삽입 정렬로 정렬한다.
def shellSort(arr):
N = len(arr)
gap = N // 2
while gap > 0:
for i in range(gap, N):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = gap // 2
- 오름차순으로 정렬된 여러 개의 데이터 열이 있을 때, 전체 열의 최소 값은 항상 각 데이터 열의 첫 번째에 있다.
- 병합 정렬은 병합 알고리즘을 이용한 정렬이다. 병합 정렬은 두 개로 나누는 단계와 병합하는 단계로 구성된다. 분할 단계는 나뉜 데이터 열의 요소 개수가 하나가 될 때까지 반복한다.
def mergeSort(arr):
if len(arr) > 1:
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array elements
L = arr[:mid]
# into 2 halves
R = arr[mid:]
# Sorting the first half
mergeSort(L)
# Sorting the second half
mergeSort(R)
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# 출처: https://www.geeksforgeeks.org/merge-sort/
- 퀵 정렬은 고속 정렬 알고리즘으로 기준값보다 작은 그룹과 큰 그룹을 분류하는 작업을 반복해서 정렬한다. 먼저 기준값을 정하고, 나머지 데이터들을 정렬 기준에 맞추어 기준값의 왼쪽/오른쪽에 배치시키면 기준값의 위치가 고정된다.
def partition(array, start, end):
pivot = array[start]
low = start + 1
high = end
while True:
while low <= high and array[high] >= pivot:
high = high - 1
while low <= high and array[low] <= pivot:
low = low + 1
if low <= high:
array[low], array[high] = array[high], array[low]
# The loop continues
else:
break
array[start], array[high] = array[high], array[start]
return high
def quick_sort(array, start, end):
if start >= end:
return
p = partition(array, start, end)
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)
# 출처: https://stackabuse.com/quicksort-in-python/
- 힙 정렬은 힙의 특성을 이용한 정렬 알고리즘이다.
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')
# 출처: https://www.programiz.com/dsa/heap-sort
Author And Source
이 문제에 관하여(알고리즘 Basic -2-), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beemo/알고리즘-Basic-2-저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)