ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [python]선택 정렬
    Programming/python 2019. 10. 15. 00:16

    선택 정렬(Selection sort)이란?


    리스트 중에서 가장 작은 걸 선택한 뒤에 가장 앞으로 보내면서 정렬하는 방법.

    1. 리스트 중에 최소값을 찾는다.
    2. 그 값을 맨 앞에 값과 교체한다.
    3. 맨 앞의 값을 제외하고 다시 검색해서 최소값을 찾는다.
    4. 맨 앞의 값 뒤에 값과 최소값을 교체한다.
    5. 차례로 반복

    직관적으로 애니메이션 이미지를 보면서 예를들어보자.

    옆에 [8,5,2,6,9,3,1,4,0,7]이라는 배열이 있다. 가장 처음에 앞에서부터 찾아가며 최소값 0을 찾아내고 이를 맨 앞에 있는 0과 교환한다. [0,5,2,6,9,3,1,4,8,7] 그 다음에 0을 제외하고 검색을 시작하고 최소값 1을 찾아낸 뒤에 5와 1을 교환한다. [0,1,2,6,9,3,5,4,8,7] 그 다음에 0,1을 제외하고 검색을 시작하고 최소값 2를 찾아낸다. 근데 2 이외에 최소값은 더이상 없으므로 2는 그냥 그 자리에 있게 된다. 이런 식으로 계속 내려가다가 결국 [0,1,2,3,4,5,6,7,8,9]로 리스트가 정렬된다.

    선택 정렬 알고리즘의 특징


    장점

    • 이해하기 쉽고 간단하다.

     

    단점

    • 입력 크기가 커지면 커질수록 정렬하는 데 시간이 굉장히 오래 걸림

    한마디로 단순하지만 비효율적이다.

    선택 정렬 시간복잡도


    하나씩 비교해야하므로 n개의 자연수의 합을 구하는 시그마 공식과 같다.

    (n-1)+(n-2)+...+2+0= n(n-1)/2

    따라서 빅오표기법으로 표현하면 최악의 경우를 가정하기 때문에 n제곱만 남아서 O(N²)

    코드


    # 선택 정렬
    # 리스트 a를 정렬하기
    
    def sel_sort(a):
        n = len(a) #배열 a의 갯수
        for i in range(n-1):
            min_idx = i #인덱스 초기값으로 첫번째 배열을 넣어둔다
            for j in range(i+1,n): #배열 두번째 값부터 배열의 갯수만큼
                if a[j] < a[min_idx]:
                    min_idx = j #찾은 값이 최솟값이면 그 찾은 값의 인덱스를 min_idx에 넣는다
            a[i],a[min_idx] = a[min_idx],a[i] #찾은 최솟값을 i위치와 교환한다
        return a #어차피 매게변수로 들어온 리스트 값 자체를 바꾸므로 리턴을 생략해도 출력되는 것은 같다
    a = [8,1,3,4,5,2,6,7]
    sel_sort(a)
    print(a)

    여기서 두 자료 값을 서로 바꾸는데 <code<a[i], a[min_idx] = a[min_idx],a[i] 가 쓰였다.

    다른 언어는 두 값을 바꾸기위해서 제 3의 임시 변수를 만들어 두 값을 교환했야 하는데.

    파이썬에서는 x,y = y, x 이렇게 간단하게 두 값을 교환하는 문법을 제공한다.

    참고로 만약 리스트를 오름차순 정렬이 아니라 내림차순으로 정렬하기 위해서는 이중for문의 안에 for문의 부등호를 반대로 if a[j] > a[min_idx] 이렇게 바꾸어주면 된다.

    'Programming > python' 카테고리의 다른 글

    [python]버블 정렬  (0) 2019.10.20
    [python]퀵 정렬  (0) 2019.10.18
    [python]합병 정렬  (0) 2019.10.18
    [python]삽입 정렬  (0) 2019.10.16
    [python]팩토리얼과 재귀함수  (0) 2019.10.11

    댓글

Copyright 2023. 은유 All rights reserved.