정렬 (Sorting)

정렬 (Sorting)

참고할만한 사이트 :: https://im-developer.tistory.com/133

데이터를 특정한 기준에 따라서 순서대로 나열 하는 것

프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary) 이 가능해진다.

보통 정렬을 공부하면 '알고리즘의 효율성' 을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 정렬 알고리즘을 공부하다보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

선택 정렬

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 하는 알고리즘

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
  min_index = i  # 가장 작은 원소의 인덱스
  for j in range(i + 1, len(array)):
    if (array[min_index] > array[j]):
      min_index = j

  # SWAP
  array[i], array[min_index] = array[min_index], array[i]

print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

function selectionSort (array) {
    for (let i = 0; i < array.length; i++) {
        let minIndex = i
        for (let j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) minIndex = j
        }

        if (minIndex !== i) {
            let swap = array[minIndex]
            array[minIndex] = array[i]
            array[i] = swap
        }

        console.log(`${i}회전: [${array}]`)
    }
    return array
}

const array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
console.log(selectionSort(array)) // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

N + (N - 1) + (N - 2) + ... + 2

시간 복잡도 : 이중 반복문으로 인해, O(N²)
연산 횟수 : (N² + N) / 2
효율성 : 10,000 개 이상의 데이터에서는 속도가 급격히 느려진다.

선택 정렬은 다소 비효율적이다. 다만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.

삽입 정렬

특히 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어있을 때 효율적이다.
삽입 정렬은 특정한 데이터를 적절한 위치에 삽입 한다는 의미에서 삽입정렬이라고 부른다.

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞 까지의 데이터는 이미 정렬되어있다고 가정한다. 정렬되어있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이 특징이다. 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정 할 때 (삽입할 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
  # 인덱스 i 부터 1 까지 감소하여 반복
  for j in range(i, 0, -1):
    # 비교 후 SWAP
    if (array[j] < array[j - 1]):
      array[j],  array[j - 1] = array[j - 1], array[j]

    # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
    else:
      break

print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

function insertionSort (array) {
    for (let i = 1; i < array.length; i++) {
        let cur = array[i]
        let left = i - 1

        while (left >= 0 && array[left] > cur) {
            array[left + 1] = array[left]
            left--
        }

        array[left + 1] = cur
        console.log(`${i} 회전: [${array}]`)
    }
    return array
}



const array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
console.log(insertionSort(array)) // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

시간 복잡도 : 이중 반복문으로 인해, O(N²)
연산 횟수 : (N² + N) / 2
효율성 : 현재 리스트의 데이터가 거의 정렬되어있는 상태라면 매우 빠르게 동작함

퀵 정렬

퀵 정렬은 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 병합 정렬 은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.

퀵 정렬에서는 피벗 이 사용되는데, 큰 숫자와 작은 숫자를 교환할때, 교환하기 위한 기준으로 사용된다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야한다.

가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 설명하겠다. 호어 분할 방식에는 [리스트에서 첫 번째 데이터를 피벗으로 정한다] 라는 규칙을 가지고 있다.

피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
그 다음, 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 피벗에 대하여 정렬이 수행된다.
현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈리는 경우, 작은 데이터와 피벗의 위치를 변경한다
1 - 3 과정을 반복한다.

퀵 정렬에서는 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 이는 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다.

퀵 정렬의 종료 조건은, 현재 리스트의 데이터 개수가 1 개 인 경우 이다. 리스트의 원소가 1 개라면, 이미 정렬이 되어있다고 간주할 수 있으며, 분할이 불가능하다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start,end):
  if (start >= end): # 원소가 1 개 인 경우 종료
    return

  pivot = start # 피벗은 항상 첫 번째 원소로 설정
  left = start + 1
  right = end

  while (left <= right):
    # 왼쪽 - 피벗보다 큰 데이터를 찾을 때 까지 반복 이동
    while (left <= end and array[left] <= array[pivot]):
      left += 1

    # 오른쪽 - 피벗 보다 작은 데이터를 찾을 때 까지 반복 이동
    while (right > start and array[right] >= array[pivot]):
      right -= 1

    if (left > right):   # 엇갈릴 경우 작은 데이터와 피벗 교체
      array[right], array[pivot] = array[pivot], array[right]
    else:   # 엇갈리지 않은 경우 작은데이터와 큰 데이터 교체
      array[left], array[right] = array[right], array[left]

  # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

