TIL88. CodeKata : 정렬 알고리즘 문제

🌈 정렬 알고리즘 문제

🔥 버블 정렬

🔥 선택 정렬

🔥 삽입 정렬

🔥 퀵 정렬

🔥 병합 정렬

🤔 버블 정렬

✔️ 버블정렬은 앞에서부터 두 수를 계속 비교해서 가장 큰 수를 맨 뒤로 보냅니다.

✔️ 그렇기 때문에 내부 for문에서는 i가 증가하는 만큼 순회하는 배열의 길이가 짧아집니다.

✔️ 이렇게하더라도 for문이 2번 반복되기 때문에 최악의 경우를 기준으로하는 시간복잡도는 O(N2^2) 입니다.

import random
def bubble_sort(l):
  for i in range(len(l)-1):
    swap = False
    for j in range(len(l)-1-i):
      if l[j] > l[j+1]:
        l[j], l[j+1] = l[j+1], l[j]
        swap = True
    if swap == False: break
  return l
data = random.sample(range(100), 10)
print(bubble_sort(data))

🤔 선택 정렬

✔️ 선택 정렬은 반복을 순회하며 가장 작은 숫자의 index를 선택해 두었다가, 맨 앞자리로 swap한다.

✔️ 이에 두번째 순회부터는 시작점이 i만큼 증가한다. 이미 가장 작은 수가 i번째에 존재하기 때문이다.

✔️ 선택 정렬 또한 for문이 두번 반복하기 때문에 시간 복잡도는 O(N^2)이다.

import random
def select_sort(l):
  for i in range(len(l)-1):
    lowest_idx = i
    for j in range(i+1, len(l)):
      if l[lowest_idx] > l[j]:
        lowest_idx = j
    l[lowest_idx], l[i] = l[i], l[lowest_idx]
  return l
data = random.sample(range(100), 10)
print(select_sort(data))

🤔 삽입 정렬

✔️ 삽입 정렬은 순회의 범위를 점차 늘려가면서 역으로 수를 비교한다. 뒤에 수가 더 크다면 앞으로 계쏙 삽입시키다가 작은 수를 만나면 현재 순회중인 반복문을 빠져나간다.

✔️ 그리고 다시 다음 범위까지에서 마지막 요소부터 이전 요소와 비교하면서 정렬을 반복한다.

✔️ 이 또한 시간 복잡도는 O(N^2) 이다.

import random
def insert_sort(l):
  for i in range(len(l)-1):
    for j in range(i+1, 0, -1):
      if l[j] < l[j-1]:
        l[j], l[j-1] = l[j-1], l[j]
      else: break
  return l
data = random.sample(range(100), 10)
print(insert_sort(data))

🤔 퀵 정렬

✔️ 퀵 정렬은 재귀함수를 이용한 방법으로 이미 정렬이 되어있지 않다는 가정아래 정렬 방법 중에 가장 빠르다.

✔️ 시간 복잡도는 평균적으로 O(nlogN)이다. logN앞의 n은 상수다. 최악의 경우 O(n^2)이 된다.

def quick_sort(l):
    if len(l) <= 1: return l
    left, right = list(), list()
    pivot = l[0]
    left = [i for i in l[1:] if pivot > i]
    right = [i for i in l[1:] if pivot <= i]
    return quick_sort(left) + [pivot] + quick_sort(right)
import random
data = random.sample(range(100), 10)
print(quick_sort(data))

🤔 병합 정렬

✔️ 시간 복잡도는 평균적으로 O(nlogN) 이다. n은 상수인데, 평균적으로는 이 n의 값이 더 크기 때문에 퀵정렬보다는 느리다.

import random
def merge_sort(l):
    if len(l) <= 1: return l
    mid = len(l) // 2
    left = merge_sort(l[:mid])
    right = merge_sort(l[mid:])
    merged = []
    while left and right:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    while left:
        merged.append(left.pop(0))
    while right:
        merged.append(right.pop(0))
    return merged    
data = random.sample(range(100), 10)
print(merge_sort(data))