정렬과 선택 정렬 설명 및 문제 실습 (파이썬)

 

 

 

 

 

알고리즘을 공부할 때 대부분

가장 먼저 풀어보는 것이 바로

정렬(Sort)문제라고 하는데

 

 

그 이유로는 바로 알고리즘의

필요성과 효율성을 극명하게

확인할 수 있기 때문이라고 한다.

 

 

알고리즘 문제를 풀 때는 바로

소스코드부터 만지는 것이 아니라

간단한 수식을 활용해 먼저

손으로 풀어보며 테스트를 한 뒤

후에 소스코드로 옮기는 것이

효율적이라 한다.

 

 

 

 

---

 

 

 

선택 정렬

 

 

 

정렬의 종류 중에는

선택 정렬이있고

대표적인 기초 문제로는 :

 

 

다음 숫자들을 오름차 순으로

정렬시켜라 : 2 1 3 5 4

등이 있는데

 

 

문제를 해결하는 방식을 보면 모든

index의 값을 자신의 값과 비교하여

필요한 index에 위치시킬값을

선택하기 때문에

 

 

이와 같은 정렬 알고리즘을

선택 정렬 (Selection Sort)라 부른다.

 

 

* 참고로 index란,

[ 2, 1, 3, 5, 4 ]

식의리스트(list)가 있을 때

 

 

괄호 안 각각의 숫자의 위치를 뜻하며

세는 순서는 1부터가 아닌 0부터,

역순으로는 -1

 

 

현재 숫자 2의 위치는 (0),

숫자 4의 위치는 (4) 이자 (-1).

 

 

 

 

index 예시

 

 

 

 

 

성능 상의 한계 때문에

실전에서는 거의 보기 힘들지만

가장 구현이 쉬운 정렬 알고리즘이라

 

 

알고리즘 수업 시간에는 한 번씩

꼭 접하게 되는 유명한 정렬 알고리즘

이라고 한다.

 

 

 

 

---

 

 

 

 

선택 정렬의 특징

 

 

 

선택 정렬의 특징으로는

정렬된 값을 배열의 맨 앞부터

하나씩 채워나가는 데있고

 

 

뒤에 있는 index로 갈수록

비교 범위가 하나씩 줄어드는

특성이 있다. (당연한 이야기)

 

 

앞서 언급한 것처럼

퍼포먼스가N2로

좋지 않은데 그 이유로는

 

 

입력 배열이 이미 정렬되어 있건 말건

관계없이 동일한 연산량을 가지고 있어

최적화 여지가 적기 때문.

 

 

그러니 다른

O(N2)(order of nsquare)와

비교해 볼 때 성능이 떨어지는 편이라고

 

 

 

 

---

 

 

 

 

코드 구현하기

 

 

두 개의 반복문이 필요.

 

 

1. 내부 반복문에서는

현재 index부터 마지막 index까지

최솟값의 index를 찾아내고

 

 

2. 외부 반복문에서는

이 최솟값의 index와

현재 index에 있는 값을

서로 교환(swap) 한다.

 

 

 

 

 

2가지 방식으로

코드를 작성

 

 

1.

def selection_sort(arr):
    for i in range(len(arr) -1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min:idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]



###################################################################


2. 


import unittest


def selectionSort(input):
    for i in range(len(input) - 1):
        idx_min = i #assume the min is the first element
        j = i + 1

        #test against elements after i to find the smallest
        while j < leg(input):
            if(input[j] < input[idx_min]): # found new minimum, remember its index
                idx_min = j
            j = j + 1

        if idx_min is not i: #swap
            input[idx_min], input[i] = input[i], input[idx_min]

    return input



class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1,2,3,4,5]), selectionSort ([2, 1, 3, 5 ,4])
        self.assertEqual([1,2,3,4,5,6,7,8]), selectionSort([8,3,2,4,1,5,7,6])