선택 정렬
가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘이다.
제일 작은 원소를 찾아서 탐색 기준점으로부터 가장 앞 원소와 바꾸고 이를 끝까지 반복한다.
시간복잡도는 O(N^2)이다.
데이터 커질수록 엄청 커지므로 최대한 피해야할 시간복잡도다.
아래는 예시 문제 및 풀이방법이다.
[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 1. 선택정렬
문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력 풀이 function solution(arr) { let answer = arr; let min, tmp, index; for (let i = 0; i < answer.length; i++) { min = Number.MAX_SAFE_INTEGER; for (let j = i; j < answer.length;
sanghee01.tistory.com
버블 정렬
이웃한 두 숫자끼리 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복하는 알고리즘이다.
한번 돌면 가장 큰 값이 맨 뒤로 간다.
시간복잡도는 O(N^2)이다.
선택정렬은 하나 선택해서 그것만 바꾸는데에 비해 버블 정렬은 계속해서 자리를 바꾸는 연산을 하므로 훨씬 오래걸린다.
효율성이 가장 떨어지는 정렬 알고리즘이다.
아래는 예시 문제 및 풀이방법이다.
[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 2. 버블정렬
문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력. 단, 버블정렬로 해야한다. 풀이 function solution(arr) { let answer = arr; for (let i = 0; i < answer.length - 1; i++) { for (let j = 0; j < answer.length - 1 - i; j++)
sanghee01.tistory.com
삽입 정렬
이전 정렬들은 무조건 위치를 바꿨지만 삽입 정렬은 ‘필요할 때’만 위치를 바꾼다.
선택정렬은 각 숫자를 자기보다 앞에 있는 수들 중 적절한 위치에 삽입하는 알고리즘이다.
항상 왼쪽이 자기보다 크다는, ‘정렬이 되어있다는 가정’ 하에 있다.
계속해서 앞이 정렬되어있으니 계속 적절한 위치에 쏙 들어가기만 하면 된다.
선택한 숫자의 바로 앞과 비교해서 더 작으면 위치를 바꿔주는 것이다.
시간복잡도는 O(N^2)지만, 선택, 버블정렬보단 휠씬 효율적이다.
데이터가 이미 거의 정렬된 상태에 한해서는 그 어떤 알고리즘보다도 빠르다는 특징을 갖고 있다.
아래는 예시 문제 및 풀이방법이다.
[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 4. 삽입정렬
문제 N개이 숫자가 입력되면 오름차순으로 삽입정렬로 정렬 풀이 function solution(arr) { let answer = arr; for (let i = 0; i < answer.length; i++) { j = i; while (answer[j] < answer[j - 1]) { [answer[j], answer[j - 1]] = [answer[j -
sanghee01.tistory.com
'CS > Data structure & Algorithom' 카테고리의 다른 글
| 단순 연결 리스트(Singly Linked List) (0) | 2023.06.18 |
|---|---|
| 이분 검색 (0) | 2023.02.19 |
| 스택(Stack), 큐(QUEUE) (0) | 2023.02.08 |
| 슬라이딩 윈도우(Sliding Window) 알고리즘 (0) | 2023.02.03 |
| 투 포인터(Two Pointers) 알고리즘 (0) | 2023.01.31 |