선택정렬
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
let temp = arr[i]
arr[i] = arr[minIndex];
arr[minIndex] = temp
}
return arr
}
console.log(selectionSort([5,1,2,3,6]))
내부 반복을 할 때 마다 가장 작은 값의 인덱스를 찾아내고 내부 반복이 끝나면 가장 작은 값이 맨앞 인덱스로 온다. 외부 반복으로 배열의 원소 갯수만큼 반복하여 최종정렬
버블정렬
let arr = [9,8,7,6,5,4]
function bubbleSort(arr) {
for (let i = 0; i < arr.length-1; i++) {
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp
}
}
}
return arr
}
console.log(bubbleSort(arr))
내부 루프를 돌 때 첫번째값과 바로 뒤 값이랑 비교하고 첫번째 값이 더 크면 위치를 바꿔준다. 안쪽 루프는 j와 j+1값이랑 비교해야 하므로 범위를 length-1로 두고 (length로 두면 마지막 j+1값이 없는값이랑 비교해야 하므로 오류생긴다) 바깥족 루프는 배열의 마지막원소는 이미 J+1에 의해 정렬된 상태이므로 굳이 한번 더 돌릴 필요는 없으므로 length-1로 한다.
삽입정렬
let arr = [2, 4, 1, 6, 3]
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
}
else {
break;
}
}
}
return arr
}
console.log(insertSort(arr))
첫번째 원소는 고정되어 있으므로 비교를 시작하는 바깥쪽 루프에서 i=1로 시작했다. 내부에서는 비교를 시작하는 지점부터 맨왼쪽까지 쭉 비교를 시작해서 전 값이 더 크면 기존값과 값을 바꾼다. 단 기존값이 왼쪽값보다 크면 굳이 정렬을 할 필요가 없으므로 break를 써서 쓸데없는 낭비를 하지 않는다.
병합정렬
병합정렬의 기본적인 로직 분할(배열의 크기를 절반으로줄임) -> 정복(두개의 부분배열을 정렬된 하나의 배열로 만든다. -> 조합
일반적으로 병합정렬은 재귀 함수를 이용하는데 함수 호출 횟수가 많이 발생해 오버헤드로 이어질수 있다
재귀함수는 기존 함수에서 만들어진 새로운 함수가 완전히 끝나야 기존함수가 끝나기 때문에 스택으로 이해하면 편하다.
@banhogu