[이코테] 정렬

샤이니·2022년 1월 21일

알고리즘 이코테 정렬

이코테

목록 보기

4/8

정렬이란?
=> 데이터를 특정한 기준에 따라서 순서대로 나열

프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 많이 사용되는 알고리즘 중 하나다.
정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary search)가 가능해진다.
모두 오름차순 정렬을 수행. 내림차순 정렬의 경우에는 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다. => 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드(Reverse)를 제공한다.

선택 정렬(selction sort)

=> 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?

매번 "가장 작은 것을 선택"한다는 의미에서 "선택"정렬 알고리즘이라고 한다.

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
  array[i], array[min_index] = array[min_index], array[i] #스와프

print(array)

*시간 복잡도 : O(N제곱)

선택 정렬은 기본 정렬 라이브러리나 뒤에서 다룰 알고리즘에 비해서 매우 비효율적. 그러나 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 형태는 알아두어야 함.

삽입 정렬(insertion sort)

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?!

삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘
필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적
선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 바꾸는 반면 삽입 정렬은 그렇지 않다.
삽입 정렬은 특정한 데이터를 적절한 위치에 "삽입" 한다는 의미에서 "삽입 정렬"
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징
삽입 정렬은 두번째 데이터 부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
삽입 정렬의 특징으로는 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다.

-> 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(삽입할 위치를 찾기 위하여 한 칸씩 이동할 때),삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

#삽입 정렬

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

for i in range(1, len(array)) :
  for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
    if array[j] &lt; array[j -1]:  #한 칸씩 왼쪽으로 이동
        array[j], array[j -1] = array[j -1], array[j]
    else: #  자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      break
print(array)

cf)range의 세 번쨰 매개 변수
range의 매개 변수는 3개(srart, end, step)이다. 세 번째 매개변수에 -1이 들어가면 start인덱스 부터 시작해서 end +1 인덱스까지 1씩 감소한다.

*시간 복잡도 : O(N제곱)

현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

퀵 정렬(quick sort)

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
퀵 정렬에서는 피벗(pivot)이 사용된다. 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 "기준"을 바로 피벗이라고 표현한다.
퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것이지 미리 명시해야 하는데, 우리는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 퀵 정렬을 설명.
호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다.
퀵 정렬에서는 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.
=> 재귀 함수와 동작원리가 같다
재귀함수와 동작 원리가 같다면, 종료 조건도 있어야 할것.
=> 현재 리스트의 데이터 개수가 1개인 경우
=> 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다.

#퀵 정렬

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


def quick_sort(array, start, end) :
  if start &gt;= end: #원소가 1개인 경우 종료
    return
  pivot = start
  left = start + 1
  right = end
  while left &lt;= right:
    #피벗보다 큰 데이터를 찾을 때까지 반복
    while left &lt;= end and array[left] &lt;= array[pivot]:
      left += 1

    #피벗보다 작은 데이터를 찾을 때까지 반복
    while right &gt; start and array[right] &gt;= array[pivot]:
      right -= 1

    if left &gt; 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)</code></pre>

#퀵 소트,시간 면에서는 비효율

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


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

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


  left_side = [x for x in tail if x &lt;= pivot] #분할된 왼쪽 부분
  right_side = [x for x in tail if x &gt;= pivot] #분할된 오른쪽 부분




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

print(quick_sort(array))

퀵 정렬의 시간 복잡도 : 평균 시간 복잡도는 O(NlogN). 삽입과 선택에 비해 매우 빠르다.

=> 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 데이터의 개수가 n개라면 높이는 logN이 된다. (책 그림 참고)

다시말해 분할이 이루어지는 횟수가 기하급수적으로 감소하게 된다.
- 일반적으로 컴퓨터 과학에서 Log의 의미는 밑이 2인 로그를 의미
- 평균적으로는 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(n제곱)이라는것
  => 데이터가 무작위로 입력되는 경우 퀵정렬을 매우 빠르게 동작하지만, 하지만 위와 같이 호어방식분할을 사용해 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, "이미 데이터가 정렬되어 있는 경우"에는 매우 느리게 동작한다.

계수 정렬(count sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.
"데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때"만 사용할 수 있다.
따라서 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기가 어렵다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
-> 계수 정렬이 이러한 특징을 가지는 이유는 계수 정렬을 이용할 때는 **모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언**해야 하기 때문이다.
계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘 처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.

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

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)

print(max(array))

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 =' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 시간 복잡도
=> 데이터의 개수를 N, 데이터 중 최대값의 크기를 k라고 할때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.
=> 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.

계수 정렬의 공간 복잡도
=> 계수 정렬은 때에 따라서 심각한 비효율성을 초래 할 수 있다. ex) 데이터가 0과 999,999 단 2개만 존재한다고 가정. 이럴 때에도 리스트의 크기가 100만개가 되로고 선언해야 한다.
=> 따라서 항상 사용할 수 있는 알고리즘은 아니고, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합.

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted()함수를 제공한다.

<sorted()함수>
- 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐.
- 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.
- 리스트, 딕셔너리 자료형을 입력받아서 정렬된 결과를 리스트 자료형으로 출력

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

result_1 = sorted(array #sorted 함수

array.sort() # sort함수 별도의 정렬된 리스트가 반환되지 않고, 내부 원소가 바로 정렬

print(result_1)
print("------------")
print(array)


array_1 = [("바나나", 2), ("사과", 5), ("당근", 3)]

def setting(data):
  return data[1]

result = sorted(array_1, key = setting)
print(result)

sorted()나 sort()를 이용할때에는 key 매개변수를 입력받을 수 있다. key값으로는 하나의 함수가 들어가야하며 이는 정렬 기준이 된다.
정렬 라이브러리의 시간 복잡도
- 항상 최악의 경우에도 시간 복잡도 O(NlonN)을 보장한다.
- 이미 잘 작성된 함수
- 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

#N을 입력받기

n = int(input())

#N개의 정수를 입력받아 리스트에 저장

array = []
for i in range(n):
  array.append(int(input()))

array = sorted(array, reverse = True)

for i in array:
  print(i, end = " ")</code></pre>
<h2 id="성적이-낮은-순서로-학생-출력하기">성적이 낮은 순서로 학생 출력하기</h2>
<pre class=" language-null"><code class=" language-null">#N을 입력받기
n = int(input())


#N명의 학생 정보를 입력받아 리스트에 자장
array = []
for i in range(n):
  input_data = input().split()
  #이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
  array.append((input_data[0], int(input_data[1])))


#키(key)를 용하여, 점수를 기준으로 정렬
array = sorted(array, key = lambda student: student[1])

#정렬이 수행된 결과를 출력
for student in array:
  print(student[0], end = '')

두 배열의 원소 교체

n, k = map(int, input().split())

# N과 K를 입력받기
a = list(map(int, input().split())) #배열 A의 모든  원소를 입력받기
b = list(map(int, input().split())) #배열 B의 모든 원소를 입력받기

a.sort() #배열 A는 오름차순 정렬 수행
b.sort(reverse = True) #배열 B는 내림차순 정렬 수행


for i in range(k):
  #A의 원소가 B의 원소보다 작은 경우
  if a[i] &lt; b[i]:
    # 두 원소를 교체
    a[i], b[i] = b[i], a[i]
  else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
    break   



print(sum(a)) #배열 A의 모든 원소의 합을 출력

샤이니

이전 포스트

[이코테] DFS & BFS

다음 포스트