자료구조, 알고리즘) Sorting - Bubblesort, Selectionsort, Insertionsort, Quicksort + Partition

 

 

※ 여기서 Stable, Unstable이란 동일한 key값에 대하여 정렬 후 순서가 바뀌면 Unstable, 바뀌지 않으면 Stable

(출처: 자료구조 강의시간 자료에서 캡쳐했습니다)

 

BubbleSort

• 좌우 대소비교를 하면서 정렬
• 시간복잡도: O(N^2) - 평균의 경우
• Stable한 정렬 

 

Bubblesort 정렬과정

- List = [6, 8, 1, 3, 10, 11]

 

- 진행과정 

 

[6, 8, 1, 3, 10, 11]   -> [6, 1, 8, 3, 10, 11]  -> [6, 1, 3, 8, 10, 11]  -> [6, 1, 3, 8, 10, 11] 

 

[6, 1, 3, 8, 10, 11]  -> [1, 6, 3, 8, 10, 11 ]  -> [1, 3, 6, 8, 10, 11]   -> [ 1, 3, 6, 8, 10, 11 ]

.

.

.

위 과정 반복

-> [ 1,  3,  6 , 8, 10, 11 ]

 

 

 

 

---

 

SelectionSort

• 리스트 맨 앞의 원소가 정렬되어 있다고 가정 하에 정렬 진행
• 시간 복잡도: O(N^2) - 평균의 경우
• Unstable한 정렬

 

Selectionsort 정렬과정

- List: [3, 7, 1, 5, 10]

 

- 진행과정 ( 파란 숫자는 가정되어 있음을 나타냄)

 

[3, 7, 1, 5, 10]   ->  [ 3, 7, 1, 5, 10]  -> [1, 7, 3, 5, 10]

 

[1, 7, 3, 5, 10]   ->  [1, 7, 3, 5, 10]   -> [1, 3, 7, 5, 10]

 

[1, 3, 7, 5, 10]   ->  [1, 3, 7, 5, 10]  ->  [1, 3, 5, 7, 10]

 

.

.

.

위 과정 반복

-> [ 1,  3,  5 , 7, 10 ]

 

 

 

---

InsertionSort

• 정렬의 범위를 한 칸씩 늘려가면서 정렬 진행, 진행방향: 자신의 왼쪽 (즉, 인덱스가 적어지는 방향으로 sorting)
• Selectionsort와 마찬가지로 첫번째는 이미 정렬되어 있다는 가정 하에 1번 인덱스부터 정렬 진행
• 시간복잡도: O(N^2) - 평균의 경우
• 기존의 정렬된 위치가 새로운 인덱스로 인해서 바뀔 수 있음
• Stable한 정렬

 

Insertionsort 정렬과정

-  List: [ 5, 11, 8, 9, 1, 3]

 

- 진행과정

(이전에 정렬이 되었더라도 그 뒤에 더 작은 수가 존재 할 수 있어서 정렬이 끝나지 않은 이상 정렬 완료된 게 아님)

 

[ 5, 11, 8, 9, 1, 3]  ->  [5, 8, 11, 9, 1, 3]  ->  [5, 8, 9, 11, 1, 3]  ->  [1, 5, 8, 9, 11, 3] 

 

->  [1, 3, 5, 8, 9, 11]   (정렬완료) 

 

 

 

 

---

QuickSort + Partition

• 재귀적 구조 (Recursive) 
• Partition이란 함수를 사용해 Pivot값을 설정 (맨 처음의 경우, Pivot은 맨 뒤의 인덱스 값으로 설정)
• Pivot 을 정한 후, Pivot  의 왼쪽 부분과 오른쪽 부분을 나눠서 정렬
• Unstable한 정렬
• 시간복잡도는 2가지로 나뉨 

        - Worst인 경우: O(N^2)  (모든 원소가 동일한 경우, 리스트가 불균등하게 나눠지는 경우)

        - Average, Best : O(N log N)

 

 

 

※ Quicksort visualization

출처: https://workat.tech/problem-solving/tutorial/sorting-algorithms-quick-sort-merge-sort-dsa-tutorials-6j3h98lk6j2w

 

 

---

