버블 정렬
출처: 이해가 어려워서 이미지 자료도 빌리겠습니다 ㅜㅜ
첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …
이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식.
작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경!
버블 정렬의 시간 복잡도는 O(N^2)
[버블정렬 함수_오름차순 버전]
function bubbleSort(array) {
let n = array.length; // array의 길이를 n에 저장해요! 루프 카운트 변수로 쓰겠죠?
for (let i = 0; i < n; i++) {
// 이건 array를 순차적으로 돌겠다는 뜻이구요!
// 이건 버블정렬 알고리즘의 특성처럼 1개씩 줄어들면서 반복하며 비교를 해요.
for (let j = 0; j < n - i - 1; j++) {
// n-1 -> n-1-1 -> n-2-1
if (array[j] > array[j + 1]) {
// 앞의 원소가 뒤의 원소보다 크면 바꿔야겠죠?
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
console.log('정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ', bubbleSort([4, 6, 2, 9, 1]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', bubbleSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', bubbleSort([100, 56, -3, 32, 44]));
선택 정렬
이미지도 퍼옴
선택 정렬은 index 하나마다 위치할 원소를 결정하고 그 다음 index로 넘어가는 기법이에요!
다음과 같이 사람들이 일렬로 쭉~ 서 있는데, 한번 쓱 둘러보면서 가장 키 작은 사람을 찾는겁니다.
그리고 전부 다 봤다면, 그 중 가장 키 작은 사람! 맨 앞으로 와! 한 다음에 또 둘러보면서 두 번째로 키 작은 사람을 두 번째에 배치 시킵니다.
선택 정렬도 시간 복잡도는 O(N^2)
[선택정렬 함수_오름차순 버전]
function selectionSort(array) {
let n = array.length; // 루프 카운트!
// 이번에는 i ~ n - 2까지 돌면서 실험군을 선택해요!
for (let i = 0; i < n - 1; i++) {
let minIndex = i; // i번째에 들어갈 최소값을 찾아요!
for (let j = i + 1; j < n; j++) {
// 현재 최소값으로 설정된 친구보다 더 작은 친구를 발견하면!
if (array[j] < array[minIndex]) {
minIndex = j; // 최소값 인덱스를 갱신합니다!
}
}
// i번째에 최소값 인덱스에 있는 값을 넣어줍니다!
let temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
return array;
}
console.log('정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ', selectionSort([4, 6, 2, 9, 1]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', selectionSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', selectionSort([100, 56, -3, 32, 44]));
삽입 정렬
이미지도 퍼옴
선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,
삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!
이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데,
다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서
아 여기가 내 자리구나! 하면서 삽입하며 정렬하는 방식
삽입 정렬의 시간 복잡도는 O(N^2)지만 최선의 경우엔 Ω(N)만큼의 시간 복잡도가 걸립니다.
대상 배열이 거의 정렬되었다고 가정하면 더 비교를 하지않고 바로 다음 스텝으로 넘어가기 때문
[삽입정렬 함수_오름차순 버전]
function insertionSort(array) {
let n = array.length; // 루프 카운트!
// 삽입 정렬의 0번째 인덱스는 정렬된 상태라고 판단하므로 인덱스가 1부터 시작해요!
for (let i = 1; i < n; i++) {
// 최초 i = 1 -> i = 2
// 현재 index 범위 내에서 비교를 시작하죠! 비교 방향은 끝에서부터 시작해요!
for (let j = i; j > 0; j--) {
// 최초 j = 1 -> j = 2 -> j = 1
// 뒤의 값보다 앞의 값이 크면 바꿔줘요!
if (array[j - 1] > array[j]) {
// array[1-1] > array[1]
let temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
} else {
// 그렇지 않다면 정렬된 상태이기 때문에 이번 루프는 바로 나가도 되어요!
break;
}
}
}
return array;
}
console.log('정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ', insertionSort([5, 8, 4, 7, 7]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', insertionSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', insertionSort([100, 56, -3, 32, 44]));
그 외 앞으로 추가로 공부해야될 것들 메모 ...ㅎㄷㄷ
정렬 알고리즘
- 머지 정렬
- 힙 정렬
- 퀵 정렬
- 셸 정렬
- 기수 정렬
자료구조
- 트리 (참고로 트리 종류도 엄청 많아요!)
- 트라이
- 그래프
- 해시 테이블
이 밖에 재귀, DP(다이나믹 프로그래밍), 탐욕 알고리즘, 근사 알고리즘, 메모이제이션, 휴리스틱 등등