JS Search and Sort

검색과 정렬

검색

선형 검색

선형 검색은 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작

• 시간 복잡도: O(n)

이진 검색

이진 검색은 정렬된 자료에 사용할 수 있는 검색 알고리즘, 배열을 계속해서 두 부분으로 나누고 원하는 값을 찾는다.

• 중간 값을 확인해 원하는 값보다 해당 중간 값이 큰지 작은지 확인
  • 원하는 값이 중간 값보다 작은 경우 중간 값보다 작은 쪽을 검색
  • 원하는 값이 중간 값보다 큰 경우 중간 값보다 큰 쪽을 검색

정렬

거품 정렬

전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.

• 시간 복잡도: O(n2)
• 공간 복잡도: O(1)

선택 정렬

가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입하는 방식으로 동작

• 시간 복잡도: O(n2)
• 공간 복잡도: O(1)

삽입 정렬

배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열 왼쪽의 정렬된 부분으로 이동시킨다.

• 시간 복잡도: O(n2)
• 공간 복잡도: O(1)

빠른 정렬

기준점을 획득한 다음 해당 기준점을 기준으로 배열을 나눈다. 한쪽은 기준점보다 큰 항목들, 다른 쪽에는 기준점보다 작은 항목들이 위치한다. 이런식으로 모든 항목이 정렬될 때까지 이 과정을 반복

• 가장 이상적인 기준점은 배열의 중간 값
• 일반적으로 분할 부분의 첫 번째 항목, 중간 항목, 마지막 항목의 중간 값을 취해 기준점을 얻는다.
• 재귀 정렬이고 분할 정복 방식을 사용해 시간 복잡도를 O(n log n)으로 낮춘다.
• 시간 복잡도: 평균 O(n log n), 최악의 경우 O(n2)
• 공간 복잡도: O(n log n)

빠른 선택

정렬되지 않은 목록에서 K번째로 작은 항목을 찾는 선택 알고리즘, 기준점을 선택하고 배열을 분할한 다음 한쪽만을 재귀적으로 수행한다.

• 시간 복잡도: O(n)

병렬 정렬

각 하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나누고 각 하위 배열을 정렬된 순서로 연결한다. 병합 정렬의 시간 복잡도는 O(n log n)임이 보장된다.

• 시간 복잡도 O(n log n)
• 공간 복잡도: O(n) 병합할 n개의 배열을 생성해야 하기 때문에 공간 복잡도가 크다.

계수 정렬

값들을 비교하지 않기 때문에 O(k+n)시간 안에 수행된다. 숫자에 대해서만 동작하며 특정 범위가 주어져야 한다. 배열 안 각 항목의 등장 횟수를 세고, 해당 등장 횟수를 사용해 새로운 배열을 생성할 수 있다.

• 시간 복잡도: O(k+n)
• 공간 복잡도: O(k)