이것이 코딩 테스트다 - Chapter6 정렬 정리

"정렬" 이란

연속된 데이터를 기준에 따라서 순서대로 나열하기 위한 알고리즘

 

정렬의 경우 항상 사용하게 되는 기법중 하나이다.

최소값, 최대값을 구하기 위하여 정렬 후 맨앞, 맨뒤 데이터를 접근하기 때문이다.

 

또한, 정렬이 되면 뒤에서 배울 "이진탐색"이 가능하여 진다.

여기서 정렬의 방법이 다양하지만, 그중 4가지 정렬에 대하여 알아보겠다.

 

1. 선택 정렬

정렬이 안된 부분 중 가장 작은값을 맨 앞으로 보내는 방법이다.

이중 for문을 통해 구현한다.

array = [7,5,9,0,3]

배열이 이렇게 주어져 있다면

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]

이 코드를 통해 정렬이 되는 과정은 다음과 같습니다.

 

1. [0, 5, 9, 7, 3] : 0번째 인덱스값 수정

2. [0, 3, 9, 7, 5] : 1번째 인덱스 값 수정

3. [0, 3, 5, 7, 9] : 2번째 인덱스 값 수정

4. [0, 3, 5, 7, 9] : 3번째 인덱스 값 (그대로)

 

시간복잡도 : O(N^2)

 

2. 삽입 정렬

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.

앞쪽은 정렬되어 있으며, 각 데이터를 정렬된 부분에서 적절한 위치에 넣는 식이다.

앞쪽의 값이 큰경우 계속하여 자리를 바꾸는 식이다.

 

array = [7,5,9,0,3]

배열이 이렇게 주어져 있다면

for i in range(1, len(array)) :
  for j in range(i, 0, -1) :
    if array[j] < array[j-1] :
      array[j], array[j-1] = array[j-1], array[j]
    else :
      break

이 코드를 통해 정렬이 되는 과정은 다음과 같습니다.

 

1. [7, 5, 9, 0, 3] : 0번째까지 정렬 완료

2. [5, 7, 9, 0, 3] : 1번째까지 정렬 완료

3. [5, 7, 9, 0, 3] : 2번째 까지 정렬 완료

4. [0, 5, 7, 9, 3] : 3번째 까지 정렬 완료

5. [0, 3, 5, 7, 9] : 4번째 까지 정렬 완료

 

시간복잡도 : O(N^2) but 정렬이 거의 되어있는 경우 빠르게 동작한다.

 

 

3. 퀵 정렬

기준점 데이터를 설정하여 작은값들과 큰값들로 나누어 정렬한다.

나눠진 왼쪽, 오른쪽 리스트를 또다시 기준점을 설정 후 정렬하는 식으로 작동된다.

 

array = [7,5,9,0,3]

배열이 이렇게 주어져 있다면

def quick_sort(array, start, end) :
  if start >= end : #종료조건
    return

  pivot = start
  left = start+1
  right = end

  while left <= right :
    while left <= end and array[left] <= array[pivot] :
      left += 1 #pivot 보다 큰 값을 찾는다
    while right > start and array[right] >= array[pivot] :
      right -= 1 #pivot 보다 작은 값을 찾는다
    
    if left > right :
      array[right], array[pivot] = array[pivot], array[right] #엇갈린 경우 povot과 위치를 바꾼다
    else :
      array[left], array[right] = array[right], array[left] #정상의 경우 크고 작은 값끼리 바꾼다

  quick_sort(array, start, right-1) #povot 왼쪽을 정렬한다
  quick_sort(array, right+1, end) #pivot 오른쪽을 정렬한다

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

스와이프를 통해 기준점을 토대로 작은값, 큰값으로 나뉘게 된다.

좀 복잡한 방식이므로 파이썬용 코드를 통해 더 간결하게 구할 수 있다.

 

