간단하게 구현해본 삽입정렬
목표는 ["텍스트",숫자],["텍스트",숫자],..... 이렇게 구성되어있는 리스트에서
-
숫자에 대한 오름차순으로 정렬
-
숫자에 대한 내림차순으로 정렬
-
숫자에 대해 정렬한 뒤 숫자가 같다면 글자순서대로 정렬
간단히 말해서 MySQL의 ORDER BY ... ASC,DESC 구현을 삽입정렬로 해보자
우선, Test data는 간단하게 5개의 영화데이터로 실행한다.
이 다섯개의 영화데이터는 ["제목",개봉연도]로 구성 되어있다.
list_m = [["명량",2014],["극한직업",2019],
["신과함께:죄와벌",2017],["국제시장",2014],["베테랑",2015]]비교를 위해 간단하게 함수 두개를 선언해준다.
def is_asc(a,b):
if a > b :
return -1
if a < b :
return 1
return 0
def is_desc(a,b):
if a < b :
return -1
if a > b :
return 1
return 0
이건 어디에 쓰는 함수이냐면 메인 함수의 while안에 조건문으로 들어가게 되며
비교문에서 어떤때는 오름차순 어떤떄는 내림차순을 이용하기 때문에 미리 선언한다.
간단히 말해서 is_asc(오름차순인가?)함수가 1이라면 오름차순인 것이고 -1이라면 오름차순이 아닌 상태, 0이면 두개가 같은 상태이다.
다음으로는 이 data구조에 대한 비교 함수를 구현해주는데
def asc_cmp(a,b):
if is_asc(a[1],b[1]) != 0:
return is_asc(a[1],b[1])
else:
return is_asc(a[0],b[0])
def desc_cmp(a,b):
if is_desc(a[1],b[1]) != 0:
return is_desc(a[1],b[1])
else :
return is_desc(a[0],b[0])이 is_asc를 사용해서 비교기를 만든다. a와 b를 받은 뒤
개봉연도끼리 비교해서 같지 않으면 숫자에대한 오름차순 내림차순
만약 같으면(is_asc가 0이면) 영화 제목의 글자순으로 정렬하는 함수들이다.
만약, 다른 조건을 원하면 이렇게 검색해준다.
def is_muti_cmp(a,b):
if is_desc(a[1],b[1]) != 0:
return is_desc(a[1],b[1])
else :
return is_asc(a[0],b[0])숫자에 개봉연도에 대한 내림차순(최신순), 영화제목에 대한 오름차순(글자순)
여기에 메인코드는
for i in range(1,len(list_m)):
j = i-1
while j>=0 and is_multicmp(list_m[j],list_m[i]) < 0:
j -= 1
list_m.insert(j+1,list_m.pop(i)) 이렇게 짧게 나오는데 만약 기준 조건을 바꾸고 싶다면 is_multicmp부분을 수정하면 간단하게 수정할 수 있는 구조이다.
삽입정렬을 배우면서 기억해둬야 할 점은
- 함수를 이용해 정렬기준을 정의하자 (코드의 깔끔함)
- insert()와 pop()을 사용 >> 사용하지 않으려면 어떻게 해야할까?
- i는 1부터 시작해서 j(=i-1)과 비교해주며 만약 오른쪽값(i)가 왼쪽(j)보다 작다면(정렬기준과 다르다면) j -=1로 줄여주고 다시 비교하는데 j가 0보다 작아질 경우 종료를 해준 뒤 맨처음에 넣어줘야한다. (list_m[-1]은 맨마지막 값.)
while문을 이용해 j==-1일때 종료하고 while 뒤의 insert(j+1)으로
맨처음 인 0번째에 넣어주며 반복을 종료한다.
요약 : 정렬기준 함수이용, insert()/pop(), j(=i-1)의 이용
