function solution(arr) {
for(let i = arr.length; i > 0; i--) {
let j = 0;
while(j < i) {
if(arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp
}
j++;
}
}
return arr
}
console.log(solution([3, 4, 5, 2, 6, 7, 9, 1, 8, 0]))
function solution(array) {
for(let i = 0; i < array.length; i++) {
let tmpMinIdx = i;
for(let j = i + 1; j < array.length; j++) {
if(array[j] < array[tmpMinIdx]) {
tmpMinIdx = j
}
}
let tmp = array[i];
array[i] = array[tmpMinIdx];
array[tmpMinIdx] = tmp;
}
return array
}
console.log(solution([3, 4, 5, 2, 6, 7, 9, 1, 8, 0]));
* 8,4,2,3 ⇒ 4,8,2,3
4,8,2,3 ⇒ 4,2,8,3 ⇒ 2,4,8,3
2,4,8,3 ⇒ 2,4,3,8 ⇒ 2,3,4,8
function solution(arr) {
for (let i = 1; i < arr.length; i++) { // i 가 위 예시의 빨간색역할
let curIdx = i;
let isTrue = true;
while (isTrue) {
let tmpIdx = curIdx - 1; // tmpIdx가 위 예시의 파란색 역할
if (arr[curIdx] < arr[tmpIdx]) { // 빨간색이 더 작으면 앞으로 보내기(파란색과 자리 바꾸기)
let tmp = arr[curIdx];
arr[curIdx] = arr[tmpIdx];
arr[tmpIdx] = tmp;
curIdx--;
} else {
isTrue = false; // 파란색이 더 작으면 앞에는 이미 정렬된 상태이므로 더이상 검사를 안해도된다.(while을 멈춰도된다)
}
}
}
return arr
}
console.log(solution([4, 2, 7, 1, 3]));
console.log(solution([8, 4, 2, 3]));
퀵정렬을 구현하는 방법의 첫번째는 왼쪽(피벗보다 작은값들)과 오른쪽(피벗보다 큰 값들)으로 쪼개서 배열을 만들고 각각 배열에 재귀를 타면 쪼개짐이 반복되면서 결국 left와 right의 길이가 1개로 되는시점이 온다. 그 지점에 다다랐을떄 모든 재귀들은 리턴값을 내면서 정렬이 되는 것 이다. 하지만 이 방법은 코드구현은 수월하지만 메모리 낭비가 심하다는 단점이 있다.
두번째 방법은 swap으로 구현하는것인데. 이것은 메모리가 전혀 필요가없다. 일단은 첫번쨰 방법만 이해했는데 내일은 두번째 방법도 이해해서 꼭 구현해봐야겠다.! 재귀는 너무 어렵당..
function quickSort(array) {
if (array.length < 2) { // 재귀를 계속 돌다보면 결국 left와 right의 길이는 1이될것이다. 그것을 상상하면서 난 그저 현재 배열에서 left와 right를 쪼개는 것 이다.
return array;
}
const pivot = [array[0]];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else if (array[i] > pivot) {
right.push(array[i]);
} else {
pivot.push(array[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
//연습할 코드
function quickSort(array, left = 0, right = array.length - 1) {
if (left >= right) {
return;
}
const mid = Math.floor((left + right) / 2);
const pivot = array[mid];
const partition = divide(array, left, right, pivot);
quickSort(array, left, partition - 1);
quickSort(array, partition, right);
function divide(array, left, right, pivot) {
while (left <= right) { // 왼쪽이 오른쪽보다 작거나 같을때까지만 반복
while (array[left] < pivot) { // 왼쪽의 원소가 피벗보다 작으면 왼쪽++
left++;
}
while (array[right] > pivot) { // 오른쪽원소작 피벗보다 크면 오른쪽--
right--;
}
if (left <= right) { // 현재 왼쪽 오른쪽 자리 바꾸기 (같다면 그냥 그대로 겠지?)
let swap = array[left];
array[left] = array[right];
array[right] = swap;
left++;
right--;
}
}
return left;
}
return array;
}