기초 정렬들 개념 한번에 정리(선택, 버블, 삽입, 퀵 정렬)

1. 선택 정렬

- 개념 : 가장 작은 걸 선택해서 가장 앞으로 보낸다.

- 코드 내용 : 모든 자리의 최소값을 스캔해서 가장 앞에 있는 숫자와 위치 바꿈.

- 시간복잡도 : O(N*N)

 

2. 버블 정렬

- 개념 : 당장 옆에 있는 것과 비교

- 코드 내용 : 당장 옆에 있는 것과 서로 비교해서 순서에 맞게 서로 위치 바꿈.

- 시간복잡도 : O(N*N), O(N*N)인 정렬 중 가장 느림

 

3. 삽입 정렬

- 개념 : 앞 숫자들이 정렬돼 있다고 가정하고 다음 숫자를 사이에 삽입.

- 코드 내용 : 정렬돼 있는 숫자를 기준으로 바로 오른쪽에 있는 숫자의 크기와 비교하여 (정렬숫자)>(정렬안된 오른쪽숫자) 이면 둘의 위치를 바꾼다. 정렬될 때 까지 반복한다.

- 시간복잡도 :  O(N*N),  O(N*N)인 정렬 중 가장 빠름, 거의 정렬돼 있는 경우 정렬 알고리즘중에서도 가장 빠름.

 

4. 퀵 정렬

- 개념 : 왼쪽, 오른쪽으로 나누어 생각

- 코드 내용 :

1) (첫 피벗값은 맨 앞) 왼쪽에선 오른쪽으로 이동하며 피벗값보다 큰 숫자 찾음, 오른쪽에선 왼쪽으로 이동하며 피벗값보다 작은 숫자 찾음.

2) 만약 이 두 숫자들의 위치가 엇갈리면 피벗값과 작은 값 위치 바꿈, 안엇갈렸으면 큰 값과 작은 값 위치 바꿈. -> 엇갈릴 때 까지 while문으로 반복

3) 엇갈린 후엔 피벗값과 교체했던 작은 값이 새로운 피벗값이 되어 피벗값을 기준으로 왼쪽과 오른쪽 나누어 똑같이 진행 -> 여기서 재귀함수 사용

- 시간복잡도 : O(N*logN) 단, 대부분 정렬되어 있으면 O(N*N)으로 이때는 삽입 정렬을 사용해야 함.