def insert_sort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j] # 비교 값을 오른쪽으로 이동
j = j - 1 # 앞쪽 값을 비교하기 위해 -1
x[j+1] = key
return x
삽입 정렬은 현재 값을 기준으로 앞쪽의 값들과 비교해 자기 자리에 삽입하는 정렬 알고리즘이다.
삽입 정렬의 구체적인 알고리즘은 다음과 같다.
- 삽입 정렬은 두 번째 자료부터 알고리즘을 수행한다.
- 두 번째 자료(인덱스)부터 시작해 그 앞쪽의 값들과 비교해 삽입될 자리를 찾는다.
- 자리를 찾은 후 현재 값을 넣은 다음 나머지 값들은 한 칸씩 이동시킨다.(오른쪽)
- 세 번째 자료가 현재 값이 되고, 앞쪽 값인 첫 번째, 두 번째 값과 비교해 자리를 찾는다.
- 자리를 찾아 삽입되고 다른 값들은 옆으로 이동시킨다.
- 네 번째 값도 마찬가지로 왼쪽의 값들(1,2,3번째 값)과 비교해 삽입될 자리를 찾는다.
- 나머지 값들도 같은 방식으로 알고리즘이 수행된다.
위의 코드에서 보면 key가 선택된 값이 되고 j 인덱스가 왼쪽의 비교하는 값들이 된다.
j 번째 비교 값과 key 값을 비교했을 때 key가 작다면 j 번 값을 +1(즉 오른쪽으로 하나씩 이동) 시킨다. 계속 앞쪽의 값들과 비교해 비교 값들을 한 칸씩 오른쪽으로 이동시킨다.
만약 key 값이 더 크거나, 젤 앞의 값까지 비교가 끝나면 그 자리에 현재 값(key)을 넣어준다.
삽입 정렬의 시간 복잡도
- 두 번째 값으로 시작 시 첫 번째 값과 비교 -- 1번
- 세 번째 값은 첫 번째, 두 번째랑 비교 -- 2번
- n-1 번째 값은 1, 2, 3,... , n-2 번째 비교 -- (n-2)번
- n 번째 값은 -- (n-1)번
즉, 1 + 2 + 3 + ... + n-2 + n-1 = n(n-1) /2 가 돼서, 시간 복잡도가 최악의 경우 O(n^2)가 된다. 최선의 경우는 자료가 다 정렬된 경우이고 이때는 시간 복잡도가 O(n)이 된다. 왜냐하면 각 자리의 값마다 왼쪽의 값 하나만 비교하면 되기 때문이다. 따라서 삽입 정렬은 n값이 커질수록 복잡도가 커져 알고리즘 성능이 떨어진다.
case = int(input())
for _ in range(case):
# n : 자료 개수 , m : 찾고자 하는 자료 위치
n, m = map(int, input().split())
imp = list(map(int, input().split()))
temp = [0 for _ in range(n)] #리스트 표현식으로 0인 리스트 생성
temp[m] = 1 # 찾고자 하는 m번째를 1로 표시
cnt = 0
while imp:
if imp[0] == max(imp):
cnt += 1
if temp[0] == 1:
print(cnt)
break
else:
imp.pop(0)
temp.pop(0)
else:
imp.append(imp[0])
temp.append(temp[0])
del(imp[0])
del(temp[0])
- 중요도를 표시하는 imp 입력을 리스트로 만든다.
- imp 리스트와 비교하기 위한 temp 리스트를 만든다.
- imp[0]이 젤 큰 값인지 판단해, 아니라면 imp, temp 첫 요소를 뒤로 보내고 한 칸씩 땡긴다.
- imp[0]이 최댓값이면서 찾고자 하는 값이면 cnt 값을 출력하고 종료한다. 만약 찾고자 하는 값이 아니면 지우고 한 칸씩 땡긴다.
Numbers라는 재밌는 API를 이용해서 숫자에 맞는 재밌는 사실을 알려주는 웹앱을 만들어 봤다. 입력란에 아무 숫자나 넣으면 그 숫자에 맞는 사실(Fact) 한 가지를 보여주는 기능이다. 만약 숫자가 너무 크거나, 숫자에 맞는 리턴 값이 없다면 'boring number'라는 기본값을 보여준다.
id가 fact인 숫자를 입력했을 때 값을 표현하는 영역이다. 우선 처음에는 이 영역을 display: none으로 설정해 보이지 않도록 했다. 그리고 나중에 값을 입력받았을 때, 자바스크립트를 이용해 영역이 다시 보이도록 만들었다.
다음으로 JavaScript 코드다. 여기서 두 가지 방식 즉, AJAX 와 Fetch를 이용했다. 기능적인 부분은 동일하지만 Fetch를 이용한 방법이 훨씬 간단하게 코드를 짤 수 있다. 둘 다 같은 기능을 구현한 거니 선택해서 사용하면 된다.
1) AJAX - XHR 방식
let fact = document.querySelector('#fact');
let factText = document.querySelector('#factText');
let numberInput = document.querySelector('#numberInput')
numberInput.addEventListener('input', getFactAjax);
function getFactAjax() {
let number = numberInput.value; // input 입력 값
let xhr = new XMLHttpRequest(); // XHR 생성자 생성
xhr.open("GET", "http://numbersapi.com/" + number); // GET방식, API 요청
xhr.onload = function () {// 요청이 성공적으로 완료되면
if (this.status == 200 && number != "") { // 요청상태 확인 및 입력한 값이 있다면
fact.style.display = 'block';
factText.innerText = xhr.responseText;
}
};
xhr.send();
}
number라는 변수는 input태그에서 입력한 값을 담고 있다. 이제 URL에 number를 붙여 GET방식으로 API 서버에 요청한다. 만약 성공적으로 응답을 받으면 div#fact 영역을 block으로 바꿔 보이도록 한다. 그리고 텍스트란에 받아온 응답 값을 표현해주면 성공적으로 앱이 완성된다.
2) Fetch 방식
let fact = document.querySelector('#fact');
let factText = document.querySelector('#factText');
let numberInput = document.querySelector('#numberInput')
numberInput.addEventListener('input', getFactAjax);
function getFactFetch() {
let number = numberInput.value;
fetch("http://numbersapi.com/" + number)
.then((response) => response.text())
.then((data) => {
console.log(data);
if (number != "") {
fact.style.display = "block";
factText.innerText = data;
}
})
.catch((err) => console.log(err));
}
fetch 함수에 요청할 URL을 넣어준다. 성공적으로 응답을 받으면 response.text()를 이용해 promise 값을 리턴하도록 한다. 그 값이 data 인자로 들어가고, 입력값(number)이 있는지 확인 후, 응답 값을 보여주도록 한다. catch를 사용해 에러 처리를 했다.
여기서 사용한 Numbers API는 서버 요청, 응답을 공부하기에 가장 간단한 예제라고 생각한다. 2가지 방식으로 모두 공부해보면서 조금이나마 서버 요청과 응답을 이해할 수 있었다. 다음에 다른 자바스크립트 예제를 포스팅할 예정이다.
