반응형
실버 2 찍었다.
근데 풀다보니까 더 이상 무지성 때려박기로는 안된다는 생각이 들어서 알고리즘을 공부하기로 했다.
1. 선택정렬
현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
인덱스 값을 증가 시키며 인덱스 이후의 최소값과 값을 바꿔주는 방식이며, 반복문을 두번 사용하기 때문에 시간복잡도는 N(O^2)이다.
파이썬 코드(오름차순)
| arr=[2,5,3,1,8,7,6,9,4] for j in range(0,len(arr)): low=arr[j] for i in range(j,len(arr)): if low>=arr[i]: low=arr[i] index=i arr[index],arr[j]=arr[j],low print(arr) |
자바스크립트 코드(오름차순)
| <html> <head> </head> <body> <script> arr=[2,5,3,1,8,7,6,9,4] var index=0; for (var j=0; j<arr.length; j++){ var low=arr[j]; for (var i=j; i<arr.length; i++){ if(low>=arr[i]){ low=arr[i]; index=i; } } arr[index]=arr[j]; arr[j]=low; } document.write(arr) </script> </body> </html> |
2. 삽입 정렬
현재위치에서 이하의 배열을 비교, 자신이 들어갈 위치에 들어가는식으로 정렬되는 알고리즘
두번째 이하부터 시작하여 끝까지, 현재 위치 이하까지 비교하여 현재 인덱스값과 교체
시간복잡도는 역정렬 시에 O(n^2), 정렬된 채로 배열이 주어질시에 O(n)이다.
파이썬 코드(오름차순)
| arr=[2,5,3,1,8,7,6,9,4] for i in range(2, len(arr)): for j in range(i,0,-1): if arr[j-1]>arr[j]: arr[j-1],arr[j]=arr[j],arr[j-1] print(arr) |
자바스크립트 (오름차순)
| <html> <head> </head> <body> <script> arr=[2,5,3,1,8,7,6,9,4] for (var i=0; i<arr.length; j++){ for (var i=j; i>0; i++){ if(arr[i-1]>arr[i]){ var tmp=arr[i-1]; arr[i-1]=arr[i]; arr[i]=tmp; } } document.write(arr) </script> </body> </html> |
3. 버블정렬
두개의 인덱스를 증가시키며 값을 비교하여 교환, 정렬하는 알고리즘
시간 복잡도는 어떻게 정렬되있던간에 O(N^2)
파이썬 코드(오름차순)
| arr=[2,5,3,1,8,7,6,9,4] for i in range(0,len(arr)): for j in range(0,len(arr)-1): if(arr[j]>arr[j+1]): arr[j],arr[j+1]=arr[j+1],arr[j] print(arr) |
자바스크립트(오름차순)
| <html> <head> </head> <body> <script> arr=[2,5,3,1,8,7,6,9,4] ; var tmp=0; for (var i=0; i<arr.length; i++){ for (var j=0; j<arr.length; j++){ if(arr[j]>arr[j+1]){ tmp=arr[j+1]; arr[j+1]=arr[j]; arr[j]=tmp; } } } document.write(arr); |
반응형
