[알고리즘] 정렬 이란 ( 선택, 버블, 삽입 )

정렬 이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

 

정렬 알고리즘의 예시로는 선택, 버블, 삽입, 병합, 퀵 정렬 등이 있다.

---

1. 선택 정렬

 

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 

그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 하는 것으로

 

매번 가장 작은 것을 선택하는 알고리즘이다.

선택정렬 시각화

 

하나씩 정밀 비교가 가능하며, 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다.

따라서 교환이 많이 일어나는 문제에 효율적인 적용을 할 수 있다. 가장 적합한 문제는 역순 정렬이다.

 

하지만, 그만큼 자료 수 가 많은 문제에 대해서는 정밀 비교를 하게 되므로 속도가 떨어지는 단점이 있다.

 

 

선택 정렬 구현 Python

def selectsort(array):
    n=len(array)
    for i in range(n):
        num = i
        for j in range(i+1, n):
            if array[j] < array[num]:
                num = j
        array[i], array[num] = array[num], array[i]

전체 배열의 길이만큼 반복하면서, i번째 위치(= 처음에는 맨 앞자리가 되고, 다음 반복부터는 다음 자리가 됨)의 값과

i 위치 다음의 배열의 값들 중에서 제일 작은 값을 i 번째 위치에 넣으면서 정렬한다.

---

2.  버블 정렬

 

서로 인접한 요소끼리 크기 비교를 통해 정렬하는 알고리즘이다.

 

버블정렬 시각화

 

버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 구현이 쉽고 코드가 직관적이다.

하지만, n개 원소에 대해 n개의 메모리를 사용하기에 원소의 개수가 많아지면 비교 횟수가 많아져 성능이 저하된다.

 

버블 정렬 구현 Python

def bubblesort(array):
    n=len(array)
    for i in range(n):
        for j in range(n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]

전체 배열의 길이만큼 반복하면서, 현재 위치의 값과 다음 위치의 값의 대소 비교를 해서 정렬하는 방식이다.

---

3. 삽입 정렬

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 과정을 하는 것으로

 

'특정 데이터'를 적절한 위치에 삽입하는 알고리즘이다. 

 

삽입정렬 시각화

 

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

 

이미 정렬되어 있는 경우, 매우 효율적이고 정렬 하고자 하는 배열 안에서 교환하는 방식이므로,

다른 메모리 공간이 필요로 하지 않는다.

 

하지만, 배열 값들의 이동이 필요하므로 배열 길이가 길수록 비효율적이다.

 

삽입 정렬 구현 Python

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

전체 배열의 길이만큼 반복하면서, 뒤에서 부터 반복해 적절한 위치를 찾아서 정렬하는 방식이다.

---

정렬 알고리즘 시간 복잡도 비교

시간복잡도 비교 (출처:https://d2.naver.com/helloworld/0315536)