1. Sort

2. Bubble Sort

3. Selection Sort

4. Insertion Sort

1. Sort(정렬)

A부터 Z까지 기준으로 정렬하든가 큰 수에서 작은 수 기준으로 정렬할 수도 있음.

이진검색처럼 빠른 알고리즘을 사용하려면 일단 먼저 배열 정렬을 해야 함.

동일한 시간복잡도를 갖고 있다하더라도 매우매우 다르게 나타날 수 있음.

삽입과 선택 정렬은 작은 DB 기준으로 훌륭한 알고리즘임**(데이터가 커지면 커질수록 좀 느려지지만)**

2. Bubble Sort(버블 정렬)

2-1) Bubble Sort

배열에서 2개의 아이템을 선택하고 비교해서

왼쪽이 오른쪽보다 크면 교환(Swap)할 거임.

오른쪽으로 이동해서 해당 프로세스를 반복

2-1)-1. 비효율성

이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해

너무 많이 교환하는 낭비가 발생할 수도 있음.

버블 정렬은 수행 한 번 만에 모든 원소가 정렬되는 것을 보장하지 않음.

최악의 상황인 경우 최대한의 횟수를 실행해줘야 하므로 경제적이지 않음.

2-2) Bubble Sort의 시간 복잡도

배열의 N-1의 아이템을 비교해야함.

좋은 알고리즘은 아님.

2-3) Bubble Sort Image

3. Selection Sort(선택 정렬)

3-1) Selection Sort

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있음.

정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수를 찾아

첫 번째 위치의 수와 교환해주는 방식의 정렬임.

정렬되지 않은 배열에서 가장 작은 숫자를 찾음.

즉 이는 N-1 비교를 하는 거임.

버블 정렬과 같지만 다르게 N번의 스왑을 하지 않음.

3-1)-1. 효율성

선택 정렬은 교환 횟수를 최소화하는 할 수 있음.

3-1)-2. 비효율성

각 자료를 비교하는 횟수는 증가함.

3-2) Selection Sort Image

→ 선택정렬에서는 매번 싸이클 마다 1번의 스왑만 하면 됨.

→ 선택정렬이 버블정렬보다 2배 더 빠를 수도 있음에도 선택정렬의 시간복잡도 역시 O[n^2]임.

4. Insertion Sort(삽입 정렬)

4-1) Insertion Sort

삽입정렬은 선택정렬보다 빠름.

왜냐면 삽입정렬은 필요한 아이템만 스캔을 함.

4-2) Insertion Sort의 시간 복잡도

→ 삽입정렬이 선택정렬보다 빨라도 버블정렬보다 빨라도

→ 삽입정렬의 시간복잡도와 동일하게 O[n^2]임.