Python 자료구조 [파이썬으로 구현한 알고리즘] (3) 선택 정렬(Selection Sort)

2018.02.27 17:45

졸리운_곰 조회 수:549

[파이썬으로 구현한 알고리즘] (3) 선택 정렬(Selection Sort)

        
 
 선택 정렬은 정렬 알고리즘 중에 가장 간단한 알고리즘 이다. 선택 정렬은 최소값을 가장 앞쪽으로 가져오는 작업을 반복하는 형식으로 정렬한다.

 
사용자 삽입 이미지
 
사용자 삽입 이미지

사용자 삽입 이미지

사용자 삽입 이미지

< 그림 1. 선택 정렬 과정 >
 
 파이썬의 리스트형에는 내장 정렬 함수 sort()를 제공 한다. 다음과 같이 간단하게 리스트를 정렬 할 수 있다.
 
#!/usr/bin/python
list = []
for i in range(10):
   list.append( random.randint(1,10) )

print "< Before Sort >"
print list
list.sort()
print "< After Sort >"
print list
< 예제 1. 리스트형의 정렬 >

 하지만 지금은 자료를 정렬을 하는게 목적이 아니라, 정렬 알고리즘을 이해하는게 목적이므로 정렬 함수를 따로 구현 하도록 하겠다.
 
#!/usr/bin/python
import random

def selected_sort(random_list):
  for sel in range( len(random_list)-1 ):
    min = random_list[sel]
    minindex = sel
    # find min value
    for step in range( sel+1, len(random_list) ):
      if min > random_list[step]:
        min = random_list[step]
        minindex = step  
    # swap            
    random_list[minindex] = random_list[sel]
    random_list[sel] = min

def Main():     
  list = []     
  for i in range(10):
    list.append( random.randint(1,10) )
  print "< Before Sort >"
  print list

  selected_sort(list) # now sorting!
  print "< After Sort >"
  print list

Main()
< 예제 2. 선택 정렬 알고리즘 구현 >

 선택 정렬은 루프 내에 또 다른 루프가 있으므로 big O 표기법으로 O(N^2)의 성능을 가진다.
 
[출처] http://onestep.tistory.com/43

 

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

 

본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
이 게시물을
목록
목록
쓰기
태그
대표 김성준 주소 : 경기 용인 분당수지 U타워 등록번호 : 142-07-27414
통신판매업 신고 : 제2012-용인수지-0185호 출판업 신고 : 수지구청 제 123호 개인정보보호최고책임자 : 김성준 sjkim70@stechstar.com
대표전화 : 010-4589-2193 [fax] 02-6280-1294 COPYRIGHT(C) stechstar.com ALL RIGHTS RESERVED