선택 정렬

https://www.fun-coding.org/Chapter12-selectionsorting.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 선택 정렬 (selection sort) - 잔재미코딩

선택정렬이란 원소를 넣을 위치는 정해져 있고, 그곳에 어떤원소를 넣을지 정하는 알고리즘이다.

제자리 정렬 : 입력 배열 이외에 추가적인 메모리를 요구하지 않는 정렬 방법

 

 

데이터가 무작위로 있을 때, 이중 가장 작은 데이터를 선택해서 맨앞 데이터와 바꾸고,

그다음으로 작은 데이터를 선택해서 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.

 

방식:

1.현재 데이터중에서 최소값을 찾는다. (0~마지막인덱스-1까지)

처음 최소값은 현재 데이터중 가장 처음값으로 초기화한다.

2.구한 최소값과 현재 데이터의 맨 처음값을 교환한다.

3.교환된 맨 앞 값을 제외한 데이터에서 1번으로 다시 돌아간다.

 

장점:

1) 버블 정렬처럼 비교적 알고리즘이 단순함. 교환이 많이 일어날 때 좋음

2)제자리 정렬이라 메모리를 추가적으로 사용하지 않는다.

 

단점:

1)불안정정렬 = 중복된 값을 입력 순서와 상관없이 무작위로 뒤섞인 상태에서 정렬이

이루어짐. (선택, 퀵,힙 정렬)

2)O(n^2)이라 비효율적임. 

 

파이썬의 경우 n이 10000을 넘어가면 선택정렬은 급격하게 느려진다.

 

def 함수:

*외부 for문: 0~ 데이터길이-1까지 진행. (데이터의 범위를 맨앞에서부터 한칸씩 줄여준다.)

    초기 최솟값=현재 데이터의 범위의 맨처음값

    *내부 for문 : 현재 데이터의 처음~ 끝까지 :

               현재 최솟값과 현재 인덱스의 값을 비교해서 최솟값 갱신

    맨앞값과 현재데이터의 최솟값 스왑. 

 

def selection_sort(data_list):
    for stand in range(len(data_list)-1):
        lowest=stand
        for num in range(stand,len(data_list)):
            if data_list[lowest]>data_list[num]:
                lowest=num
        data_list[stand],data_list[lowest]=data_list[lowest],data_list[stand]
    return data_list