[알고리즘] 선택 정렬

1. 선택 정렬 (selection sort) 란?

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최소값을 찾음
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

이 사이트에서 시뮬레이션을 확인하자!

2. 어떻게 코드로 만들까?

데이터가 네 개 일때
예: dataList = [2, 6, 3, 1]

• 첫 번째 턴
  - 기준점의 인덱스(=p)는 0이며 , 1, 6, 3, 2 가 됨
• 두 번째 턴
  - 기준점의 인덱스(=p)은 1이며, 1, 2, 3, 6 가 됨
• 세 번째 턴
  - 기준점의 인덱스(=p)은 2이며, 변화 없음

3. 알고리즘 구현

# 선택정렬
def selectionSort(dataList):
    for p in range(len(dataList)-1): # p는 기준점(point)
        minIdx = p # minIdx는 최솟값의 인덱스
        for i in range(p+1, len(dataList)):
            if dataList[minIdx] > dataList[i]:
                minIdx = i
        dataList[minIdx], dataList[p] = dataList[p], dataList[minIdx] # 기준점과 (순회하며 찾은) 최솟값을 swap한다
    return dataList

코드 이미지

테스트

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기