자료구조 알고리즘

선택정렬

판교데싸 2021. 3. 3. 13:24

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

 

어떻게 코드로 만들까?

* 데이터가 두 개 일때
  - 예: 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 가 됨
    - 세 번째 실행하면, 변화 없음

 

 

* 정렬을 하려면 무조건 데이터의 길이 -1 만큼을 비교해야 정렬이 됨

최솟값을 일단 기준점으로 놓고 기준점에 1더한 값부터 시작해서 끝까지 시작해서 가장 낮은 최솟값을 가진 인덱스를 뽑아내고 lowest와 바꾼다

 

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest] #swqp 하는 법
    return data

def selection_sort(data):     
  for stand in range(len(data) - 1):        
  	lowest = stand         
  	for index in range(stand + 1, len(data)):           
  		if data[lowest] > data[index]:                
  			lowest = index       
  		data[lowest], data[stand] = data[stand], data[lowest] #swqp 하는 법   
  	return data

간단한 구현 코드는 이렇다 - > 직접 해보기

반응형

'자료구조 알고리즘' 카테고리의 다른 글

순차탐색  (0) 2021.03.04
버블 정렬  (0) 2021.03.03
힙-HEAP  (0) 2020.05.06
이진 트리-binary Tree  (0) 2020.04.28
Hash Table- 해쉬 테이블  (0) 2020.04.10
반응형