[Algorithm] Bubble / Insert / Select Sort

Bubble sort : O(n^2) 평균

• [9 3 5 7 1] → 앞에서 부터 두개씩 비교하는것bubble sort
• 최대한 사용 안하는 것이 좋음

9 3 5 7 1	7a 5a 5b 7b 3c
3 5 7 1 9	5a 5b 7a 3c 7b
3 5 1 7 9	5a 5b 3c 7a 7b
3 1 5 7 9	5a 3c 5b 7a 7b
1 3 5 7 9	3c 5a 5b 7a 7b

→ bubble sort 은 stability 를 가짐 두개의 정렬 요소가 있을 때 첫번째 정렬의 요소가 같을 경우 두번째 정렬은 a→c 순서대로 이루어짐 => 불안정 정렬

from typing import List   

def sort(nums: List[int]) -> List[int]:
  for idx in range(0,len(nums)-1):
    for i in range(0,len(nums) - idx - 1):
      if nums[i] > nums[i+1]:
        nums[i],nums[i+1] = nums[i+1],nums[i] #swap
  return nums

print(sort(nums=[9,3,5,7,1]))

def sort(num_strs):
  for idx in range(0,len(num_strs)-1):
    for i in range(0,len(num_strs) - idx - 1):
      if num_strs[i][0] > num_strs[i+1][0]:
        num_strs[i],num_strs[i+1] = num_strs[i+1],num_strs[i] #swap
  return num_strs

print(sort(num_strs=[(7,'a'),(5,'a'),(5,'b'),(7,'b'),(3,'c')]))

---

Insertion Sorting : O(n^2)

• 이미 정렬된 배열 부분과 비교하여 , 자신의 위치를 찾아 삽입함으로 써 정렬을 완성하는 알고리즘
• bubble 만큼 직관적이고 느림

from typing import List   

def insertionSort(nums: List[int]) -> List[int]:
  for pIdx in range(1, len(nums)):
    tmp = nums[pIdx]
    idx = pIdx-1      
    while 0 <= idx and tmp < nums[idx]:
        nums[idx+1] = nums[idx]
        idx = idx-1
    nums[idx+1] = tmp
  return nums

print(insertionSort(nums=[9,3,5,7,1]))

---

Selection sort : O(n^2) not stable

• element 를 선택하고 → swap
• 칸에 들어갈 값을 찾고 swap 해주면 됨

Method

1. 배열에서 최솟값을 찾고

2. 최솟값이 배열의 맨 앞 원소보다 작을 때 자리 교체

3. 맨앞의 원소를 제외한체 1-2 과정 반복

import sys
from typing import List   

def sort(nums: List[int]) -> List[int]:
  for idx in range(0,len(nums)):
    minNum = nums[idx]
    minIdx = idx
    for i in range(idx,len(nums)):
      if nums[i] < minNum:
        minNum = nums[i]
        minIdx = i
    nums[idx],nums[minIdx] = nums[minIdx],nums[idx] #swap
  return nums

print(sort(nums=[9,3,5,7,1]))

#selection sort is not stable

def sort(num_strs):
  for idx in range(0,len(num_strs)):
    minNum = num_strs[idx][0]
    minIdx = idx
    for i in range(idx,len(num_strs)):
      if num_strs[i][0] < minNum:
        minNum = num_strs[i][0]
        minIdx = i
    num_strs[idx],num_strs[minIdx] = num_strs[minIdx],num_strs[idx] #swap
  return num_strs

print(sort(num_strs=[(7,'a'),(7,'b'),(5,'a'),(5,'b'),(3,'c')]))