# 파이썬용 더 간결한 코드
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고있다면 종료
  if (len(array) <= 1):
    return array

  pivot = array[0] # 피벗은 첫 번째 요소
  tail = array[1:] # 피벗을 제외한 리스트

  left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
  right_side = [x for x in tail if x >= pivot] # 분할된 오른쪽 부분

  # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
  return quick_sort(left_side) + [pivot] + quick_sort(right_side) 

print(quick_sort(array))

function quickSort(arr){
  if(arr.length <= 1) return arr

  const pivot = arr[arr.length - 1]
  const leftarr = []
  const rightarr = []

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) leftarr.push(arr[i])
    else rightarr.push(arr[i])
  }

  return [...quickSort(leftarr) , pivot, ...quickSort(rightarr)]

}

const array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
console.log(quickSort(array)) // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

시간 복잡도 : 평균적으로는 O(NlogN) 최악의 경우 O(N²)
효율성 : 데이터가 무작위로 입력된 경우 빠르게 동작하지만, 이미 데이터가 정렬된 경우에는 느리게 동작한다.

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
데이터의 크기 범위가 제한되어 양의 정수 형태로 표현할 수 있을 때만 사용 가능

계수 정렬은 앞 의 3 가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한뒤에 위치를 변경하며 정렬하는 방식 (비교 기반의 정렬 알고리즘) 이 아니다.

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

# 모든 원소의 값이 0 보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언 (모든 값은 0 으로 초기화)
count = [0] * (max(array) + 1)

# 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(array)):
  count[array[i]] += 1

# 리스트에 기록된 정렬 정보 확인
for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ') # 등장한 횟수만큼 인덱스 출력

# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

0	1	2	3	4	5	6	7	8	9
`//`	`//`	`//`	`/`	`/`	`//`	`/`	`/`	`/`	`//`
`00`	`11`	`22`	`3`	`4`	`55`	`6`	`7`	`8`	`99`

시간 복잡도 : O(N + K) (최대값 K)
효율성 : 데이터의 범위만 한정되어있고, 데이터의 크기가 많이 중복되어있을수록 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.\
공간 복잡도 : 0, 999,999 두 개의 정수만 있는경우 100만 개의 리스트를 선언해야한다.
항상 사용할 수 있는 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

파이썬의 정렬 라이브러리 (sorted, sort)

# sorted()
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

# sort()
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

array.sort()
print(array)

# key 를 활용하여 정렬
array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
  return data[1]

result = sorted(array, key = setting)
print(result)
# [('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고있는지 물어보는 문제로, 기본 정렬 라이브러리의 사용 방법을 숙지하고있으면 어렵지 않게 풀 수 있다.
정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고있어야 문제를 풀 수 있다.
더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으론 풀 수 없으며, 계수 정렬등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

시간 복잡도 : 최선, 최악의 경우 모두 O(NlogN)
효율성 : 단순히 정렬해야하는 상황에서는 정렬 라이브러리를 사용하고, 더 빠르게 동작해야할 때는 계수 정렬을 사용하자
공간 복잡도 : 0, 999,999 두 개의 정수만 있는경우 100만 개의 리스트를 선언해야한다.
항상 사용할 수 있는 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

'BACKEND > 코딩테스트 및 solution' 카테고리의 다른 글

211227 다이나믹 프로그래밍 (0)	2022.01.16
211221 이진탐색 개념 (0)	2022.01.16
211126 탐색, 자료구조 개념 (0)	2022.01.16
211110 구현 개념 (0)	2022.01.16
211203 그리디 알고리즘 (0)	2021.12.03

평범하지않은 또야의 블로그

211208 정렬 개념

정렬 (Sorting)

선택 정렬

삽입 정렬

퀵 정렬

계수 정렬

파이썬의 정렬 라이브러리 (sorted, sort)

'BACKEND > 코딩테스트 및 solution' 카테고리의 다른 글

댓글

티스토리툴바

211208 정렬 개념

정렬 (Sorting)

선택 정렬

삽입 정렬

퀵 정렬

계수 정렬

파이썬의 정렬 라이브러리 (sorted, sort)

'BACKEND > 코딩테스트 및 solution' 카테고리의 다른 글

관련글

댓글

티스토리툴바