문자열 포맷팅 - f스트링
쉘정렬
간격을 나눠서 부분적으로 삽입 정렬,
간격을 홀수로 해 주고 정렬한다
def shell_sort(a) :
n = len(a)
gap = n // 2
while gap >= 1 :
if (gap % 2) == 0 : gap += 1
for i in range(gap, n) :
j=i
while j >= gap and a[ j] < a[ j-gap]: #삽입 위치를 찾음
a[ j], a[ j-gap] = a[ j-gap], a[ j] #항목 이동
j -= gap
# print(' Gap=', gap, a)
gap = gap//2
a = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original :", a)
shell_sort(a)
print("Shell :", a)시간복잡도 측정 코드
코드 2개를 실행시간과 종료 시간을 측정해서 비교함
import random
import time
#시간복잡도 테스트를 위한 코드, 함수 2개의 실행시간과 종료시간을 비교
count_array = [1000,10000,12000,15000]
for count in count_array:
#리스트 함축으로 count 갯수만큼 숫자를 뽑아냄
arr = [random.randint(10000,99999) for i in range(count)]
start = time.time()
#exec
end = time.time()
start = time.time()
#exec
end = time.time()
위의 뼈대코드를 이용해서 시간복잡도 비교
import random
import time
#시간복잡도 테스트를 위한 코드, 함수 2개의 실행시간과 종료시간을 비교
def insertion_sort(a):
for i in range(1, len(a)): # i는 1번부터 시작
key = a[i]
j = i - 1 # j를 루프 외부에서 선언해서 재사용
#값이 정렬되지 않았으면 한칸씩 뒤로 밀어준다
while (j >= 0 and a[j] > key):
a[j+1] = a[j]
j-=1
a[j+1] = key
def shell_sort(a) :
n = len(a)
gap = n // 2
while gap >= 1 :
if (gap % 2) == 0 : gap += 1
for i in range(gap, n) :
j=i
while j >= gap and a[ j] < a[ j-gap]: #삽입 위치를 찾음
a[ j], a[ j-gap] = a[ j-gap], a[ j] #항목 이동
j -= gap
# print(' Gap=', gap, a)
gap = gap//2
count_array = [1000,10000,12000,15000]
for count in count_array:
#리스트 함축으로 count 갯수만큼 숫자를 뽑아냄
arr = [random.randint(10000,99999) for i in range(count)]
insertion_arr = arr.copy();
shell_arr = arr.copy();
print(f'데이터 수 : {count}개')
start = time.time()
shell_sort(shell_arr)
end = time.time()
print(f'셀정렬 실행시간 = {end-start:10.3f}')
start = time.time()
insertion_sort(insertion_arr)
end = time.time()
print(f'삽입정렬 실행시간 = {end-start:10.3f}')실습
경기에 참가한 마라톤 선수 총인원 수, 참가번호, 기록(초 단위)을 입력 받은 후, 기록을
기준으로 오름차순으로 정렬한 후, 시, 분, 초 단위로 출력하는 프로그램을 작성하라.
(단, 동일 기록은 없다고 가정한다.)
입력
61
2
23
33
45
58
65
7798
7862
8171
7384
7820
7707
출력
45 2 3 4
65 2 8 27
12 2 9 58
def insertion_sort(score, arr):
for i in range(1, len(score)): # i는 1번부터 시작
key = score[i]
human = arr[i]
j = i - 1 # j를 루프 외부에서 선언해서 재사용
#값이 정렬되지 않았으면 한칸씩 뒤로 밀어준다
while (j >= 0 and score[j] > key):
score[j + 1] = score[j]
arr[j + 1] = arr[j]
j-=1
score[j + 1] = key
arr[j + 1] = human
n = int(input())
arr = []
score = []
for i in range(n): arr.append(int(input()))
for i in range(n): score.append(int(input()))
insertion_sort(score, arr)
for i in range(0,3):
tmp1 = score[i] // 3600
tmp2 = (score[i] - tmp1*3600) // 60
tmp3 = score[i] % 60
print(arr[i], tmp1, tmp2, tmp3)
