[알고리즘] Array Deep Dive 배열 정렬하기
문제 설명
정수 배열을 정렬해서 반환하는 solution() 함수 완성하기
제한사항
- 정수 배열의 길이는 2이상 10^5 이하
- 정수 배열의 각 데이터값은 -100,000이상 100,000 이하
입출력 예
| 입력 | 출력 |
|---|---|
| [1,-5,2,4,3] | [-5,1,2,3,4] |
| [6,1,7] | [1,6,7] |
O(NlogN) sort() 이용 방법
function solution(arr) {
return arr.sort((a, b) => a - b);
}
// 코드 실행 시간은 1ms
// O(NlogN)
O(N^2) 정렬 알고리즘을 이용한 방법 (버블정렬) ⇒ 요소가 10개 미만인 경우는 효율적
//버블 정렬로 배열 정렬하기
function bubbleSortSolution(arr) {
const n = arr.length; // 배열의 길이를 변수 n에 저장
for (let i = 0; i < n; i++) {
// 배열의 모든 요소를 반복
for (let j = 0; j < n - i - 1; j++) {
// 배열의 인접한 요소를 비교
if (arr[j + 1] < arr[j]) {
// 오른쪽 요소가 왼쪽 요소보다 작으면
const temp = arr[j + 1]; // 두 요소를 교환
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
console.log(bubbleSortSolution([5, 7, 2, 9, 1, 3, 8, 4, 6])); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
// 코드 실행 시간은 2081ms
