1.선택 정렬(Insertion Sort)

1.선택 정렬이란?🤷‍♂️

배열에서 가장 작은 원소를 찾아 첫번째 원소와 교환하고,
두번째 작은 원소를 찾아 두번째 원소와 교환하고...이 방식이 끝까지 반복되는 제자리 정렬방식이다.

2.성능 특징

1.전체 시간 복잡도는 $O(N^2)$

위의 그림처럼 배열 [None,3,2,5,1,4]가 있다.(None은 무시하고 3,2,5,1,4를 정렬)
첫번째 원소 3은 가장 작은 원소를 찾기 위해 두번째 인덱스~끝까지 비교를 실시한 후 교환한다.
두번째 원소 2는 두번째 작은 원소를 찾기 위해 세번째 인덱스~끝까지 비교를 실시한 후 교환한다.
세번째 원소 5는 세번째 작은 원소를 찾기 위해 네번째 인덱스~끝까지 비교를 실시한 후 교환한다.
...(반복)
이러한 방식으로 N번째 원소는 N-1번의 비교를 해야된다. 따라서 전체 비교횟수는 N(N-1)/2이고, 전체 시간 복잡도는 $O(N^2)$ 가 된다.

2.적합한 상황

비교 횟수는 많지만 실제 교환되는 건 상대적으로 적기 때문에 작은 키와 큰 레코드를 가지는 화일을 정렬할 때 적합하다.

3.입력배열에 대한 민감도가 낮음

정렬하고자 하는 데이터가 정렬, 역정렬, 랜덤한 것과 크게 상관없이 비슷한 시간과 비용이 든다. 탐색범위가 일정하고 n번째로 작은 원소를 탐색해서 i번째와 교환하기 때문이다.

4.불안정한 정렬🤔

중복 값에 대해 기존의 순서가 유지되지 않을 수 있다.

[B b a c]라는 배열이 있고 a>b=B>c 라면,
선택정렬의 결과가 [a b B c]이기 때문이다. b와 B가 값이 같아도 정렬 후 순서가 같지 않기 때문에 불안정하다고 말한다.

3.코드

def selectionSort(a,n):
    for i in range(1,n):
        minIndex = i
        for j in range(i+1, n+1):
            if a[minIndex] > a[j]:
                minIndex = j
        a[minIndex], a[i] = a[i],a[minIndex]

import random, time

N = 5000
a = []
a.append(None)
for i in range(N):
    a.append(random.randint(1,N))
selectionSort(a, N)

2.버블 정렬(Bubble Sort)

1.버블 정렬이란?🍺

루프를 한 번 반복하는 과정동안 더 큰 값이 뒤쪽으로 이동하는데, 결국 가장 큰 값의 원소가 가장 뒤쪽으로 이동하는 제자리 정렬 방식이다. 거품이 물 위로 올라가는 것 같다고해서 버블정렬이라한다.

gif 출처)https://commons.wikimedia.org/wiki/File:Sorting_bubblesort_anim.gif

위 그림처럼 버블 정렬은 배열 길이와 같은 횟수의 루프를 돌게 되어 있다. 길이가 5이면 큰 루프5개인 것이다. 그리고 루프 안의 루프에서는 배열 첫번째 원소부터 정렬된 원소까지 비교하며 자리를 교환해 나간다.

2.성능 특징

1.전체 시간 복잡도 $O(N^2)$

버블정렬은 N개의 원소들이 각각 N-1번의 비교를 하므로 전체 비교횟수는 N(N-1)/2이고, 전체 시간 복잡도는 $O(N^2)$ 가 된다.

2.적합한 상황

레코드를 계속 교환하기 때문에 레코드 크기가 크면 적합하지 않다. 다만 거의 정렬이 된 화일인 경우 유리하다.

3.입력배열에 대한 민감도가 높음😈

정렬하고자하는 데이터가 역순인 경우 비교와 교환이 모두 이루어지기 때문에 차이가 심하다.
아래 코드처럼 실행시간측정을 적용하면

	start_time = time.time()
    bubbleSort(a, N)
    end_time = time.time() - start_time

1.정렬인 경우 1.273초

2.역정렬인 경우 3.491초

이처럼 시간 차이가 2.5배 이상 차이가 나는 걸 알 수 있다.

4.안정한 정렬

선택정렬과 달리 안정적인 정렬방법이다.

[B b a c]라는 배열이 있고 a>b=B>c 라면,
버블정렬의 결과가 [c B b a]이기 때문이다. 타깃 인덱스와 타깃 인덱스+1의 값을 비교 후 교환하기 때문에 중복된 값 B,b의 순서가 바뀔 수 없다.

3.코드

def bubbleSort(a,n):
    for i in range(n+1,1,-1):
        for j in range(1,i-1,1):
            if a[j] > a[j+1]:
                a[j],a[j+1] = a[j+1],a[j]
           
import random, time

# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    N = 300
    a = []
    a.append(None)
    for i in range(N):
        a.append(random.randint(1,N))
    bubbleSort(a, N)

3.삽입 정렬(Selection Sort)

1.삽입 정렬이란?🪄

타깃인덱스의 원소를 차례대로 적절한 위치에 삽입할 수 있을 때까지 이전의 나머지 원소들을 하나씩 오른쪽으로 이동시키는 제자리 정렬방식이다.

gif출처)https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

위의 그림을 보면 파랑색이 타깃 원소이며 설명은 오름차순 기준으로 한다.
삽입 정렬은 타깃 원소를 k라는 변수에 따로 담아두고, k보다 작거나 같은 원소가 나올때까지 왼쪽원소를 오른쪽으로 이동시킨다. 작거나 같은 원소가 나오면 그 원소의 다음 인덱스자리에 k값을 넣어준다. 이게 루프 하나의 과정이다. 타깃원소를 배열의 끝원소까지 반복하면 정렬이 완료된다.

2.성능 특징

1.전체 시간 복잡도 $O(N^2)$

2.적합한 상황

레코드를 계속 이동시켜야 해서 레코드의 크기가 큰 경우 불리하고, 거의 정렬된 화일의 경우 유리하다.

3.입력배열에 대한 민감도가 높다😈

버블정렬과 비슷하게 값을 비교한 결과에 따라 값 삽입이 있으므로 역정렬과 정렬된 배열의 시간소모가 차이가 크다.
1.정렬인 경우 0.004초

2.역정렬인 경우 2.320초

4.안정적인 정렬

[B a b c]라는 배열이 있고 a>b=B>c 라면,
삽입정렬의 결과가 [c B b a]이기 때문이다. 타깃 원소보다 작거나 같은 경우 그 원소의 바로 다음 인덱스의 원소로 삽입하기 때문에 중복값의 순서가 바뀔 수 없다.

3.코드

def insertionSort(a,n):
    for i in range(2,n+1):
        k = a[i]
        j = i - 1
        while((j>=1)&(a[j]>k)):
            a[j+1] = a[j]
            j=j-1
        a[j+1] = k

import random, time

# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    N = 5000
    a = []
    a.append(None)
    for i in range(N,0,-1):
        a.append(i)
    insertionSort(a, N)
    

참고자료 출처😊

https://devlog-wjdrbs96.tistory.com/53
https://mygumi.tistory.com/94
https://commons.wikimedia.org
알고리즘과 파이썬(Algorithms and python) 채진석 저