알고리즘 기초 - 정렬

반응형

이번 게시물에서는 꼭 알아야 할 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 계수 정렬에 대해서 설명하겠습니다. 

​

- 선택 정렬

1) 선택 정렬(Selection Sort)이란?

선택 정렬은 여러 개의 데이터가 무작위로 있을 때, 값이 가장 작은 데이터를 선택해 가장 앞에 있는 데이터와 교체하고, 두번째로 값이 작은 데이터를 선택해 앞에서 두번째로 작은 테이터와 바꾸는 과정을 반복하는 알고리즘입니다.

2) 정렬 예시

위 그림은 무작위 데이터인 [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]의 입력에 대해 선택 정렬을 수행하는 그림입니다. 위의 과정을 마지막 입력에 도착할 때 까지 반복해주면 됩니다! 

이를 코드로 작성하면 !

inputlist = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(inputlist)):
    minidx = i
    for j in range(i+1, len(inputlist)):
        if inputlist[minidx] > inputlist[j]:
            minidx = j
    inputlist[i], inputlist[minidx] = inputlist[minidx], inputlist[i]

값 하나하나마다 반복문을 거쳐야 하기 때문에 시간복잡도 측면에서 매우 비효율적입니다.

 

 

두번째 정렬 방법입니다.

- 삽입 정렬

1) 삽입 정렬(Insertion Sort)이란?

삽입 정렬은 여러 개의 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입해주는 알고리즘입니다. 이 방법은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 아주 효과적입니다.

2) 정렬 예시

위 그림은 무작위 데이터인 [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]의 입력에 대해 삽입 정렬을 수행하는 그림입니다. 각 데이터를 하나씩 검사하여 적절한 위치에 끼워넣는 과정을 확인할 수 있습니다. 이 과정을 모든 데이터에 대해 반복합니다.

이를 코드로 작성하면 !

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

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

 

 

 

세번째 정렬 방법입니다.

- 퀵 정렬

1) 퀵 정렬(Quick Sort)란?

퀵 정렬은 앞의 두 알고리즘과 다르게 기준이 되는 값을 설정해야 합니다. 이를 기준 데이터(pivot)이라고 합니다. 기준을 설정한 다음 그 값을 기준으로 큰 수와 작은 수를 교환하여 입력 리스트를 반으로 나누는 방식으로 작동합니다.

2) 정렬 예시

첫번째 데이터를 기준으로 정하고 왼쪽에서부터 기준보다 큰 수를, 오른쪽에서 부터는 기준보다 작은 수를 찾습니다. 그 후 두 수의 위치를 바꿔줍니다. 이 과정을 반복하다보면 큰 수가 오른쪽에서, 작은 수가 왼쪽에서 찾아지는 경우가 발생하게 되는데, 이때! 작은 수와 기준값의 위치를 바꿔주고 작은 수를 새로운 기준값으로 설정해줍니다. 이 후 이와 같은 과정을 반복하면 됩니다.

​

이를 코드로 작성하면 !

(재귀를 이용해 구현합니다.)

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

def quick_sort(inputlist):
    if len(inputlist)<=1:
        return inputlist
    pivot = inputlist[0]
    newlist = inputlist[1:]
    
    left = [x for x in newlist if x<=pivot]
    right = [x for x in newlist if x>pivot]
    
    return quick_sort(left) + [pivot] + quick_sort(right)

 

 

네번째 정렬 방법입니다.

- 병합 정렬

1) 병합 정렬(Merge Sort)이란?

병합 정렬은 입력을 항상 반으로 나누는 분할과 병합을 반복하는 방법입니다. 입력을 여러 개의 작은 입력으로 분할 한 뒤 각각 정렬하고, 분할된 것들을 나중에 합치는 방식으로 동작합니다. 이를 "분할 정복 == Divide and Conquer"라고 합니다. 

2) 정렬 예시

입력의 리스트의 길이가 1이 될 때까지 계속 반으로 나누고 1이되면 합쳐야할 리스트의 값들과 크기를 비교하면서  하나로 합쳐줍니다.

​

이를 코드로 작성하면 !

3) python 코드

def merge_sort(data):
  result = []
  mid = (len(data))//2

  if len(data) == 1 :
    return data

  left = merge_sort(data[:mid])
  right = merge_sort(data[mid:])
  li = rj = 0

  while li<len(left) and rj<len(right):
    if left[li] < right[rj]:
      result.append(left[li])
      li = li+1
    else:
      result.append(right[rj])
      rj = rj+1

  result += left[li:]
  result += right[rj:]

  return result

 

 

네번째 정렬 방법입니다.

- 계수 정렬

1) 계수 정렬(Count Sort)이란?

이름 그대로, 데이터 값의 갯수를 이용하는 정렬 방법입니다. 입력으로 들어온 데이터를 하나씩 검사하여 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨 후, 최종적으로 증가된 수만큼 해당 index의 데이터를 출력합니다. 이 알고리즘은 데이터의 최댓값이 크지 않을 때 매우 빠르지만 데이터 크기의 범위가 제한되어 있을때만 사용할 수 있다는 단점이 있습니다. 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합한 알고리즘입니다!

 

이를 코드로 작성하면 !

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

cntlist = [0] *(max(inputlist)+1)
for i in range(len(inputlist)):
    cntlist[inputlist[i]] += 1
for i in range(len(cntlist)):
    for j in range(len(cntlist[i])):
        print(i, end=' ')