📖 오늘 학습 뽀인트!
- Linked List
- 정렬
2-1 선택 정렬
2-2 삽입 정렬
2-3 병합 정렬
2-4 퀵 정렬
1. Linked List
🕵️♀️Linked List(연결 리스트)란?
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.class Node{ constructor(data){ this.data = data; this.next = null; } } class LinkedList{ constructor(){ let init = new Node('init'); this.head = init; this.tail = init; this.count = 0; } length(){ return this.count; } toString(){ let currNode = this.head; currNode = currNode.next; let dataStr = ""; for(let i=0; i < this.count; i++){ dataStr += `${currNode.data}, `; currNode = currNode.next } return `[${dataStr.slice(0, -2)}]` } fullData(){ return JSON.parse(this.toString()) } append(data){ let newNode = new Node(data); this.tail.next = newNode; this.tail = newNode; this.count +=1; } insert(data, index){ let currNode = this.head currNode = currNode.next for(let i=0; i < index-1; i++){ currNode = currNode.next } let newNode = new Node(data) newNode.next = currNode.next; currNode.next = newNode; this.count +=1; } } test = new LinkedList();위 코드는 오늘 강의 시간에 학습한 연결 리스트의 전체 코드이다.
class Node { constructor(data, next=null) { this.data = data; this.next = next; } } class LinkedList { constructor() { let init = new Node("init"); // 1 this.head = init; // 2 this.tail = init; // 3 } append(data) { let newNode = new Node(10); // 4 // 마지막 값의 새로운 노드 this.tail.next = newNode; // 5 // 마지막 노드의 새로운 노드 this.tail = newNode; // 6 } }코드 전체가 중요하지만, 연결 리스트의 핵심이 되는 코드는 바로 위 코드이다.
1. 최초 test 라는 인스턴스가 생성됐을 때, init이라는 인스턴스가 생성되고 data에 "init" 을 넣어 전달한다. 즉, ["init", null] 이라는 노드가 생긴 것이다.
2. head는 init을 가리킨다. 즉, this.head 는 ["init", null] 이다.
3. tail는 init을 가리킨다. 즉, this.tail 은 ["init", null] 이다.
4. newNode라는 인스턴스가 생성이 되고, 안에 노드는 [10, null] 이다.
이 단계에서는 다른 노드와 연결되지 않았고 생성만 되어 있는 것이다.
5. 3번에서 this.tail은 this.head와 같은 ["init", null]를 가리킨다고 했다. 여기서는 다시 this.tail 안에 next 프로퍼티를 newNode로 변경했다. 즉, head 노드는 ["init", newNode] 이다.
6. this.tail은 4번에서 생성된 newNode를 가르킨다. 즉, this.tail = [10, null] 이다.
❓ 왜 연결 리스트를 사용할까?
- 새로운 요소 삽입 또는 삭제가 용이하다.
- 하나의 배열에 데이터가 구성되어 있기 때문에 메모리 효율이 좋다.
2. 정렬
2-1 선택 정렬
원본 배열에 최솟값을 뽑아 결과 변수에 순차적으로 삽입하는 정렬이다.
let arr = [199, 22, 33, 12, 32, 64, 72, 222, 233]; let arrSort = []; let arrLength = arr.length; for (let i = 0; i < arrLength; i++) { // 1 let numMin = Math.min(...arr); // 2 arrSort.push(numMin); // 3 arr.splice(arr.indexOf(numMin), 1); // 4 }
- 반복문 조건식에 arrLength를 따로 넣는 이유는 arr.length를 했을 경우, 실행문에서 splice로 해당 요소가 제거되면 길이가 달라지기 때문이다.
- 원본 배열인 arr에서 최솟값을 저장한다.
- 최솟값을 결과 변수인 arrSort에 저장한다.
- 원본 배열에서 결과 변수에 저장된 최솟값을 제거한다.
2-2 삽입 정렬
원본 배열을 요소를 하나씩 뽑아 이전 인덱스의 요소들과 비교하여 현재 인덱스 < 이전 인덱스 (오름차순)라면 위치를 바꿔 정렬한다.
let 입력값 = [199, 22, 33, 12, 32, 64, 72, 222, 233]; let 정렬된배열 = []; let 배열의길이 = 입력값.length; function insertIndex(sorted_arr, value) { //삽입될 위치를 찾는 함수 for (let i in sorted_arr) { // 4 if (value < sorted_arr[i]) { return i; } } return sorted_arr.length; } function insertSort(arr) { let sorted_arr = []; while (arr.length != 0) { // 1 let [value, ...arr2] = arr; // 2 arr = arr2; // 3 //삽입될 위치를 반환함 let index = insertIndex(sorted_arr, value); //삽입될 위치에 값을 반환 sorted_arr.splice(index, 0, value); // 5 } return sorted_arr; } const arr = [199, 22, 33, 12, 32, 64, 72, 222, 233]; console.log(insertSort(arr));
- arr이라는 원본 배열에서 값을 하나씩 뽑아 정렬된 배열과 비교하여 정렬된 배열에 삽입하기 때문에 arr 배열의 길이가 없어지면 전체 정렬이 완료된 것이다.
- 구조 분해 할당으로 arr 원본 배열에 첫 번째 값을 value에 넣고 나머지 값을 arr2에 넣는다.
- 첫 번째 요소를 제외한 나머지 요소들을 다시 arr 배열에 넣는다.
- 정렬된 배열에서 2번에서 정의한 배열의 첫 번째 값인 value보다 큰 값을 찾아 해당 값의 인덱스를 반환한다. 만약, 큰 값이 없다면 value가 제일 큰 값이기 때문에 length를 반환한다.
- 4번에서 반환된 index를 가지고 정렬된 배열에서 삭제한다.
2-3 병합 정렬
원본 배열을 계속 이등분하여 요소 하나로 만든 후 정렬하여 합병하는 방식의 알고리즘이다.
let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15]; function 병합정렬(입력배열) { let 입력배열의길이 = 입력배열.length; let 결과값 = []; if (입력배열의길이 <= 1) { // 4 return 입력배열; } let 중간값 = parseInt(입력배열의길이 / 2); // 1 let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값)); // 2 let 그룹둘 = 병합정렬(입력배열.slice(중간값)); // 3 while (그룹하나.length != 0 && 그룹둘.length != 0) { // 5 if (그룹하나[0] < 그룹둘[0]) { 결과값.push(그룹하나.shift()); } else { 결과값.push(그룹둘.shift()); } } while (그룹하나.length != 0) { // 6 결과값.push(그룹하나.shift()); } while (그룹둘.length != 0) { 결과값.push(그룹둘.shift()); } return 결과값; } console.log(병합정렬(입력값));
- 배열의 중간 인덱스를 저장한다.
- 재귀적으로 병합정렬 함수를 호출한다. 이때, 배열의 처음부터 중간까지를 그룹하나에 저장한다.
- 재귀적으로 병합정렬 함수를 호출한다. 이때, 배열의 중간부터 끝까지를 그룹둘에 저장한다.
- 재귀적 함수로 배열을 단일 요소로 만들었을 때 해당 배열을 반환한다.
- 그룹하나와 그룹둘, 둘 중에 하나의 배열 길이가 0이 될 때까지 반복한다. 그룹하나의 0번 인덱스와 그룹둘의 0번 인덱스 값을 비교하여 작은쪽 값을 뽑는다.
- 만약, 그룹하나의 길이가 0이 아니라면 0이 될 때까지 그룹하나의 값을 결과값이라는 배열에 저장한다.
2-4 퀵 정렬
원본 배열에서 기준이 되는 값(pivot)을 하나 뽑아 pivot과 비교하여 값이 작으면 왼쪽, 크면 오른쪽에 배치한다.
출처
let 입력값 = [66, 77, 54, 32, 10, 5, 11, 15]; function 퀵정렬(입력배열) { let 입력배열의길이 = 입력배열.length; if (입력배열의길이 <= 1) { return 입력배열; } const 피벗값 = [입력배열.shift()]; // 1 const 그룹하나 = []; const 그룹둘 = []; for (let i in 입력배열) { // 2 if (입력배열[i] < 피벗값) { 그룹하나.push(입력배열[i]); } else { 그룹둘.push(입력배열[i]); } } return 퀵정렬(그룹하나).concat(피벗값, 퀵정렬(그룹둘)); //3 } console.log(퀵정렬(입력값));구조를 보면 조금은 익숙한 코드가 보인다. 퀵 정렬은 병합 정렬의 Divide and Conquer 전략을 사용한 알고리즘이기 때문에 비슷한 부분이 있다.
1. 배열의 맨 앞 요소를 피벗값으로 지정한다.
2. 원본 배열, 그룹하나 배열, 그룹둘 배열 각각 피벗값과 비교하여 피벗값보다 값이 작으면 그룹하나에 push하고 크면 그룹둘에 push한다.
3. 퀵정렬 그룹하나를 재귀호출하여 값을 정렬하고 concat으로 피벗값과 그룹둘을 재귀호출하여 얻은 정렬된 배열을 붙인다.
