단순 선택 정렬

개념

정렬되지 않은 부분에서 가장 작은 원소를 선택해 알맞은 위치로 이동시키는 정렬 방법.

알고리즘 (파이썬)

a = [6, 3, 2, 1, 4, 8, 9]

n = len(a)  #배열 길이

for i in range(n-1):
    min = i #가장 작은 원소값을 가진 인덱스를 저장하는 부분. 처음에는 정렬되지 않은 부분의 가장 앞 인덱스를 저장한다
    for j in range(i+1, n): #정렬되지 않은 부분의 두번째부터 배열 끝까지 
        if a[j] < a[min]:   #어떤 원소값이 가장 처음 인덱스의 원소값보다 작으면
            min = j #가장 작은 값 인덱스를 수정함
    a[i], a[min] = a[min], a[j] #가장 작은 값 검색을 끝냈으면 위치 교환한다

프로그램 추적 일부분

시간복잡도

선택정렬의 시간복잡도는 O(n^2)이다.

불안정한 정렬

원소의 위치가 서로 뒤바뀔 가능성이 있어, 불안정한 졍렬에 속한다.

• 동일한 값들이 정렬 후 입력 시의 순서와 같지 않은 경우 불안정한 정렬이다.