def quick_sort(array) :
  if len(array) <= 1 :
    return array

  pivot = array[0] #pivot 설정
  tail = array[1:] #pivot 뒤의 array

  left_side = [x for x in tail if x <= pivot] #array 에서 pivot 보다 작은값을들 left_side로 넣는다
  right_side = [x for x in tail if x > pivot] #array 에서 pivot 보다 큰값들을 right_size로 넣는다

  return quick_sort(left_side) + [pivot] + quick_sort(right_side) #작은값들, 기준점, 큰값들을 한 리스트로 묶는다

리스트 내에서 기준점보다 작은값들, 큰값들을 리스트로 구하여 한 리스트로 다시 반환하는 식이다.

 

이 코드를 통해 정렬되는 과정은 다음과 같습니다.

 

1. [0, 3, 5] + [7] + [9]

2. [] + [0] + [3, 5] + [7] + [] + [9] + []

3. [] + [0] + [] + [3] + [5] + [7] + [] + [9] + []

-> [0, 3, 5, 7, 9]

 

시간복잡도 : O(NlogN) but 정렬이 거의 되어있는 경우 느리게 동작

 

 

4, 계수 정렬

최소, 최대 데이터를 담을 수 있는 범위의 리스트를 만들어 해당위치의 카운터를 증가시키는 식이다.

보통 정수의 데이터이며 데이터의 크기 범위가 제한된 경우에 빠르게 작동된다.

동일한 값이 여려번 있는 경우에 가장 좋다.

 

array = [7,5,9,0,3]

배열이 이렇게 주어져 있다면

count = [0]*(max(array)+1) #array의 최고수+1만큼 크기설정

for i in range(len(array)) :
  count[array[i]] += 1 #해당수의 count 증가

for i in range(len(count)) :
  for j in range(count[i]) :
    print(i, end=" ") #해당수를 count만큼 출력

해당 수에 대항하는 count를 증가시키면서

count 개수만큼 수를 가지고 있는 식이다.

 

이 코드를 통해 정렬이 되는 과정은 다음과 같습니다.

 

1. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] : 0부터 9까지 담을 수 있는 배열을 생성

2. [0, 0, 0, 0, 0, 0, 0, 1, 0, 0] : 7에 해당 count를 증가

3. [0, 0, 0, 0, 0, 1, 0, 1, 0, 0] : 5에 해당 count를 증가

4. [0, 0, 0, 0, 0, 1, 0, 1, 0, 1] : 9에 해당 count를 증가

5. [1, 0, 0, 0, 0, 1, 0, 1, 0, 1] : 0에 해당 count를 증가

6. [1, 0, 0, 1, 0, 1, 0, 1, 0, 1] : 3에 해당 count를 증가

-> [0, 3, 5, 7, 9]

 

시간복잡도 : O(N+K)

 

 

이렇게 네가지 정렬 방법에 대해 알아보았습니다.

 

다음으로는 파이썬 기본내장 정렬 라이브러리에 대해 알아보겠습니다.

5. 파이썬 기본 정렬 sort(), sorted()

파이썬에서는 정렬 라이브러리를 제공합니다. 이를 통해 손쉽게 정렬을 할 수 있습니다.

 

array = [7,5,9,0,3]

배열이 이렇게 주어져 있다면

result = sorted(array)

이 코드를 통해 정렬된 배열을 따로 저장하여 얻을 수 있습니다.

 

이때, sorted에 key값을 넣으면 key에 따라 정렬을 할 수 있습니다.

for i in range(N) :
  name, score = map(str, input().split())
  array.append((name, int(score)))

array = sorted(array, key = lambda data: data[1]) #score에 따라 정렬하기

 

array.sort()

이코드를 통해 배열 내부에서 정렬를 할 수 있습니다.

 

시간복잡도 : O(NlogN)

 

 

이렇게 정렬방법에 대해 알아보았습니다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/정렬

CodingTestStudy/FreeDeveloper_Cote