Skip to main content Link Menu Expand (external link) Document Search Copy Copied

배열의 원소의 총합 계산하기

n = [13,6,9,8,12]

def min(array, com):
    #array의 비교할 것이 남아있지 않다면,
    if not array: 
        #com을 넘기면서 프로그램을 종료한다.                              
        return com                              
    #배열의 첫번째를 now로 선언.
    now = array[0]                              
    #now가 com보다 작다면,
    if now < com:                               
        #배열의 첫번째수가 비교하는 수보다 작으면, now를 com로 대체한다.
        return min(array[1:], now)              
    #now가 com보다 작지 않다면,
    else:                                       
        #배열의 첫번째가 비교하는 수보다 작지 않다면, com을 유지한다.
        return min(array[1:], com)              

def selection_sort(array, count=0):
    #array의 길이 만큼, count가 진행되었다면,
    if count == len(array):                     
        #array를 리턴.
        return array                            

    #min함수를 사용하여서 배열의 가장 최솟값을 찾아 mini에 저장
    mini = min(array[count:], array[count])     
    #최솟값 mini의 index번호를 찾는다.
    index = array.index(mini)                  
    array[index] = array[count]                 
    #단계(count)의 맞게 찾은 최솟값을 대상의 array와 위치를 바꾼다.
    array[count] = mini                         
    #다음 최소값을 찾기 위해서, count를 1증가 시켜 다음 단계를 진행.
    count += 1                                  
    return selection_sort(array, count)         

print(selection_sort(n))

‘데이터의 개수가 n개라고 했을 때, 첫 번째 회전에서의 비교횟수 :1~(n-1)=>n-1 두 번째 회전에서의 비교횟수 :2~(n-1)=>n-2 … (n-1) + (n-2) + …. + 2 + 1 => n(n-1)/2 이므로 선택 정렬의 시간복잡도는 $O(n^2)$이다.