Python에서 간단한 비교 sort와 binary search

import random #1. sort MAX = 10 a = [] for x in range(MAX): a.append(random.randrange(1,100)) print a for x in range(MAX-1): for y in range(x+1,MAX): if a[x] > a[y]: a[x], a[y] = a[y], a[x] print a #2. binary search MAX = 1000 a = [] # 천개의 원소가 들어가는 리스트를 만든다. for x in range(1,MAX+1): a.append(random.randrange(1,1000)) # 그것들을 정렬하고... a.sort() # 찾을 원소를 적고... compared = int(raw_input("1~1000 : ")) s_min = 0 #시작 s_max = MAX-1 #끝 cnt = 1 #몇번 만에 맞추는지 알아보려고... while 1: s_div = (s_min+s_max)/2 print cnt,"th serarching...",s_min,"~",s_max cnt += 1 if s_div == s_min: print "찾을게 없구만..." break if compared == a[s_div]: print s_div,"에 위치하고 있음" print "a[%d] = %d"%(s_div,a[s_div]) break elif compared > a[s_div]: s_min = s_div elif compared < a[s_div]: s_max = s_div

sort야 기본적인 비교 정렬 방식이어서, 대충 해본 것이고...

두번째 예제를 보면 sort()를 이용해서 바로 리스트들의 원소들을 sorting할 수 있다.

1000개의 랜덤 원소들을 담는 리스트에서 내가 원하는 값을 찾고, 그 위치까지 알아내는 검색인데, 이진 검색 기술을 사용하면 굉장히 빠른 속도로 찾을 수 있다는 것을 알 수 있다. 물론 자료들은 정렬이 되어 있어야 한다!!

일일히 비교해서 다 찾는 다는 것은 정말 시간 낭비인 것은 누구나 다 아는 센스~