[알고리즘] 정렬 알고리즘

정렬 알고리즘

목록안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘

 

1. 선택 정렬 (Selection Sort)

선택된 값과 나머지 데이터 중에 비교하여 알맞은 자리를 찾는 알고리즘

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[indexMin];
    arr[indexMin] = temp;
    //[arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]
  }
  return arr;
}

2. 삽입 정렬 (Insertion Sort)

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 적당한 곳으로 삽입하는 알고리즘

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let value = arr[i];
    let prev = i - 1;
    while (prev >= 0 && arr[prev] > value) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = value;
  }

  return arr;
}

3. 버블 정렬 (Bubble Sort)

인접한 두 수를 비교하여 오름차순 or 내림 차순으로 정렬

function bubble(arr) {
    for (let i = 0; i < arr.length; i++) {
      for (let j = 1; j < arr.length - i; j++) {
        if (arr[j - 1] > arr[j]) swap(j - 1, j);
      }
    }
  }

4. 병합 정렬 (Merge Sort)

둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 부분집합들을 다시 정렬된 형태로 합치는 방식

 

5. 힙 정렬 (Heap Sort)

트리 기반으로 최대 힙 트리 or 최소 힙 트리를 구성해 정렬하는 방법

class MinHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  swap(a,b){
      [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }    
  push(value) { // 값을 넣되, 오름차 순 정렬함
    this.heap.push(value);
    let curIdx = this.size() - 1;
    let parentIdx = Math.floor((curIdx -1) / 2);
      
    while (
      curIdx > 0 &&
      this.heap[curIdx] < this.heap[parentIdx]
    ) {
        this.swap(curIdx,parentIdx);
        curIdx = parentIdx;
        parentIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  pop() { // 값을 빼되, 오름차 순 정렬 함
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

    const minValue = this.peek();
    this.heap[0] = this.heap.pop();
    let curIdx = 0;
    let leftIdx = curIdx *2 +1;
    let rightIdx = curIdx *2 +2;
      
    while (leftIdx < this.size()) {
      let minChildIndex = rightIdx < this.size() && this.heap[rightIdx] < this.heap[leftIdx] ? rightIdx : leftIdx;

      if (this.heap[curIdx] < this.heap[minChildIndex]) break;
      
      this.swap(curIdx, minChildIndex);
      curIdx = minChildIndex;
        
      leftIdx = curIdx * 2 +1;
      rightIdx = curIdx *2 +2;
    }

    return minValue;
  }

  peek() {
    return this.heap[0];
  }
}

 

6. 퀵 정렬 (Quick Sort)

데이터 집합 내에 임의의 기준값을 정하고 해당 피벗으로 집합을 기준으로 두개의 부분 집합으로 나눈다