패스트 캠퍼스 챌린지 29일차 - 알고리즘 선택정렬

목차

1. 선택정렬
2. 선택정렬 구현 단계
3. 알고리즘 분석

1.선택정렬

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

출처:  https://en.wikipedia.org/wiki/Selection_sort

---

2.삽입정렬 구현단계

• 데이터가 두 개 일때
  • 예: dataList = [9, 1]
    • data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환
• 데이터가 세 개 일때
  • 예: data_list = [9, 1, 7]
    • 처음 한번 실행하면, 1, 9, 7 이 됨
    • 두 번째 실행하면, 1, 7, 9 가 됨
• 데이터가 네 개 일때
  • 예: data_list = [9, 3, 2, 1]
    • 처음 한번 실행하면, 1, 3, 2, 9 가 됨
    • 두 번째 실행하면, 1, 2, 3, 9 가 됨
    • 세 번째 실행하면, 변화 없음

---

3.알고리즘 분석

• 반복문이 두 개 O(n**2)
  • 최악의 경우, (n∗(n−1))/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

https://bit.ly/37BpXiC