[자료구조] sorting1 - bubble sort, selection sort, insertion sort (개념 및python 실습)

sorting 개념&실습(python) 시리즈😊

sorting 2 - mergesort, quicksort, heapsort
sorting 3 - counting sort, radix sort, topological sort

• 시간복잡도가 최대 $O(n^2)$ 인 기본 정렬 알고리즘을 알아봅시다.
  
  출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

1. Bubble Sort

• 자주 이용되지는 않음
• 이해하기 쉬움
• n, n+1 번째 index를 각각 비교하면서 설정

1st cycle

[https://dev.to/buurzx/buble-sort-4jkc]

해당 cycle 반복

• cycle 반복때마다 맨 뒤 값은 하나씩 정렬 완료됨

• 최악의 경우 모든 item을 swap 해야함!

Code😘

lis = [9,6,7,3,5]
for m in range(len(lis)-1 , 0, -1):
  for n in range(m):

    if lis[n]>lis[n+1]:
      temp=lis[n]
      lis[n]=lis[n+1]
      lis[n+1]=temp
      # lis[n],lis[n+1] = lis[n+1],lis[n] #pythonic 한 코드
  print(lis)
# print(lis)
print(sorted_lis==lis)

>>>
[6, 7, 3, 5, 9]
[6, 3, 5, 7, 9]
[3, 5, 6, 7, 9]
[3, 5, 6, 7, 9]
True

additional optimization

• 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 됨
• 다시말해 바뀐 지점까지는 다시 연산을 안하도록 세팅

def bubble_sort(arr):
  end = len(arr)-1
  while end>0 :
    last_swap = 0
    for n in range(end):
      if arr[n]> arr[n+1]:
        temp = arr[n]
        arr[n] = arr[n+1]
        arr[n+1] = temp
        last_swap = n
      end = last_swap

Time Complexity

$O(n^2)$ -> not good!

2. Selection Sort

[https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html]

• 최솟값 index 정보 저장 후 맨 앞 index와 swap
• swap 완료된 값은 제외하고 다른 값들로 순차적으로 진행
• 매 cycle마다 1번의 swap만 하면 됨

Code😘

lis = [9,6,7,3,5]
for i in range(len(lis)-1):
  min_idx = i
  for j in range(i+1,len(lis)):
    if lis[j]<lis[min_idx]:
      min_idx = j
  lis[i],lis[min_idx] = lis[min_idx], lis[i]
  print(lis)
print(lis==sorted_lis)

>>>
[3, 6, 7, 9, 5]
[3, 5, 7, 9, 6]
[3, 5, 6, 9, 7]
[3, 5, 6, 7, 9]
True

Time Complexity

also $O(n^2)$ -> not good!

3. insertion Sort

[https://algopoolja.tistory.com/19]

• index 0 은 원래 정렬되어 있다고 가정
• index 1 부터 왼쪽에 더 큰수가 있는지를 확인
• 클경우 swap
• index 2, 3로 진행하면서 왼쪽에 더 큰수가 있을 경우 index 0 까지 swappng 가능

장점

• 필요한 아이템만 스캔하기 때문에 시간이 덜걸림

Code😘

lis = [9,6,7,3,5]
for end in range(1,len(lis)):
  for i in range(end,0,-1):
    if lis[i-1]>lis[i]:
      lis[i-1], lis[i] = lis[i], lis[i-1]
    print(lis)
print(sorted_lis==lis)

>>>
[3, 6, 7, 9, 5]
[3, 5, 7, 9, 6]
[3, 5, 6, 9, 7]
[3, 5, 6, 7, 9]
True

>>>
[6, 9, 7, 3, 5]
[6, 7, 9, 3, 5]
[6, 7, 9, 3, 5]
[6, 7, 3, 9, 5]
[6, 3, 7, 9, 5]
[3, 6, 7, 9, 5]
[3, 6, 7, 5, 9]
[3, 6, 5, 7, 9]
[3, 5, 6, 7, 9]
[3, 5, 6, 7, 9]
True

Time Complexity

• best : $O(n)$
• worst : $O(n^2)$

정리😘

• 잘 쓰이지는 않음
• 쉬운 알고리즘이고 sorting의 고전 알고리즘