정렬

정렬 알고리즘에 대해 간단하게 알아보는 시간을 가지고, 파이썬으로 이를 구현해볼게요.

bubble sort

인접한 두 원소를 검사하여 정렬하는 방법입니다.
시간복잡도 : O(n^2)

arr= [2,3,1,4]

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

bubbleSort(arr)
# [1,2,3,4]

Selection Sort

최솟값을 선택하는 과정을 반복합니다.
시간복잡도 : O(n^2)

1. 주어진 리스트 중 최솟값을 찾습니다.
2. 그 값을 맨앞에 위치한 값과 교체합니다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체합니다.

arr= [2,3,1,4]

def selectionSort(arr):
  n = len(arr)
  for i in range(n-1):
    min_idx = i
    for j in range(i+1,n):
      if arr[min_idx] > arr[j]:
        min_idx = j
    if min_idx != i:
      arr[i],arr[min_idx] = arr[min_idx],arr[i]

selectionSort(arr)
# [ 1,2,3,4 ]

Insertion Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
시간복잡도 : O(n^2)

arr = [2,3,1,4]
def insertionSort(arr):
  n = len(arr)
  for i in range(1,n):
    j = i-1
    key = arr[i]
    while j >= 0 and arr[j] > key:
      arr[j+1] = arr[j]
      j -= 1
    arr[j+1] = key

insertionSort(arr)
# [ 1,2,3,4 ]