[Front-end🦁] #34 정렬

1. Linked List

#33 에서 어제 하던 연결 리스트의 insert 함수를 구현을 마쳤다. 위 글에 이어서 정리했다.

2. 정렬 알고리즘

모두 오름차순 기준 설명, 필기!

1. 선택정렬

배열에서 최솟값을 찾아서 새로운 배열에 넣는다. 그리고 남은 배열에서 또 최솟값을 찾아서 새로운 배열에 넣는다...

let 입력값 = [199, 22, 33, 12, 32, 64, 72, 222, 223];
let 정렬된배열 = [];
let 길이 = 입력값.length;
//
for(let i = 0; i < 길이; i++) {
    정렬된배열.push(Math.min(...입력값));
}

2. 삽입정렬

첫번째 값은 그냥 넣고, 그 다음 것이 자신의 위치를 찾아서 들어간다.

function insertIndex(sorted_arr, value) {
    //삽입될 위치를 찾는 함수
    for(let i in sorted_arr){
        if(value < sorted_arr[i]){
            return i;
        }
    }
    return sorted_arr.length;
}

function insertSort(arr) {
    let sorted_arr = [];
    while (arr.length != 0){
        let value = arr.shift();
        //삽입될 위치를 반환함
        let index = insertIndex(sorted_arr, value);
        //삽입될 위치에 값을 반환
        sorted_arr.splice(index, 0, value);
    }
    return sorted_arr;
}
const arr = [199, 22, 33, 12, 32, 64, 72, 222, 233];
console.log(insertSort(arr))

3. 병합정렬

(mergesort - 분할 정복 방법)
배열을 원소가 0개나 1개가 될 때 까지 반으로 계속 쪼갠 후, 병합 알고리즘을 이용하여 합치는데, 합칠 때 작은 것부터 들어가도록 합쳐준다.

function 병합정렬(입력배열){
    let 입력배열의길이 = 입력배열.length;
    let 결과값 = [];
    // 자르기
    if (입력배열의길이 <= 1){
        return 입력배열
    }
    let 중간값 = parseInt(입력배열의길이 / 2);
    // 자른 배열로 재귀 호출
    let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
    let 그룹둘 = 병합정렬(입력배열.slice(중간값))
    // 병합
    while (그룹하나.length != 0 && 그룹둘.length != 0) {
        if(그룹하나[0] < 그룹둘[0]) {
            결과값.push(그룹하나.shift());
        } else {
            결과값.push(그룹둘.shift());
        }
    }
    while (그룹하나.length != 0) {
        결과값.push(그룹하나.shift());
    }
    while (그룹둘.length != 0) {
        결과값.push(그룹둘.shift());
    }
    return 결과값
}

4. 퀵정렬

function 퀵정렬(입력배열){
    let 입력배열의길이 = 입력배열.length;
    if (입력배열의길이 <= 1) {
        return 입력배열
    }
    const 피벗값 = [입력배열.shift()]; //기준점
    const 그룹하나 = [];
    const 그룹둘 = [];
    for (let i in 입력배열) {
        if (입력배열[i] < 피벗값) {
            그룹하나.push(입력배열[i]);
        } else {
            그룹둘.push(입력배열[i]);
        }
    }
    console.log(`그룹하나 : ${그룹하나}\n그룹둘 : ${그룹둘}\n피벗값 : ${피벗값}\n`);
    return 퀵정렬(그룹하나).concat(피벗값, 퀵정렬(그룹둘));
}

3. 페이지 교체 알고리즘

1. FIFO

말 그대로 참조 횟수 같은 것과 상관 없이 들어온 순서대로 나가기.

2. LRU (Last Recently Used)

계속 밀어내기! 가장 최근에 사용한 것이 뒤로 가고, 옛날에 사용한 것은 앞으로 가다가 사라짐.

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“Jeju”] 1회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“Jeju”, “Pangyo”] 2회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“Jeju”, “Pangyo”, “Seoul”] 3회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“Pangyo”, “Seoul”, “NewYork”] 4회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“Seoul”, “NewYork”, “LA”] 5회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“NewYork”, “LA”, “Seoul”] 6회차

[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”]
[“NewYork”, “Seoul”, “LA”] 7회차

hit - 1
miss - 5

3. 내일 배울 것 잠시 둘러보기

트리, 이진트리, DFS, BFS에 대해서 호다다다다다닥 짚어보고 수업이 끝났다.

4. 코드라이언 강의 수강

세렝게티 만들기 강의를 수강했다. 원래 답답한거 못견뎌서 2배속으로 놓고 타이핑 시간 필요하면 일시정지 하면서 강의를 수강하는 편이라 오늘 코드 짜는건 다 들어버렸다. 내일 강의 시간에 배포 관련된거 듣고 코드 짜는거 다시 리마인드 해보면 될 듯!!

5. 작은 회고

1. 선택정렬, 삽입정렬, 병합정렬, 퀵정렬을 배웠다.

근데 C로 하면서 배열 막 999개 미리 선언해놓고 이랬던거 생각하면... splice shift 이런거 써서 구현하니까 완전.... 날로 먹는 기분이다.

2. 페이지 교환 알고리즘도 했는데

사실 진짜 코드를 짠게 아니라 알고리즘은... 아는거네.. 하면서 좀 루즈하게 듣는 감이 있는듯... 얼른 각잡고 복습해야겠다.