🏷️JavaScript
선택정렬
가장 작은 것을 선택해서 제일 앞으로 보내는 것을 반복하는 알고리즘
- 가장 기초적이고 원시적이다.
방법
- 첫 인덱스부터 마지막 인덱스까지 반복문을 돌린다.
- 원소들 중 제일 작은 원소를 찾는다.
- 현재 인덱스의 원소와 제일 작은 원소의 자리를 바꾼다. ⇒ 바꿀 때는 스와핑
- 정렬이 완료되었으므로 다음 인덱스로 넘어간다.
시간복잡도
O(N*N) ⇒ 매우 비효율적이다.
버블정렬
옆에 있는 값과 비교하여 더 작은 숫자를 앞으로 보내주는 것을 반복하는 알고리즘
- 가장 비효율적인 알고리즘이다.
방법
- 첫 인덱스부터 반복문을 돌린다.
- 현재 인덱스의 원소와 오른쪽 원소의 값을 비교하여 현재 원소가 더 크면 자리를 바꾼다.
- 인덱스를 하나씩 증가시키며 위 과정을 반복한다.
- 마지막 인덱스는 가장 큰 원소가 차지하여 정렬이 완료된다.
- 정렬이 완료된 마지막 인덱스를 제외하고 위 과정을 반복한다.
시간복잡도
O(N*N) ⇒ 실제로는 선택 정렬보다 느리다.
버블 정렬이 선택 정렬보다 더 느린 이유? 자리를 매번 바꾸기(스와핑) 때문.
삽입정렬
각 숫자를 적절한 위치에 (필요할 때만)삽입한다.
방법
- 첫 인덱스부터 반복문 시작
- 현재 값이 왼쪽 값들 중 적절한 사이에 들어간다.
- 이때 왼쪽 값들은 정렬이 되어있다고 판단하고, 왼쪽으로 한 칸씩 이동하면서 비교하다가 나보다 작은 수를 만나면 멈춘다.
- 다음 인덱스로 넘어가서 위 과정을 반복한다.
ex) 1 4 5 6 3 2 가 있을 때, 4를 정렬하려면 4의 왼쪽으로 이동하다가 4보다 작은 수를 만나면 오른쪽에 삽입한다.
시간 복잡도
때문에 거의 정렬된 상태라면 가장 빠른 알고리즘. 하지만 O(N^2)
