💻 Algorithm
[알고리즘] Sorting Algorithm 정렬 알고리즘
date
Jul 11, 2023
slug
algorithm-sorting
author
status
Public
tags
Tech
summary
type
Post
thumbnail
updatedAt
Jul 11, 2023 02:47 PM
category
💻 Algorithm
정렬 알고리즘
1. 버블 정렬
정렬 입문용이다. 효율적이진 않다.
- 앞에서부터 두개씩 비교한다.
- 두개 중에 더 큰 수가 오른쪽에 오도록 바꾼다.
- 비교하고 스와이핑하기를 반복한다.
최악의 경우: 모든 아이템을 교환하는 경우
시간 복잡도: O(n^2)
2. 선택 정렬
- 가장 작은 아이템이 있는 위치를 저장한다.
- 그 수를 배열의 맨 앞에 오도록 바꾼다.
- 그리고 정렬되지 않은 부분의 배열에서부터 시작해서 다시 탐색하며 가장 작은 아이템을 찾는다.
- 그다음 두번째 앞에 오도록 바꾼다.
- 반복한다.
시간 복잡도: O(N^2)
⇒ 선택 정렬은 버블 정렬보다 훨씬!!! 효율적이다.
but, 시간 복잡도는 같다.
3. 삽입정렬
- 한 index에서 왼쪽과 비교해서 순서대로 바꾼다.
- 그리고 계속해서 자신의 왼쪽과 비교하며 바꾸기를 반복하고, 자리를 찾는다.
작은 DB의 정렬 알고리즘에는 효율적이다.
시간 복잡도: O(N^2)
⇒ 선택 정렬은 선택 정렬, 버블 정렬보다 훨씬!!! 효율적이다.
but, 시간 복잡도는 같다.
그렇다고 big O가 엉터리냐???
그것은 아니다. 이럴 경우 최악의 시나리오를 보지말고, 평균 시나리오를 살펴봐야 한다.
디테일하게 살펴보면, 삽입정렬의 최고 시나리오는 O(N)이다.
디테일하게 보면 다른 시간 복잡도를 발견해낼 수 있다!
