선택정렬 python selctionSort (배열, 링크드리스트로 구현)

선택정렬

 

Selection Sort, Algorithms - Code Pumpkin

선택정렬은 배열 중 최소값을 찾아 첫번째 인덱스의 값과 교환하고,

그다음은 배열의 첫번째 인덱스를 제외한 값들 중 최소값을 찾아 두번째 인덱스의 값과 교환하고..

이것을 반복하여 정렬하는 방법이다!

 

시간복잡도는 O(n^2)

 

 

배열로 선택정렬 구현

def sortSelectionInArray(array):

    min = None
    minIdx = None
    temp = None

    for i in range(len(array)):

        min = array[i]
        minIdx = i

        for j in range(len(array)-i):

            if min > array[j+i]:
                min = array[j+i]
                minIdx = j+i

        temp = array[i]
        array[i] = min
        array[minIdx] = temp

    return

 

선택정렬 역시 내부 반복문의 범위와 인덱스 계산만 잘 하면 간단하게 구현할 수 있다!

더 작은 값을 찾았을 때 minIdx도 같이 재할당 시켜주는거만 신경쓰면 됨!!

 

 

 

링크드리스트로 선택정렬 구현

 

↓ 이전글의 링크드리스트가 반드시 필요하다

2022.11.25 - [자료구조] - python 알고리즘용 LinkedList

 

def sortSelction(self):

    if self.head is None:
        return None
    elif self.head.next is None:
        return None

    idx = self.head
    curr = None
    tempValue = None
    min = None

    while idx is not None:

        curr = idx
        min = idx

        while curr is not None:

            if curr.data < min.data:
                min = curr

            curr = curr.next

        tempValue = idx.data
        idx.data = min.data
        min.data = tempValue

        idx = idx.next

    return

 

선택정렬은 단방향리스트로도 구현이 가능하다

범위나 인덱스 계산이 간단하고, 포인터 형태로 선언되는 노드변수의 특성상 오히려 배열보다도 쉬운편!