Python Code for Sorting

 

※ 코드는 강의시간과 책에서 쓴 pseudocode와 code 에서 참조  (책: 쉽게 풀어쓴 자료구조 with 파이썬)

#Bubblesort

def bubblesort(a:list):

  for i in range(0, len(a)-1): # i : 0부터 n-2까지 n-1번

    for j in range(0, len(a)-1-i): # j: 0부터 n-2-i까지 반복 (n-1 + n-2 + ... +1)

      if  a[j] > a[j+1]: # 인전합 왼쪽 원소가 오른쪽 원소보다 크다면

        a[j] , a[j+1] = a[j+1], a[j] # 두 원소를 서로 swap

# Selection sort

def selectionsort(a:list):

  for i in range(0,len(a)-1):         # i: 0 ~ n-2까지 n-1번 반복

    minIndex = i                      # 첫번째 원소의 인덱스를 최소값 인덱스라고 가정

    for j in range(i+1, len(a)):  # j: i+1 ~ n-1 (마지막 원소)까지 반복

       if a[j] < a[minIndex]:   # a[minIndex]보다 작은 값이 있으면

        minIndex = j            # minIndex값을 업데이트

    if i != minIndex :           # 첫번째 원소가 최소값이 아니면

      a[i], a[minIndex] = a[minIndex] , a[i]

# insertion sort

def insertionsort(a:list):

  for i in range(1, len(a)):  # i의 값은 1 (두번째 원소)부터 n-1 (마지막 원소)까지

    key = a[i]    # key: 자기 자리를 찾기 위해 인접한 왼쪽 원소와 비교

    j = i-1       # j : key 값보다 작은 값의 (오른쪽 끝) 인덱스

    while (j >= 0 and a[j] > key):    # j가 유효한 인덱스이고. 왼쪽 값이 key보다 큰 동안 이동

      a[j+1] = a[j] # 왼쪽값을 오른쪽으로 복사 (즉, 오른쪽으로 슬라이딩)

      j -= 1 # 하나더 왼쪽을 검사

    a[j+1] = key #  key 값이 있어야 할 제 자리는 j+1 인덱스임

# quicksort

def quicksort(a:list, left, right):  # left: 시작 인덱스, right: 끝 인덱스

  if left < right:

    q = partition(a, left, right)   # partition 함수를 호출하여 pivot 값의 인덱스 받음

    quicksort(a, left, q-1)         # pivot의 인덱스를 기준으로 왼쪽 sublist 재귀 호출

    quicksort(a, q+1, right)        # pivot의 인덱스를 기준으로 오른쪽 sublist 재귀 호출

def partition(a:list, low, high):   # low: 시작 인덱스, high: 끝 인덱스

  """리스트의 마지막 원소를 pivot으로 설정

     pivot 값의 최종 위치의 인덱스를 반환"""

  pivot = a[high]             # 마지막 원소를 pivot으로 설정

  i = low - 1                      # i: pivot보다 작은 원소들을 카운팅

  for j in range(low, high):   # j: low ~ high-1 (피봇 바로 이전 인덱스)

    if a[j] < pivot:             # 검사하는 원소가 pivot보다 작으면

      i += 1                    # i 값 1 증가

      a[i], a[j] = a[j], a[i]   # 발견한 pivot 보다 작은 값을 왼쪽으로 보냄

  a[i+1], a[high] = a[high], a[i+1]   # pivot이 자기 위치 (즉, i+1)로 보내짐

  return i+1                  # pivot이 있어야 할 위치의 인덱스 반환

 

 

---

Time Complexity

 

 

다양한 알고리즘들의 시간복잡도 

(삽입정렬: Insertionsort   /  선택정렬: Selectionsort)

 

 

 

 

---

Visualization

 

 

Bubblesort, Insertionsort visualization

- https://www.youtube.com/watch?v=TZRWRjq2CAg&t=99s

 

 

 

 

Quicksort visualization

- https://www.youtube.com/watch?v=vxENKlcs2Tw&t=2s

 

 

---

 

 

설명 잘하시는 유튜브 : https://www.youtube.com/@abdul_bari

Abdul Bari

(Caution: India English is included.....)