python 고전 정렬 알고리즘의 예시 코드 구현

다음 정렬 알고리즘의 최종 결과는 기본적으로 승순 배열로 간단하고 특수한 상황을 고려하지 않고 알고리즘의 기본 사상만 나타냈다.

거품 정렬

내부 순환에서 인접한 원소는 순서대로 비교된다. 내부 순환은 첫 번째 순환이 끝나면 가장 큰 원소를 서열의 맨 오른쪽으로 옮기고, 두 번째 순환이 끝나면 가장 큰 원소를 가장 큰 원소의 왼쪽으로 옮기고, 내부 순환이 끝날 때마다 하나의 원소를 순서대로 정한다.

def bubble_sort(arr):
  length = len(arr)
  for i in range(length):
    for j in range(length - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
  return arr

정렬 선택

매번 내부 순환은 현재 가장 작은 원소를 얻어 적당한 위치에 놓는다.내부 순환은 첫 번째 순환이 끝난 후에 가장 작은 원소를 서열 1위로 교환하고, 두 번째 순환이 끝난 후에 두 번째 작은 원소를 서열 2위로 교환하며, 매번 내부 순환이 끝난 후에 한 원소를 정확한 순서 위치에 놓는다.

def selection_sort(arr):
  length = len(arr)
  for i in range(length):
    min_index = i
    for j in range(i + 1, length):
      if arr[j] < arr[min_index]:
        min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr

정렬 삽입하기

포커를 할 때 카드를 정리하는 사상을 비유하면 첫 번째 요소부터 시작하여 그것이 이미 순서를 정했다고 가정한다.그리고 두 번째 원소를 처리하기 시작한다. 만약에 첫 번째 원소보다 작으면 첫 번째 원소의 왼쪽에 놓고, 그렇지 않으면 오른쪽에 둔다. 그러면 현재 앞의 두 원소와 순서를 정한 다음에 나머지 원소를 순서대로 처리한다.

def insertion_sort(arr):
  length = len(arr)
  for i in range(1, length):
    pre = i - 1
    current_value = arr[i]
    while pre >= 0 and arr[pre] > current_value:
      arr[pre + 1] = arr[pre]
      pre -= 1
    arr[pre+1] = current_value
  return arr

힐 정렬

힐 정렬은 정렬에 삽입할 개선 버전입니다.삽입 정렬에서 매번 요소를 점차적으로 비교하고, 힐 정렬에서는 비교적 큰 단계부터 비교하여 마지막에 한 단계로 줄인다.

def shell_sort(arr):
  length = len(arr)
  gap = length // 2
  while gap > 0:
    for i in range(gap, length):
      pre = i - gap
      current_value = arr[i]
      while pre >= 0 and arr[pre] > current_value:
        arr[pre + gap] = arr[pre]
        pre -= gap
      arr[pre + gap] = current_value
    gap = gap // 2
  return arr

병합 정렬

먼저 서열 앞부분을 순서대로 배열한 다음에 서열 뒷부분을 순서대로 배열한 다음에 이 두 부분을 합쳐서 최종 서열을 얻는다. 구체적으로 서열을 두 부분으로 나누어 각각 순서대로 배열한 후에 합친다.

def merge(left, right):
  result = []
  while len(left) > 0 and len(right) > 0:
    if left[0] < right[0]:
      result.append(left.pop(0))
    else:
      result.append(right.pop(0))
  if len(left) > 0:
    result.extend(left[:])
  if len(right) > 0:
    result.extend(right[:])
  return result


def merge_sort(arr):
  if len(arr) < 2:
    return arr
  middle = len(arr) // 2
  return merge(merge_sort(arr[:middle]), merge_sort(arr[middle:]))

빠른 정렬

하나의 원소를 취하여 그것보다 작은 원소를 왼쪽으로 옮기고, 그것보다 큰 원소를 오른쪽으로 옮기며, 그것의 왼쪽의 서열과 오른쪽의 서열을 차례로 처리한다.

def partition(arr, left=None, right=None):
  pivot = left
  index = pivot + 1
  for i in range(index, right + 1):
    if arr[i] < arr[pivot]:
      arr[i], arr[index] = arr[index], arr[i]
      index += 1
  arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]
  return index - 1


