[알고리즘] #1_2 선택 정렬

클릭시 출처 이동

 

** 선택 정렬(Selection sort)

     - 정의: 다음과 같은 일련의 과정을 반복하며 정렬하는 알고리즘

           1) 주어진 데이터 중, 최소값을 찾음

           2) 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함

           3) 맨 앞의 위치를 뺀 나머지 데이처를 동일한 방법으로 반복함

 

    - 참고:  https://visualgo.net/en/sorting

 

 

 

 

 

 

 

 

 

** 알고리즘 구현

---

def selection_sort(data_list):
    for i in range(len(data_list)):
        min_index = i
        
        for j in range(i + 1, len(data_list)):
            if data_list[j] < data_list[min_index]:
                min_index = j
                
        data_list[i], data_list[min_index] = data_list[min_index], data_list[i]
    
    return data_list

 

# 확인

import random

data_list = random.sample(range(100), 50)
selection_sort(data_list)

---

 

** 알고리즘 분석

• 이중 반복문: O(n^2)
• 실제 계산: n*(n-1)/2