알고리즘 - 기본정렬

• 데이터 셋이 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다.
• 기본 정렬 알고리즘에는 3가지가 있다.
  • 선택 정렬(Selection Sort)
  • 버블 정렬(Bubble Sort)
  • 삽입 정렬(Insertion Sort)

 

---

선택 정렬(Selection Sort)

• 주어진 데이터들 중 현재 위치에 맞는 데이터를 선택해 위치를 교환하는 정렬 알고리즘이다.
• \(O\left ( n^{2}\right )\) 의 시간 복잡도를 가지고 있다.
  • 전체 리스트에 대해 N번의 최솟값 탐색이 필요하다.

동작 방법

정렬되지 않은 값들 중 최솟값을 찾는다.

 

맨 앞 인덱스의 값과 교체한다.

모든 인덱스가 정렬될 때까지 해당 과정을 반복한다.

 

코드 구현

# 오름차순

def selectionSort(arr):
    n = len(arr)

    for i in range(n-1):        # 배열의 처음부터 마지막진전까지 반복
        min_index = i           # 가장 작은 원소의 인덱스 저장
        for j in range(i+1, n):
            if arr[j] < arr[min_index]: # i 이후 원소들 중 최솟값 탐색
                min_index = j

        # 최솟값을 i의 원소와 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]
        
arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
selectionSort(arr)
print("선택 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

 

출력결과

 

내림차순은 부등호만 바꾸면 된다.

# 내림차순

def selectionSort(arr):
    n = len(arr)

    for i in range(n-1):        
        min_index = i           
        for j in range(i+1, n):
            if arr[j] > arr[min_index]: # i 이후 원소들 중 최댓값 탐색
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
selectionSort(arr)
print("선택 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

출력결과

---

버블 정렬(Bubble Sort)

• 두 인접한 원소를 검사해 정렬하는 알고리즘
  • 한 리스트에 대해 하나의 사이클을 돌면 최대값이 맨 오른쪽에 위치하게 된다.
• \(O\left ( n^{2}\right )\) 의 시간 복잡도를 가지고 있다

 

 동작 방식

초기 리스트

첫번째 사이클

1. 앞에서부터 가장 인접한 7과 4를 비교했을 때 7이 더 크므로 교환한다. [ 4, 7, 5, 1, 3 ]
2. 7과 5를 비교했을 때 7이 더 크므로 교환한다. [ 4, 5, 7, 1, 3 ]
3. 7과 1을 비교했을 때 7이 더 크므로 교환한다. [ 4, 5, 1, 7, 3 ]
4. 7과 3을 비교했을 때 7이 더 크므로 교환한다. [ 4, 5, 1, 3, 7 ]

첫번째 사이클이 끝난 배열 상태

두번째 사이클

1. 4와 5를 비교했을 때 4가 더 작으므로 교환하지 않는다. [ 4, 5, 1, 3, 7 ]
2. 5와 1을 비교했을 때 5가 더 크므로 교환한다. [ 4, 1, 5, 3, 7 ]
3. 5와 3을 비교했을 때 5가 더 크므로 교환한다. [ 4, 1, 3, 5, 7 ]
4. 가장 큰 값이 맨 끝으로 이동하므로 2회전부터는 가장 끝 값과 비교하지 않는다!!

두번째 사이클이 끝난 배열상태

 

세번째 사이클

1. 4와 1을 비교했을 때 4가 더 크므로 교환한다. [ 1, 4, 3, 5, 7 ]
2. 4와 3을 비교했을 때 4가 더 크므로 교환한다. [ 1, 3, 4, 5, 7 ]
3. 4와 5를 비교했을 때 4가 더 작으므로 교환하지 않는다. [ 1, 3, 4, 5, 7 ]
4.  

세번째 사이클이 끝난 배열상태

네번째 사이클

1. 1과 3을 비교했을 때 1이 더 작으므로 교환하지 않는다.

 

오름차순 완성상태

버블정렬 완성!

코드 구현

# 오름차순
def bubbleSort(arr):
    n = len(arr)	# 배열의 크기 측정
    for i in range(n):
        for j in range(0, n-i-1):	# 배열 크기에서 i값과 1을 뺀 만큼 반복
        	# 만약 현재 인덱스의 값이 다음 인덱스 값보다 클 경우
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]	# 위치 교환

arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
bubbleSort(arr)
print("버블 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

 

출력결과

 

# 내림차순
def bubbleSort(arr):
    n = len(arr)	# 배열의 크기 측정
    for i in range(n):
        for j in range(0, n-i-1):	# 배열 크기에서 i값과 1을 뺀 만큼 반복
        	# 만약 현재 인덱스의 값이 다음 인덱스 값보다 클 경우

            if arr[j] < arr[j+1]:   # 앞의 원소가 뒤의 원소보다 작으면 
                arr[j], arr[j+1] = arr[j+1], arr[j]	# 위치 교환
                # 결과적으로 가장 작은 값이 맨 뒤로 밀려나도록

arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
bubbleSort(arr)
print("버블 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

 

출력결과

---

삽입 정렬(Insertion Sort)

• 배열의 모든 요소를 이전 정렬된 데이터와 차례대로 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘
• 즉 2번째 요소부터 시작하여 앞쪽과 비교한다.
• \(O\left ( n^{2}\right )\) 의 시간 복잡도를 가지고 있다. (최선의 경우 O(n))

 

 동작 방식

초기상태

첫번째 사이클

1. 두번째 요소 4, 정렬된 데이터는 첫번째 요소인 5
2. 4와 5를 비교해서 교환한다.
3.  

첫번째 사이클 후 배열상태

 

두번째 사이클

1. 정렬할 데이터: 1, 1보다 앞의 데이터들을 기준으로 적절한 위치에 삽입
2. 1이 값이 제일 작으므로 0번째 인덱스로 삽입
3.  

두번째 사이클 후 배열상태

세번째 사이클

1. 정렬할 데이터: 3 
2. 3의 값은 1보다 크므로 1번째 인덱스에 삽입
3.  

세번째 사이클 후 배열상태

 

네번째 사이클

1. 정렬할 데이터: 2
2. 2의 값은 1보다는 크고 3보다는 작으므로 1번째 인덱스에 삽입
3.  

정렬 끝!

 

 

코드 구현

#오름차순
def  InsertionSort(arr):
    n = len(arr)
    for i in range(1, n):   # 1번째 인덱스부터 시작
        key = arr[i]        # 삽입할 원소 선택
        j = i - 1           # 현재 원소의 바로 왼쪽 원소 인덱스

        # 이미 정렬된 앞부분을 탐색하며 키보다 큰 값을 오른쪽으로 이동
        while j>=0 and arr[j] > key:
            arr[j+1] =  arr [j]
            j -= 1

        arr [j+1] = key     # 알맞은 위치에 키 삽입

arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
InsertionSort(arr)
print("삽입 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

 

출력결과

내림차순은 부등호만 바꾸면 된다.

# 내림차순
def  InsertionSort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1

        # 키보다 작은 값을 오른쪽으로 이동
        while j>=0 and arr[j] < key:
            arr[j+1] =  arr [j]
            j -= 1

        arr [j+1] = key

arr = [12, 52, 11, 7, 25, 30]
print("기존 배열:", (arr))
InsertionSort(arr)
print("삽입 정렬 후 배열:")
for i in range(len(arr)):
    print( arr[i], end = " ")

출력결과

---

기본 알고리즘의 장단점

	장점	단점	시간복잡도
선택 정렬	교환 횟수가 적다 (역순 정렬에 적합)	비교횟수가 많다	\(O\left ( n^{2}\right )\)
버블 정렬	구현이 쉽다 n개의 원소에 대해 n개의 메모리를 사용하기에 정밀 비교가 가능한다.	원소의 개수가 많아지면 비교 횟수가 많아져 성능이 저하된다.	\(O\left ( n^{2}\right )\)
삽입 정렬	최선의 경우 O(n)으로 빠른 효율성을 가지고 있다.  버블 정렬의 비교횟수를 줄이기 위해 고안됐다. 크기가 적은 집합을 정렬할 때 효율이 좋다.	데이터의 상태와 크기에 따라 성능 편차가 크다.	\(O\left ( n^{2}\right )\)