[Algorithm]정렬 알고리즘 -1 (Sorting Algorithm)

---

✏️ 정렬 알고리즘이란?

 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 일상 생활은 물론, 많은 상황에서 사용되는 방법이며 사람들에게 매우 익숙한 알고리즘이다.

 정렬의 기준은 보통 오름차순, 내림차순 등이 있으며 데이터를 해석하는 데 있어 중요한 역할을 한다.

❗️왜 정렬 알고리즘을 사용하는가?

• 컴퓨터는 수백만개의 데이터를 다루기 때문에 일관된 기준으로 데이터를 정리할 필요가 있다.
• 데이터가 정렬되어 있을 경우 이진탐색을 사용하여 시간복잡도를 줄일 수 있다.

✏️ 정렬알고리즘의 종류

• $O(n^2)$ 정렬 알고리즘
  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬
• $O(nlogn)$ 정렬 알고리즘
  • 퀵 정렬
  • 병합 정렬
  • 트리 정렬
  • 힙 정렬
• 특수 알고리즘
  • 계수 정렬
  • 기수 정렬

버블 정렬(Bubble Sort)

 버블 정렬이란 현재의 자신과 그 다음을 비교하여 다음 숫자가 더 작다면 서로의 위치를 바꾸는 작업을 정렬이 모두 끝날 때까지 반복하는 방법이다.

 최선의 경우(자료가 이미 정렬된 경우)에는 0번 정렬하지만 최악의 경우에는 $n(n-1)/2$번 정렬한다. 효율적인 알고리즘은 아니기 때문에 자주 사용되는 방식은 아니지만 특수한 상황에서는 사용될 수 있는 정렬 방법이다.

python 구현 방법

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

def bubbleSort(data):
	for i in range(len(data) - 1):
    	for j in range(i):
        	if data[j] > data[j+1]:
            	data[j], data[j+1] = data[j+1], data[j]
    return data

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

선택 정렬(Selection Sort)

 선택 정렬이란 가장 작은 숫자를 앞으로 밀어주는 방법이다. 제자리 정렬 알고리즘의 하나로 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다. 1번째 요소부터 마지막 요소까지 가장 작은 수가 1번째, 2번째 요소부터 마자막 요소까지 가장 작은 수가 2번째가 되는 방식으로 $n(n-1)$번 반복한다.

 어떤 자료가 주어지든 일관되게 $n(n-1)/2$에 비례하는 시간이 걸리고 버블 정렬보다 시간이 빨리 걸린다는 장점이 있음.

python 구현 방법

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

def selectionSort(data):
    for i in range(len(data)):
        idx = i
        for j in range(i + 1, len(data)):
            if data[idx] > data[j]: idx = j
        data[i], data[idx] = data[idx], data[i]
    return data

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

삽입 정렬(Insertion Sort)

 삽입 정렬이란 직관적인 정렬 방법으로 현재 위치에서 가장 작은 숫자를 적절한 위치로 이동시키는 방법이다. 일상적으로 가장 많이 사용하는 방법으로 도서관의 책 정리와 같이 정렬하지 않은 곳을 하나씩 순차적으로 진행하는 방법이다.

 이러한 방식은 크게 두 가지가 있는데 적절한 위치에 다다를 때까지 계속해서 배열 위치를 바꾸거나, 아예 해당 위치에 값을 넣고 나머지를 미는 방식으로 진행된다. 다만, 배열을 미는 건 전체 배열이 커질수록 비용도 커지기 때문에 위치를 바꾸며 진행하는 것이 좋다.

python 구현 방법

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

def insertionSort(data):
    for idx in range(1, len(data)):
        i = idx
        while i > 0 and data[i - 1] > data[i]:
            data[i - 1], data[i] = data[i], data[i - 1]
            i -= 1
    return data

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