def quick_sort(arr, left=None, right=None):
  left = 0 if left is None else left
  right = len(arr) - 1 if right is None else right
  if left < right:
    partition_index = partition(arr, left, right)
    quick_sort(arr, left, partition_index - 1)
    quick_sort(arr, partition_index + 1, right)
  return arr

무더기 정렬

먼저 최대 무더기를 구축한다. 가장 큰 무더기의 성질은 부모 노드의 값이 항상 좌우 하위 노드의 값보다 크다는 것이다. 그러면 이때 루트 노드의 값이 가장 크면 서열의 맨 오른쪽으로 옮긴다.그 다음에 더미 중의 현재 마지막 잎 노드를 뿌리 노드로 옮긴다. 이것은 가장 큰 무더기의 성질에 부합되지 않을 수 있기 때문에 조정한다. 이를 좌우 자노드 중의 가장 큰 값과 교환하면 잎 노드를 아래로 이동하는 것과 같다. 교환 후에도 성질에 부합되지 않으면 계속 교환한다. 성질에 부합될 때까지 이때의 뿌리 노드의 값은 현재 더미 중의 가장 큰 값이다.시퀀스의 정확한 위치에 꺼내서 상기 절차를 계속하여 나머지 노드를 처리합니다.

global length2


def heapify(arr, i):
  left = 2 * i + 1
  right = 2 * i + 2
  largest = i
  if left < length2 and arr[left] > arr[largest]:
    largest = left
  if right < length2 and arr[right] > arr[largest]:
    largest = right
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, largest)


def build_max_heap(arr):
  for i in range(len(arr) // 2, -1, -1):
    heapify(arr, i)


def heap_sort(arr):
  global length2
  length2 = len(arr)
  build_max_heap(arr)
  for i in range(len(arr) - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    length2 -= 1
    heapify(arr, 0)
  return arr

계수 정렬

시퀀스에 있는 원소를 그 값에 따라 상응하는 통에 넣은 후 통의 순서에 따라 꺼내면 되며 계수 정렬은 비교 조작이 필요 없다.

def counting_sort(arr):
  max_value = max(arr)
  buckets = [0] * (max_value + 1)
  index = 0
  length = len(arr)
  for i in range(length):
    buckets[arr[i]] += 1
  for j in range(max_value + 1):
    while buckets[j] > 0:
      arr[index] = j
      index += 1
      buckets[j] -= 1
  return arr

통 정렬

분류 계수 정렬은 많은 통을 구성하지만 통마다 값이 특정한 범위 내에 있는 원소를 넣을 수 있다. 서열 중의 원소를 요구에 따라 통에 넣은 다음에 통마다 원소를 정렬하고 마지막으로 통의 순서와 통마다 원소의 순서에 따라 최종 서열을 얻는다.

def bucket_sort(arr):
  bucket_size = 5
  max_value = max(arr)
  min_value = min(arr)
  bucket_num = (max_value - min_value) // bucket_size + 1
  buckets = {i: [] for i in range(bucket_num)}
  for i in range(len(arr)):
    buckets[(arr[i] - min_value) // bucket_size].append(arr[i])
  result = []
  for i in range(bucket_num):
    insertion_sort(buckets[i])
    result.extend(buckets[i])
  return result

기수 정렬

원소 값의 특정 위치에 따라 정렬하고, 낮은 위치에서 높은 위치로 각각 정렬한다.

def radix_sort(arr):
  max_value = max(arr)
  max_digit = len(str(max_value))
  dev = 1
  mod = 10
  result = arr[:]
  for i in range(max_digit):
    buckets = {i: [] for i in range(mod)}
    for k in range(len(result)):
      key = (result[k] % mod) // dev
      buckets[key].append(result[k])
    result = []
    for j in range(mod):
      result.extend(buckets[j])
    dev *= 10
    mod *= 10
  return result

상술한 코드를 두다여기

참고

https://www.cnblogs.com/onepixel/p/7674659.html

알고리즘 도론

채소새 강좌

이python이 고전 정렬 알고리즘을 실현하는 예시 코드에 관한 이 글은 여기까지 소개되었습니다. 더 많은 python 고전 정렬 알고리즘 내용은 저희 이전의 글을 검색하거나 아래의 관련 글을 계속 훑어보시기 바랍니다. 앞으로 많은 응원 부탁드립니다!