정렬 알고리즘

버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬에 대해 배워봅니다.

---

Bubble Sort

서로 인접한 두 원소의 대소를 비교하고, 자리를 교환하며 정렬하는 알고리즘

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

print(bubble_sort([5, 4, 13, 1, 3])) 

Bubble Sort 특징

1. 앞에서부터 모든 원소를 차례대로 비교한다.
2. 큰 원소가 오른쪽으로 이동하게 된다.

시간복잡도 : O(n^2)
공간복잡도 : O(n)

이중 반복문으로 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 동일하다.

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간복잡도는 O(n)이다.

Bubble Sort 복습

구현이 매우 간단하지만 굉장히 비효율적이다
안정 정렬 => 정렬 후에 같은 값인 요소의 순서가 보장됨
제자리 정렬 => 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않음

Selection Sort

배열 중 최솟값을 찾아 맨 앞에 위치한 값과 교체하는 알고리즘

def selection_sort(arr):
  indexMin = 0
  for i in range(len(arr)):
    indexMin = i
    for j in range(i+1, len(arr)):
      if arr[indexMin] > arr[j]:
        indexMin = j
    arr[i], arr[indexMin] = arr[indexMin], arr[i]
  return arr

print(selection_sort([7, 9, 18, 2, 6, 31, 0]))

Selection Sort 특징

1. 배열의 맨 앞 값을 선택한다

2. 내가 선택한 값 이후에 있는 원소들 중 최솟값을 찾는다

3. 내가 선택한 값과 위치를 바꾼다

시간복잡도 : O(n^2)
공간복잡도 : O(n)

이중 반복문으로 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 동일하다.
주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간복잡도는 O(n)이다.

Selection Sort 복습

구현이 간편하고, Bubble Sort와 유사하지만 조금 더 빠르다
불안정 정렬 => 정렬 후에 같은 값인 요소의 순서가 보장되지 않음
제자리 정렬 => 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않음

Insertion Sort

삽입할 위치를 정한 후, 원소들을 뒤로 옮긴후 지정된 자리에 자료를 삽입하는 알고리즘

def insertion_sort(arr):
  for i in range(1, len(arr)):
    temp = arr[i]
    prev = i - 1
    while prev >= 0 and arr[prev] > temp:
      arr[prev+1] = arr[prev]
      prev -= 1
    arr[prev+1] = temp
  return arr

print(insertion_sort([5, 22, 31, 1, 7, 14]))

Insertion Sort 특징

1. 두 번째 위치부터 탐색을 시작해서 현재 인덱스의 값과 이전 원소 인덱스를 저장함
2. 이전 위치 인덱스가 음수가 되지 않고, 현재 인덱스의 값보다 클 때 값을 교환하고 더 이전 위치를 가리키게 한다
3. ‘2번’ 과정의 반복문이 끝나면 prev가 현재 인덱스의 값보다 작은 값들 중 최댓값의 위치를 가리키게 되므로 (prev + 1)에 현재 인덱스의 값을 넣어준다

시간복잡도 : 최선 - O(n), 최악 - O(n^2)
공간복잡도 : O(n)

이미 정렬이 되어 있는 경우, 한 번씩밖에 비교를 안하므로 O(n)으로 최고의 정렬 알고리즘이 된다
하지만, 역으로 정렬되어 있을 경우 거품, 선택 정렬과 마찬가지로 O(n^2)가 된다
주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간복잡도는 O(n)이다.

Insertion Sort 복습

때에 따라 매우 효율적일 수도 매우 비효율적일 수도 있다
안정 정렬 => 정렬 후에 같은 값인 요소의 순서가 보장됨
제자리 정렬 => 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않음

Quick Sort

분할 정복 방법을 통해 주어진 배열을 정렬하는 알고리즘

def quickSort(arr, start, end):
  if start >= end:
    return
  pivot = partition(arr, start, end)
  quickSort(arr, start, pivot-1)
  quickSort(arr, pivot+1, end)

def partition(arr, start, end):
  L, R = start, end
  while L < R:
    while arr[start] < arr[R]:
      R -= 1
    while L < R and arr[L] <= arr[start]:
      L += 1
    arr[L], arr[R] = arr[R], arr[L]
  arr[start], arr[L] = arr[L], arr[start]
  return L


arr = [7, 13, 2, 9, 25, 0, 44]
quickSort(arr, 0, len(arr)-1)
print(arr)

Quick Sort 특징

1. 배열의 첫 번째 인덱스 값의 위치를 찾아 이동시키고 피벗으로 지정한다
2. 입력 배열을 피벗을 기준으로 왼쪽, 오른쪽 2개의 부분 배열로 분할한다
3. 부분 배열의 길이가 1이 될 때까지 순환 호출을 이용하여 1~2번을 반복한다

시간복잡도 : 최선 - O(nlogn), 최악 - O(n^2)
공간복잡도 : O(n)

각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다
따라서, 최선의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog₂n 가 된다.
최악의 경우는 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있는 경우다.
주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간복잡도는 O(n)이다.

Quick Sort 복습

한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 다른 정렬 알고리즘과 비교했을 때 가장 빠르다
하지만 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 오래 걸린다
평균적으로 가장 빠르며, 각 언어들의 내장함수도 퀵 정렬로 구현되어 있는 경우가 많다
불안정 정렬 => 정렬 후에 같은 값인 요소의 순서가 보장되지 않음