코딩 테스트 공부 : 정렬

해시 개념에 이어 오늘은 자료구조, 알고리즘 내 검색과 정렬에 대해서 공부해보고자 한다.

검색?

검색은 자료 내에 특정 값을 찾는 행위를 의미하며, 배열이 정렬되었는지에 따라서 두 가지 기법을 사용할 수 있다.

선형 검색

• 배열의 각 항목을 한 인덱스씩 순차적으로 접근하며 동작한다.
• 시간 복잡도 : O(n)
• 배열의 정렬 여부와 관계없이 동작, 정렬되지 않은 배열 검색에 좋다.

이진 검색(탐색)

• 중간 값을 확인해서, 원하는 값이 중간 값보다 큰지 작은지를 확인하며 동작한다.
• 시간 복잡도 : O(logn)
• 빠르지만, 배열이 정렬된 경우에만 사용이 가능하다.

정렬?

정렬이란 원소들을 일정한 순서대로 열거하는 알고리즘이라고 할 수 있다. 그 결과는 반드시 다음 두 조건을 충족해야 한다.

1. 출력은 비 내림차순이다.
2. 출력은 입력을 재배열하여 만든 순열이다.

대표적인 정렬 알고리즘

• 삽입 정렬(Insertion sort)
• 선택 정렬(Selection sort)
• 버블 정렬(Bubble sort)
• 병합 정렬(Merge sort)
• 퀵 정렬(Quick sort)
• 힙 정렬(Heap sort)

• 삽입 정렬(Insertion Sort)
  가장 기본적인 정렬 알고리즘으로, 작은 배열을 정렬하거나 이미 정렬된 배열에 자료를 삽입/삭제할 때 효율적이다. 시간 복잡도는 O(N^2)을 갖는다. 하지만, 모두 정렬이 되어 있는 경우에는 한 번씩만 비교를 하므로 O(n)의 시간 복잡도를 갖는다. (i-1)번째 원소까지는 모두 정렬된 상태여야 하며, (i-1)번째부터 0번째까지의 원소와 i번째 원소를 각각 비교한다. 이 때, i번째 원소보다 작은 값이 발견되면, 그 위치에 i번째 원소를 삽입한다.

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

• 선택 정렬(Selection Sort)
  선택 정렬은 앞쪽부터 정렬하는 방식이다. 주어진 배열에서 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸며 정렬한다. 맨 앞의 값을 제외한 배열로 다시 반복한다. 시간 복잡도는 O(N^2)을 갖는다.

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

• 버블 정렬(Bubble Sort)
  버블 정렬은 첫 번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다. i번째 원소와 (i+1)번째 원소의 값을 비교하고 만약 i번째 값이 (i+1)번째 값보다 크다면 둘의 자리를 바꾸어 값이 큰 원소가 뒤에 위치하게 한다. 가장 큰 값을 하나씩 뒤로 보내면서 뒤 쪽부터 정렬하는 것이다.

function bubbleSort (array) {
	for(let i=0; i<array.length; i++){
    	for(let j=1; j<array.length - i; j++){
        	if(array[j-1] > array[j]){
            	[array[j-1], array[j]] = [array[j], array[j-1]];
            }
        }
    }
    return array;
}

• 병합 정렬(Merge Sort)
  병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 분할 정복 방식이다. 정렬되지 않은 배열을 비슷한 크기의 두 부분 배열로 분할한다. 인접한 두 부분 배열을 정렬한 후 병합한다. 배열이 완성될 때까지 위 과정을 반복한다.

// 이미 정렬되어 있는 왼쪽, 오른쪽 배열을 받아서 하나로 합치는 함수
const merge = (left, right) => {
  const result = [];
  while(left.length !== 0 && right.length !== 0) {
    left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift())
  }

  return [...result, ...left, ...right]
}

const mergeSort = (array) => {
  if(array.length < 2) return array;

  let pivot = Math.floor(array.length/2)
  let left = array.slice(0, pivot)
  let right = array.slice(pivot, array.length)

  return merge(mergeSort(left), mergeSort(right))
}

• 퀵 정렬(Quick Sort)
  퀵 정렬은 하나의 중심(pivot)값을 기준으로 큰 값과 작은 값을 분류하고, 이 작업을 반복하여 정렬하는 방법이다.

const quickSort = (array) => {
  // array의 요소가 하나이면 array 자체를 그대로 반환
  if(array.length <= 1){
    return array
  }
	
  // quickSort 초기 배열을 선언, 첫 pivot 배열의 첫 번째 요소
  const pivot = [array[0]]
  const left = []
  const right = []
  
  // for loop을 실행하며 pivot보다 작은 것은 왼쪽으로, 큰 것은 오른쪽으로, 그렇지 않은 것은 pivot에 넣어 준다.
  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])
    }
  }
  // quickSort 진행 상황을 단계별로 보여주기 위한 코드
  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`)
  
  // 재귀함수 구조로 다시 선언하여 끝날 때까지 실행
  return quickSort(left).concat(pivot, quickSort(right));
}

• 힙 정렬(Heap Sort)
  힙 정렬은 완전 이진트리에서 파생된 heap 특성을 이용하여 정렬하는 알고리즘으로 '부모의 값이 자식의 값보다 항상 크거나, 항상 작다'는 조건을 만족하는 완전 이진트리 형태의 자료구조이다.

heap에 대한 개념이 수반되어야 하기에, 힙 정렬에 관해서는 더 내 것으로 만들기 위한 추가 공부가 필요하다고 생각하여, 추가 공부 후 수정하여 추가해놓고자 한다.

정렬 코딩 테스트 공부 : 프로그래머스 <K번째수>

function solution(array, commands) {
  let answer = [];

  for(let i=0; i<commands.length; i++){
    let result = array.slice(commands[i][0]-1, commands[i][1]).sort((a,b)=>a-b)
    answer.push(result[commands[i][2]-1])
  }
  return answer
}