선택 정렬

https://unsplash.com/photos/zdV9ngtM0Sw

선택 정렬에 대해 알아보자

 

 

 

 

 

---

얻어갈 지식

• 선택 정렬

 

 

 

 

 

선택 정렬

 

정렬되지 않은 어레이에서 최소 수를 찾아 선두에 배치하여 정렬하는 방법이다.

버블 정렬이 인덱스 맨 뒤에서부터 정렬을 하는 것이라면 선택 정렬은 앞에서부터 정렬하는 방법이다.

 

선택 정렬 흐름도

선택 정렬 예시

• [ 64, 25, 12, 22, 11 ]을 오름차순으로 정렬할 때
  
  
• 첫 번째 패스
  • min_idx 변수에 0을 넣는다.
  • arr[min_idx]와 arr[1]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[2]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[3]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[4]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • 0 번째와 min_idx 번째 값을 서로 스왑한다.
  • [ 11, 25, 12, 22, 64 ]
    
    
• 두 번째 패스
  • min_idx 변수에 1을 넣는다.
  • arr[min_idx]와 arr[2]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[3]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[4]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • 1 번째와 min_idx 번째 값을 서로 스왑한다.
  • [ 11, 12, 25, 22, 64 ]
    
    
• 세 번째 패스
  • min_idx 변수에 2를 넣는다.
  • arr[min_idx]와 arr[3]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • arr[min_idx]와 arr[4]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • 2 번째와 min_idx 번째 값을 서로 스왑한다.
  • [ 11, 12, 22, 25, 64 ]
    
    
• 네 번째 패스
  • min_idx 변수에 3을 넣는다.
  • arr[min_idx]와 arr[4]를 비교하고 더 작은 수를 갖고있는 인덱스를 min_idx에 넣는다.
  • 3 번째와 min_idx 번째 값을 서로 스왑한다.
  • [ 11, 12, 22, 25, 64 ]

 

 

코드로 작성

for i in range(len(arr)):
	min_idx = i

	for j in range(i+1, len(arr)):
		if arr[min_idx] > arr[j]:
			min_idx = j
	arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

 

시간 복잡도와 보조 공간

 

• 버블 정렬과 마찬가지로 공간 복잡도는 O(N^2)이다.
• 주어진 배열 안에서 스왑을 통해 정렬이 수행되므로 O(N)이다.

 

 

 

 

 

---

https://www.geeksforgeeks.org/selection-sort/

Selection Sort - GeeksforGeeks