[Algorithm] 정렬 (sort)

moKo·2021년 10월 13일
0

Algorithm

목록 보기
4/5
post-thumbnail

정렬이란?

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
일반적으로 문제상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

  • 0~9의 데이터들이 순서없이 나열되있을때 0을 선택해 맨앞으로 가져와서 자리를 바꾸는식으로 정렬한다.

선택 정렬 소스코드

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)
       

삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택정렬에 비해 구현난이도가 높지만, 효율적이다.

  • 0~9의 데이터들이 순서없이 나열되있을때, 맨 처음의 데이터는 정렬이 되었다고 두고, 두번째부터 왼쪽 원소랑 비교하여 두번째원소가 더 작다면 왼쪽 위치로 넣어준다.
  • 계속 앞으로 비교하면서 비교 대상이 왼쪽보다 작으면 가장 작아질때까지 왼쪽으로 보내준다.

삽입 정렬 소스코드

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까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]: # 한 칸 왼쪽과 비교
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
            
print(array)

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되며, 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은, 첫 번째 데이터를 기준 데이터(pivot)로 설정한다.

  • 0~9의 데이터들이 순서없이 나열되있을때, 첫번째 데이터인 5를 피벗값으로 설정되었다고 가정하고 왼쪽에서 오른쪽으로 탐색하며 왼쪽에서 가장 가까운 피벗값보다 큰 수를 찾고, 오른쪽에서 왼쪽으로 탐색하며 오른쪽에서 가장 가까운 피벗값보다 작은 수를 찾아 그 둘의 위치를 서로 바꿔준다.
  • 계속 반복하다가 두 개의 탐색이 엇갈리는 순간이오면 작은 값과 피벗값의 위치를 서로 바꿔준다.
  • 그 후, 초기 피벗값 기준으로 왼쪽, 오른쪽으로 작은값, 큰값끼리 모이게 되는데 모인데로 다시 퀵 정렬을 수행한다.

퀵 정렬 소스코드

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

def quick_sort(list):
  // 원소가 1개 이하면 종료
  if len(list) <= 1 : return list
  // 중간쯤 있는 데이터를 피벗값으로 설정
  pivot = list[len(list) // 2]
  // 피벗보다 작은배열, 큰배열 선언
  less_arr, equal_arr, big_arr = [], [], []
  for i in list:
    if i < pivot: less_arr.append(i)
    elif i > pivot: big_arr.append(i)
    else: equal_arr.append(i)
  return quick_sort(less_arr) + equal_arr + quick_sort(big_arr)

print(quick_sort(list))

계수 정렬

특정한 조건 부합시에만 사용하지만 매우 빠르게 동작한다.
데이터 크기범위가 제한되어 정수형태로 표현할 수 있을 때 사용 가능하다.
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적이다.
데이터가 적거나 범위가 너무 크면 비효율적이다.
여러 학생의 점수를 정렬할 때 유용

  • 정렬되지 않은 데이터에서 각 데이터 숫자에 대한 인덱스값의 카운터를 1씩 올려준다. (데이터가 7이면 인덱스7번에 카운트 +1 한다.)
  • 모두 인덱스에 카운트 되었으면 인덱스 0부터 차례대로 출력한다. 카운트가 2이면 2번 출력한다.

계수 정렬 소스코드

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

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개의 원소를 가진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기란 A와 B의 원소끼리 교환하는 것이다. 최종목표는 A의 모든 원소의 합이 최대가 되도록 하는 것이다. N, K, A, B가 주어졌을 때 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하라.
n, k = map(int, input().split))
a = list(map(int, input().split))
b = list(map(int, input().split))

a.sort()
b.sort(reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]
    else:
        break
    
print(sum(a))
profile
🔥 Feelings fade, results remain

0개의 댓글