[알고리즘] 02. 선택 정렬

안녕하세요? 주니하랑 입니다.

오늘은 자료구조와 알고리즘의 알고리즘에서 Selection Sort에 대해 공부 해 보도록 하는 것이에요.

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

---

 

 

 

 

📌 Selection Sort (선택 정렬)란?

---

선택 정렬은 주어진 Data 중 최소값을 찾게 되는 것이에요.

그런 뒤 해당 최소값을 맨 앞에 위치한 값과 자리를 바꾸게 된답니다.

마지막으로 맨 앞의 위치를 뺀 나머지 Data를 동일한 방법으로 반복하는 것이에요.

이미 최소값으로 자리가 이동 된 것들은 다시 자리 이동을 할 필요가 없으니 정렬의 수는 n -1 만큼 줄어드는 것이에요.

 

참고 사이트 : https://visualgo.net/ko/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

 

 

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

 

 

📌 필기 자료

---

 

 

 

 

📌 알고리즘 구현

---

    📍 Python

for stand in range(len(data_list) - 1 # 로 반복
	lowest = stand					  # 로 선언 및 초기화
    
    for num in range(stand, len(data_list)	# stand 부터 데이터 길이 (배열의 길이) - 1까지 반복
    	내부 반복문 안에서 data_list[lowest] > data_list[num]	# 이면,
        	lowest = num	#	비교 대상 기준 Index에 비교 대상 Index를 넣어준다.
            
    data_list[num], data_list[lowest] data_list[lowest], data_list[num]	# 해당 위치의 값들을 위치 이동한다.

 

 

 

📌 빅오 표기법에 의한 시간 복잡도

---

반복문이 두개 이고, 그 안에서 data_list의 길이가 영향을 주기에 O($n^2$) 인 것이에요.

조금 더 깊게 상세하게 계산을 한다면 $\frac { n * (n - 1)}{ 2 }$ 이랍니다!

 

 

---

 

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글은 주니하랑에게 많은 힘이 됩니다