04-sorting.md

정렬(Sorting) 알고리즘

이코테 책

정렬 알고리즘 개요

정렬(Sorting): 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.

버블 정렬 (bubble sort)

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

//데이터길이 - 1만큼 반복을 함
for index in range(데이터길이 - 1): 
 //조건을 몇번처리하냐
  swapFlag = false;
	for index2 in range(데이터길이 - index - 1):// "데이터길이 - index -1"은 턴의횟수가 늘어날때마다 1씩 줄어들게 체크함
			if 앞데이터 > 뒤데이터:
				swap(앞데이터, 뒤데이터)
				swapFlag = true;

  if swap == false: 
		break;

return data

버블정렬 시간복잡도

• 반복문이 2개니까 O(n^2)
• 완전 정렬이 되어있는 상태라면(이미 정렬된상태) O(n)

선택 정렬(Selection Sort)

1. "가장 작은 것을 선택"

• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복해서 정렬하는 알고리즘
• 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료되는 것을 알 수 있다.
• 시간 복잡도
  • O(N^2)
  • 선택 정렬은 데이터의 개수가 많아지면 정렬 속도가 급격히 느려진다.

for stand (데이터) {
	최소값인덱스 = 기준값인덱스
	for index (stand 다음데이터) {
		if ( 데이터[최소값인덱스] > 데이터[현재인덱스] ) {
			최소값인덱스 = 현재인덱스
		}
	}
	swap(최소값인덱스, 기준값인덱스)
}

var array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];

for (var i = 0; i < array.length; i++) {
    var min_index = i;
    for (var j = i + 1; j < array.length; j++) {
        if (array[min_index] > array[j]) {
            min_index = j;
        }
    }
    [array[i], array[min_index]] = [array[min_index], array[i]];
}

console.log(array);

삽입 정렬(Insertion Sort)

1. "데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입"
   
2. 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더이상 데이터를 살펴볼 필요없이 그자리에 삽입되면 되는 것이다.
3. 이미 데이터가 정렬되어 있는 경우 매우 빠르고, 데이터가 무작위이면 매우 느림 (퀵정렬과 반대)

• 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다.
• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다.
• 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입정렬이라고 부른다.
• 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다
• 시간 복잡도
  • O(N^2)
  • 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 보통은 삽입정렬이 비효율적이나,
    정렬이 되어있는 상황에서는 퀵 정렬 등 다른 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

var array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];

for (var i = 1; i < array.length; i++) {
    for (var j = i; j > 0; j--) {
        if (array[j] < array[j - 1]) {
            [array[j], array[j - 1]] = [array[j - 1], array[j]];
        } else {
            break;
        }
    }
}

console.log(array);

퀵 정렬

1. 가장 많이 사용되는 알고리즘, '빠른 정렬 알고리즘'
   
2. "기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자"
3. 데이터가 무작위이면 퀵 정렬이 매우 빠르고, 이미 데이터가 정렬된 경우는 매우 느림(삽입정렬과 반대)

• 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

• 피벗(pivot)이 사용됨. 큰숫자와 작은숫자를 교환할때 교환하는 기준을 피벗이라고함

• 호어 분할 방식 (피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵정렬을 구분하는데, 가장 대표적인 분할방식인 호어분할방식 기준)

  • 리스트에서 첫번째 데이터를 피벗으로 정한다.
  • 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
  • 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
  • 이 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.

• 시간 복잡도

  • O(NlogN)

• 피벗을 설정하여 정렬을 수행한 후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.

• 재귀함수형태로 코드구현

  • 종료 조건? 현재 리스트의 데이터 개수가 1개인 경우다. 리스트의 원소가 1개라면 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다.

let array = [5,7,9,0,3,1,6,2,4,8];

function quickSort(array, start, end) {
    if (start >= end) {
        return;
    }

    let pivot = start;//0
    let left = start + 1; //1
    let right = end; //9

    while (left <= right) {// 1 <= 9  // 2 , 8 // 2, 7
        while (left <= end && array[left] <= array[pivot]) {
          // array[1] <= array[0]
            left++;
        }
        while (right > start && array[right] >= array[pivot]) {// 6, 5
          // 9 > 0 && array[9] >= array[0]
            right--;
        }
        if (left > right) {// 1 > 8
            [array[right], array[pivot]] = [array[pivot], array[right]];
        } else {
            [array[left], array[right]] = [array[right], array[left]];
        }
    }

    quickSort(array, start, right - 1);
    quickSort(array, right + 1, end);
}

quickSort(array, 0, array.length - 1);
console.log(array);

계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

1. 데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을때만 사용할 수 있다
   
2. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
3. 데이터의 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.
4. 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간문제로 인하여
   입력되는 데이터의 개수를 1,000만개 이상으로 설정할 수 없는 경우가 많기 때문에 정렬 문제에서의 데이터 개수는 1,000만개 미만으로 출제될 것이다.

• 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고(가장큰데이터+1)
  데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수정렬이 완료된다.
  정렬된 결과는 리스트의 첫번째 데이터부터 하나씩 그값만큼 인덱스를 출력하면 된다. (0이 2개면 0을 2번 출력 00)

• 시간 복잡도

  • O(N+K) : 데이터개수를 N, 최대값의크기를 K

• 공간 복잡도

  • O(N+K)
    • 계수 정렬은 때에 따라서 심각한 비효율성을 초래한다.
    • 동일한 값을 가지는 데이터가 여러개일 때 적합한 알고리즘이며, 데이터 특성을 파악하기 어려우면 퀵정렬을 사용하자
    • e.g. 성적 (100점이 여러명이라면)

• 정렬 알고리즘 중 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.

• 기수 정렬은 계수 정렬에 비해 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다.

let array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2];
let count = Array(Math.max(...array) + 1).fill(0);

for (let i = 0; i < array.length; i++) {
   count[array[i]]++;
}

let result = [];
for (let i = 0; i < count.length; i++) {
    // i가 얼마나 자주 등장하는지를 나타내는 count[i]를 사용해 해당 숫자만큼 반복
   for (let j = 0; j < count[i]; j++) {
      result.push(i);// 결과 배열은 입력 배열의 원소를 오름차순으로 정렬하게됨
   }
}

console.log(result.join(' '));

병합 정렬

병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다.

대부분의 프로그래밍 언어에서 제공하는 표준 라이브러리의 기본 정렬 함수는 병합 정렬 혹은 퀵 정렬에 기반한다. 퀵 정렬에 기반하는 경우에도 O(NlogN)을 보장하도록 구현되어 있다.

---

코딩테스트에서 정렬 알고리즘이 사용되는 경우 문제유형 3가지

1. 정렬 라이브러리로 풀 수 있는 문제
   1. 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
   1. 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제
   1. 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

---

이코테 책 문제

[실전문제] 위에서 아래로

function descSort(n, ...rest) {
  return rest.sort((a, b) => b - a).join(' ');
}

[실전문제] 성적이 낮은 순서로 학생 출력하기

function printLowScore(n, ...rest) {
    const studentScore = rest.map(item => ({
        name: item.split(' ')[0],
        score: item.split(' ')[1]
    }));

    return studentScore.sort((a,b) => {return a.score-b.score}).map(item => item.name).join(' ');
}

printLowScore(2, '홍길동 95', '이순신 77')

[실전문제] 두 배열의 원소 교체