sort.md

Sort, 정렬 알고리즘

• 데이터 사이에는 비슷한 속성이나 일련의 순서가 있음
• 데이터를 정렬하면 중복 데이터나 필요한 데이터를 빠르게 찾아낼 수 있음

1. 선택 정렬 (Selection sort)

• 선형 탐색을 응용한 알고리즘
• 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교해 최솟값을 첫번째에 놓고, 두번째부터 마지막 자료까지 차례대로 비교해 그 중 최솟값을 찾아 두번째 위치에 놓는 과정을 반복
• 1회전을 수행하고나면 최솟값이 맨 앞에 오게되므로 그 다음 회전 시에는 두번째 자료를 가지고 비교함

과정

1. 주어진 배열에서 최솟값 찾기
2. 그 값을 맨 앞에 위치한 값과 교체
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체
4. 하나의 원소가 남을때까지 1-3과정 반복하기

특징

• 장점
  • 자료 이동 횟수가 미리 결정됨
• 단점
  • 안정성을 만족하지 않음
  • 값이 같은 경우 상대적 위치가 변할 수 있음

시간복잡도

• 비교 횟수
  • 2개의 for문
  • 외부 (n-1)번
  • 내부 (최솟값 찾기) n-1, n-2, n-3, ..., 2, 1 번
• 교환 횟수
  • 외부 루프의 실행횟수와 동일 (배열의 길이와 동일)
• T(n) = (n-1) + (n+2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

2. 버블 정렬 (Bubble sort)

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 두 원소를 비교해 크기가 순서대로 되어있지 않으면 서로 교환함
• 인접한 두 원소를 비교하다보니 이미 초기에 가장 왼쪽에 있는 수가 가장 오른쪽으로 이동함
  • 맨 뒷자리는 바로 결정됨 (때문에 j-1-i까지만 반복하면 됨)

특징

• 장점
  • 구현이 간단함
• 단점
  • 하나의 요소가 가장 왼쪽에서 오른쪽으로 이동하려면, 배열의 모든 요소들과 교환되어야 함
  • 최종 정렬 위치에 이미 있는 경우라해도 교환됨
  • 단순하지만 자료의 교환(SWAP) 작업이 자료의 이동(MOVE)작업보다 복잡하므로 거의 쓰지 않음

시간복잡도

• 비교 횟수
  • n-1, n-2, n-3, ..., 2, 1번 = n(n-1)/2
• T(n) = O(n^2)

3. 삽입 정렬 (Insertion sort)

• 새로운 카드를 정렬된 카드 사이의 올바른 위치를 찾아 삽입
• 새로 삽입될 카드의 수만큼 반복하면 됨

특징

• 장점
  • 안정적인 정렬방법
  • 알고리즘이 매우 단순하므로 레코드가 적은 경우 유리함
  • 레코드가 대부분 정렬되어 있는 경우 매우 효율적
• 단점
  • 비교적 많은 레코드들의 이동을 포함함
  • 레코드 수가 많고 레코드가 큰 경우 적합하지않음

시간복잡도

• 최선
  • O(n)
• 최악
  • O(n^2)

4. 셸 정렬

5. 병합 정렬

6. 퀵 정렬

7. 힙 정렬

8. 버킷 정렬

9. 기수 정렬

---

2차원 배열 sort

x, y를 합하여 정렬하기

const arr = [[6, 5], [2, 2], [4, 3], [4, 5], [10, 3]];

// 오름차순
arr.sort((a,b) => a[0] + a[1] - (b[0] + b[1])); // x1과 y1를 더한 값과 x2와 y2를 더한 값을 오름차순으로 정렬 

// 내림차순
arr.sort((a,b) => b[0] + b[1] - (a[0] + a[1])); // x2와 y2를 더한 값과 x1과 y1을 더한 값을 내림차순 정렬 

x값에 의해 정렬하되, x가 같으면 y를 기준으로 오름차순 정렬하기

arr.sort((a,b) => {
  if(a[0] === b[0]) { // x1과 x2가 같은경우
    return a[1] - b[1] // y에 따라 오름차순 정렬
  } else {
    return a[0] - b[0] // 같지 않은 경우엔 x에 따라 오름차순 정렬
  }
});